꼬비.com

최근에 2022.10.30 - [알고리즘/문제풀이] - 백준 문제풀이할 목록 에 있는 문제를 풀고 있는데 중요도가 높다고 생각되는 dp 문제를 풀면서 만났던 유형들을 정리해보았다. (아직 많은 문제를 풀어본 것이 아니라서 모든 dp 문제 풀이 유형을 정리한건 아니다.) 1. 단순한 점화식 사용 dp[i] = dp[i - 1] + dp[i - 2]; dp[i] = dp[i - 1] + n * dp[i - 2]; [1로 만들기](https://www.acmicpc.net/problem/1463) [2×n 타일링](https://www.acmicpc.net/problem/11726) [2×n 타일링 2](https://www.acmicpc.net/problem/11727) [1, 2, 3 더하기](https:..

1. 개요 동적 계획법 ( Dynamic Programming, 줄여서 DP ) 은 프로그래밍 대회에서 출제되지 않으면 이상할 정도로 높은 출제빈도를 보이고 있을 만큼 중요한 알고리즘 설계 기법입니다. 동적 계획법은 주어진 문제를 여러 개의 하위문제들로 나누어 먼저 처리한 후 그 답들을 이용해 문제를 처리하는 방법을 뜻합니다. 하위문제들을 수행할 시에는 같은 문제를 여러 번 처리하는 경우가 발생하는데 이 때, 한번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도가 비약적으로 빨라지게 할 수 있습니다. 2. DP 기본 예제 – 피보나치 수열 피보나치 수열은 F[0] = 0, F[1] = 1, F[i] = F[i-1] + F[i-2] ( i > 1 ) 을 만족하는 수열인데 ..