📑 동적계획법_1463_1로만들기
동적 계획법 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 큰 문제를 푸는 것 F(N)을 구하기 위해서 풀어야 하는 문제의 개수는 O(N)개 이고, 이 답을 모두 저장할 O(N)의 메모리가 필요하며, 각각의 문제를 푸는 데 걸리는 시간이 O(1)이므로 O(N)개의 문제를 푸는 데 O(N)의 시간이 든다. 분할 정복 VS DP 분할정복과의 차이점은 분할정복은 문제를 분할했을 때 생성되는 부분 문제들 중 겹치는 문제가 발생하지 않는다. 하지만 DP는 겹치는 문제가 발생하기 때문에 메모이제이션 기법이 필요하다. EX) 피보나치 -> F(N)[구해야할 문제] = F(N-1) [ 부분 문제 ] + F(N-2) [ 부분 문제 ] Greedy VS DP 모든 경우를 메모리까지 소비해가며..
