동적계획법이란? 큰 문제를 한 번에 해결하기 힘들 때 작은 문제로 나누어 푸는데, 이 때 이전에 계산한 값을 저장해두었다가 다시 사용하는 것이 핵심이다. 큰 문제를 작은 문제로 분할하여 푼다는 점에서 분할정복 알고리즘과 유사하지만, 한 번 계산했던 값은 저장한다는 점에서 (Memoization, 메모이제이션) 분할정복 알고리즘과 다르다. 동적계획법이 필요한 이유 그렇다면 왜 동적계획법이 필요한 것일까? 피보나치 수열을 예를 들어보자면, 점화식은 F(n) = F(n-1) + F(n-2)가 된다. 이는 간단하게 재귀함수만으로 구현할 수 있지만, 비교적 그렇게 어마어마하게 크지 않은 수인 50만 생각해보더라도 50을 구하기 위해서 불필요한 재귀가 일어나게 되어 엄청나게 많은 연산이 요구된다. 위의 그림에서도 ..

문제를 풀기 위한 아이디어 다이나믹 프로그래밍 유형은 점화식을 세우는 것이 가장 중요하다. 이 문제의 점화식은 타일의 개수가 N개일 때 만들 수 있는 N자리수 이진수의 모든 개수를 T(n)이라 하면, T(n) = T(n-2) + T(n-1)이다. 다이나믹 프로그래밍을 푸는 방법에는 Top-down 방식과 Bottom-up 방식이 있는데, 처음에 이문제를 Top-down 방식으로 푸니까 stack이 계속 초과되었다고 나와서 Bottom-up 방식으로 반복문으로 풀었다. 내가 작성한 코드 (자바스크립트) function solution(N) { const memo = new Array(); memo[1] = 1; memo[2] = 2; for (let i = 3; i

문제를 풀기 위한 아이디어 피보나치 수열의 n번째 숫자는 n-2번째 수와 n-1번째 수의 합이 된다. 피보나치 수열을 재귀함수로만 풀 수도 있지만, 이렇게 하게 되면 비교적 작은 수더라도 실행횟수가 어마어마해진다. 예를 들어 fibonacci(5) 함수를 통해 피보나치 수열의 5번째 수를 구하려고 한다면, 아래의 그림과 같다. fibonacci(5) = fibonacci(4) + fibonacci(3) 이기 때문에, fibonacci(4)는 또 재귀를 부르고 fibonacci(3)도 재귀를 부른다. 이렇게 하면 안좋은 점이 2같은 경우에 3번이나 중복되고 있어 연산회수가 불필요하게 많아지고 있다. 5여서 망정이지 50번째 수만 되더라도 재귀를 쓰면 반복횟수는 어마어마해진다. 따라서 이미 구해놓은 값은 저..

let fs = require("fs"); let input = fs.readFileSync("예제.txt").toString().split(" "); const N = Number(input[0]); const K = Number(input[1]); const numbers = new Array(Number(input[0]) + 1); let primeNumber; const count = []; for (let i = 2; i < numbers.length; i++) { numbers[i] = i; } for (let i = 2; i

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제를 풀기 위한 아이디어 이 문제는 결국 현재 시간에서 시작할 수 있는 작업 중에 가장 작업 시간이 짧은 것을 우선적으로 처리하면 된다. 일명 SJF(Shortest Job First) 방식이라고 할 수 있다. SJF 들어본 적은 있는데 이걸 이렇게 접할 줄은 .... 일단 먼저 정렬한다. 정렬하는 순서는 jobs[index]라고 치면 jo..

문제출처: https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 내가 작성한 코드 function solution(tickets) { const answer = []; const DFS = (start, tickets, path) => { const newPath = [...path, start]; if (tickets.length === 0) { answer.push(path);..