cheetsheet
[Cheat Sheet]에라토스테네스의 체
function solution(num) { let arr = Array(num + 1).fill(true); arr[0] = false; arr[1] = false; for(let i = 2; i * i
all category
자료구조와 알고리즘
탐욕 알고리즘 (Greedy Algorithm)
⚡탐욕알고리즘(Greedy Algorithm)이란? 매순간 최적 해를 선택하면서 최종적으로 최적해에 도달하는 알고리즘 설계기법 쉽게 생각하면 당장 눈 앞에 놓인 선택지 A, B 중 당장 더 좋은 선택지를 고르는걸 반복하는 것으로 최종적인 해답에 도달하는 방법입니다. 욕은 인간에게는 죄악이지만 문제를 풀 때에는 아주 좋은 방법이 될 수도 있군요 지역적으로는 최적인 선택이지만 항상 전역적으로 최적이라는 보장은 없지만 보통 탐욕알고리즘을 활용하는 문제는 지역적으로 최적이면서 전역적으로도 최적인 문제들입니다. ⚡탐욕알고리즘 정리 1. 매순간 최적해를 선택하면 최종적으로 최적해에 도달 2. 현재 상황에서 지금 당장 좋은 것만 고르는 방법 3. 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이..
programmers
[Programmers Level 0] 분수의 덧셈 Javascript
⚡문제정보 분수의 덧셈 문제입니다. 수학에 약하다보니 통분을 해야한다는건 알겠는데.. 코딩을 어케해야하지.. 하면서 분수에 대해 찾아보다보니 가장 쉽게 통분을 하는 방법은 분모와 분모를 서로 곱해주는것이었습니다 서로를 곱해주면.. 같은 값이 될 수 밖에 없겠죠 크으 역시 사람들 똑똑하다 통분 해준 다음 기약분수로 만들어야하는데 기약분수로 만들어주려면 분자와 분모의 최소공배수로 나눠주면 해결 🙄제한사항 0 { if (b === 0) return a return gcd(b, a % b) } let least = gcd(wholemeal[0],wholemeal[1]) let answer = [wholemeal[0] / least , wholemeal[1]/least] return answer } 코드 설명은 ..
programmers
[Programmers Level 1] 두개 뽑아서 더하기 Javascript
⚡문제정보 for문을 이중으로 쓰면 쉽게 풀 수 있는 문제입니다 시간복잡도를 더 낮출 수 있을지가 고민되네요 🙄제한사항 numbers의 길이는 2 이상 100 이하입니다. numbers의 모든 수는 0 이상 100 이하입니다. 🔍접근방법 서로 다른 인덱스끼리 전부 더해준다음 set으로 중복을 없애준다. 🔍나의 풀이 function solution(numbers) { let answer = [] for(i=0; i
programmers
[Programmers Level 1] 소수찾기 Javascript
⚡문제정보 1부터 입력받은 숫자 n사이의 모든 소수의 개수를 반환하는 문제입니다. 처음엔 이중for문으로 구현했는데 그렇게 문제를 풀었더니 효율성 테스트에서 멸망했습니다. 🔍나의 첫번째 풀이 function solution(n) { let answer = 0 for(i=2 ; i
cheetsheet
[Cheat Sheet] 소인수 분해 코드
function solution(n) { let answer = [] let divisor = 2 while (n >= 2) { if (n % divisor === 0) { answer.push(divisor) n = n / divisor; } else divisor++; } return answer } 2부터 소인수분해를 시도합니다. 만약 n이 divsior로 나눠진다면 계속 divisor로 나눠줍니다. 나눠지지 않는다면 divisor의 값을 높여서 다시 비교해줍니다.
programmers
[Programmers Level 1] 이상한 문자 만들기 Javascript
⚡문제정보 문자열이 주어지고 문자열은 공백을 기준으로 나뉘어집니다 짝수 인덱스는 대문자로 홀수 인덱스는 소문자로 바꿔야하는데 띄어쓰기를 기준으로 단어 인덱스를 초기화해서 생각합니다. 🙄접근방법 1. 띄어쓰기를 기준으로 단어 인덱스를 초기화해야하니 먼저 " "를 기준으로 split()을 해줘야한다고 생각했습니다. 2. 각 요소의 인덱스를 한번 더 밟아야하니 각 요소마다 for문을 돌려주면서 짝수 인덱스는 대문자로 홀수 인덱스는 소문자로 만들어줘야겠다고 판단했습니다. 한계 결론적으로 for문을 2번 사용하게 되기때문에 시간복잡도가 늘어나는 문제가 있습니다. 이걸 해결할 방법을 모르겠네요.. 🔍나의 풀이 function solution(s) { let strange = s.split(" ") let answe..
programmers
[Programmers Level 2 스택] 올바른 괄호 Javascript
⚡문제정보 스택을 이용하면 쉽게 풀 수 있는 문제입니다. leetcode에서 비슷한 문제를 풀었는데 그것보다 조건이 좀 더 쉽네요! 🙄제한사항 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다. 🔍접근방법 stack을 구현하기 위해 값을 저장해줄 변수를 선언하고 for문을 순회하며 문자열이 '('인 경우 push ')' 인 경우 pop해준다. 🔍나의 풀이 function solution(s){ let stack = [] if(s[0] == ")") return false for(i=0 ; i
