목록Algorithm (1)
학습과 기록
Dynamic Programming(DP) 알고리즘
한정된 메모리 공간을 효율적이게 사용하기 위한 방법이다. 즉 최적화 문제를 해결하기 위한 알고리즘이라고 볼 수 있다. - 큰 문제 -> 작은 문제로 나눔 -> 작은 문제를 계산한 결과를 저장 -> 이 결과를 큰 문제 해결에 사용 -> .. - 한 번 계산한 문제는 다시 계산하지 않음. * DP의 사용조건 1. 겹치는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 하는 경우 2. 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있어야하고, 작은 문제의 계산 결과를 큰 문제를 해결하는데에 사용할 수 있어야 한다. DP의 활용을 잘 나타내주는 예제가 바로 피보나치 수열이다. 그렇다면 피보나치 수열 예제를 통해 DP..
Algorithm
2023. 8. 6. 18:06