알고리즘 이론 & 풀이/프로그래머스

프로그래머스 Lv.0 | 저주의 숫자 3

문제 - https://school.programmers.co.kr/learn/courses/30/lessons/120871 풀이 for i는 0부터 n까지 1씩 증가하며 count를 증가시킨다. 만약 증가시킨 수가 3의 배수거나 3을 포함한다면, 그것을 벗어날 때까지 계속 1씩 증가시킨다. 그렇게 n번 숫자를 세면 최종 결과를 반환한다. function solution(n) { let count = 0; for(let i = 0; i < n; i++) { count++; while(count % 3 === 0 || count.toString().includes('3')) count++; } return count; }

프로그래머스 Lv.2 | 괄호 회전하기 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/76502 풀이 x만큼 왼쪽으로 회전한다는 것은 문자열을 0부터 x까지 잘라서, x+1 이후의 문자열의 꽁무니에 붙이는 것과 같다. substring으로 문자열을 양분해서 앞쪽 것을 뒤에 붙여주자. 괄호의 열림, 닫힘 여부는 stack을 사용하고, 괄호의 짝을 확인하기 위해 Map object에 짝을 저장해놓는다. 0부터 x번까지 모든 회전하는 경우의 수를 구해야 하므로 회전은 바깥for문이 담당한다. 본인이 왼쪽 괄호인지는 Map에 key가 존재하는지로 확인하고, 왼쪽 괄호라면 stack에 집어넣는다. 만약 Map에 없다면 오른쪽 괄호이므로 stack에 있던 것을 pop해서 본인의 짝인지 확인해..

프로그래머스 Lv.2 | 피보나치 수 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12945 풀이 n은 2 이상이므로 for문은 2부터 시작한다. 그리고 0과 1에 대한 값을 미리 초기화해놔서 F(2)부터 구해나가는데 문제가 없도록 한다. F(n)에 도달하게 되어 다 구하면 for문이 종료되고 맨 마지막 값이 바로 피보나치 수가 된다. 맨 마지막에 1234567로 나누지 않고 중간중간 나누는 이유는 바로 오버플로우의 위험 때문이다. 피보나치 수는 일정 수준이 되면 수가 매우 커지는데 이때 오버플로우가 발생해 -값으로 변해 의도치 않은 값으로 변해버릴 수 있다. 따라서 중간에 틈틈히 1234567의 나머지로 바꿔주는 것이다. function solution(n) { const f..

프로그래머스 Lv.2 | (스택/큐) 기능개발 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42586?language=javascript 풀이 큐로 풀었다. 기능개발에 걸리는 기간은 Math.ceil((100 - progresses[0]) / speeds[0]) 맨 앞에 있는게 안 나가면 뒤에는 맨 앞 날짜보다 작거나 같은 날짜가 계속 쌓이게 된다. 날짜 배열의 [0]번보다 큰 날짜가 나온다면 그동안의 기능들을 다 배포하게 되는데, 개발한 기능의 개수를 세주고 날짜 배열을 비우고, 새로운 날짜 기준부터 다시 시작한다. function solution(progresses, speeds) { const answer = []; let dates = [Math.ceil((100 - progre..

프로그래머스 Lv.1 | (스택/큐) 같은 숫자는 싫어 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=javascript 풀이 방법 1) 슬라이딩 윈도우 슬라이딩 윈도우 방식으로 풀었다. 본인과 본인 앞자리를 비교하는 방식이다. function solution(arr) { let answer = [arr[0]]; for(let i = 1; i < arr.length; i++) { if(arr[i - 1] !== arr[i]) answer.push(arr[i]); } return answer; } 방법 2) stack 아니면 answer의 맨 마지막 값과 중복되지 않는 새로운 수를 만나면 배열에 push하는 방식으로 풀 수도 있다. function solution(arr)..

프로그래머스 Lv.2 | (DFS) 타겟 넘버 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43165 풀이 모든 가능한 조합을 시도해봐야 한다. numbers 배열의 숫자를 순서대로 + 혹은 -를 해봐야 한다. 마치 각 숫자 노드에 다음 숫자가 +, - 두 가지 버전으로 달려있는 이진트리를 모두 순회하는 경우와 같다. 깊이 우선 탐색(DFS) 이므로 dfs라고 함수를 만들고, 다음 인덱스로 넘어가기 위한 index, 합을 축적할 currSum을 마련한다. 인덱스와 sum은 0부터 시작하므로 처음에는 dfs(0, 0)로 시작한다. dfs의 종료 조건은 index가 numbers.length가 될 때 (배열의 인덱스 범위보다 넘쳤을 때)이다. 이때는 여태가지 축적한 sum이 target과 ..

프로그래머스 Lv.1 | (완전탐색) 모의고사 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42840?language=javascript 풀이 수포자가 찍는 패턴 - 12345 / 21232425 / 3311224455 answers와 수포자의 답을 비교하기 위해 각 수포자의 답을 문자열로 준비한다. 크게는 pattern이 answers에 몇 번 들어가는지 몫만큼 반복되고, pattern이 짤려서 붙는 경우를 위해 나머지 개수만큼을 덧붙여준다. (repeat과 substr 사용) 답이 일치하는 횟수를 세기 위해 [0, 0, 0]으로 초기화한 count 변수를 준비한다. 수포자의 답을 순회하며 answers와 답을 비교하며 만약 같다면 count[index]에 +1을 해준다. count ..

프로그래머스 Lv.2 | (완전탐색) 소수찾기 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=javascript 풀이 DFS 방식으로 재귀함수를 이용해 풀음. 다만 반복문에서 같은 수를 선택하지 않기 위해 visited를 두고 관리해 백트래킹함 조합을 구하다보면 중복되는 조합이 생길텐데 어떻게 해결하냐 -> 조합한 결과를 Set()에 add한다. '11'과 '011' 처럼 앞에 0이 붙을텐데 어떻게 처리할거냐 -> Number('011')을 하면 숫자 11로 변한다. 소수 판별은 아예 isPrime()이라는 함수를 만들어 true/false를 반환하게 한다. 모든 가능한 조합을 만들어봐야 한다. 본인을 제외한 문자열을 점층적으로 더하도록 재귀함수를 짠다. 맨 처..