BOJ 백준 코드플러스 알고리즘 기초 - 다이나믹 프로그래밍1

다이나믹 프로그래밍 개념과 풀이 방법을 익히자.

부끄럽지만 학과 알고리즘 수업 때 dp 관련 문제들은 정말 이해가 안가서 dp관련 문제들은 과제도 제출 못하고 시험 문제도 못 푼 기억이 있다. 알고리즘에서 중요한 부분을 차지하는 만큼 열심히 공부해서 익히자!

 

 

---

 

 

두 가지 속성을 만족해야 다이나믹 프로그래밍을 문제를 풀 수 있다.

1. Overlapping Subproblem : 겹치는 부분 문제

2. Optimal Substructure : 최적 부분 구조

 

 

각 부분 문제는 한 번만 풀어야 한다.

Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.

따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모(배열에 저장)해놓는다. (Memoization)

 

 

 

구현 방법

구현 방법은 두 가지가 있다.

 

1. Top-down - 재귀

1) 큰 문제를 작은 문제로 나눈다.

2) 작은 문제를 푼다

3) 작은 문제를 풀었으니, 이제 큰 문제를 푼다.

2. Bottom-up - 반복

1. 문제를 크기가 작은 문제부터 차례대로 푼다.

2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.

4. 반복하다 보면 가장 큰 문제를 풀 수 있다.

top-down과 bottom-up의 시간차이는 알 수 없다.

 

* python - 코드를 제대로 짜도 Top-down 방식에서 stack overflow가 발생할 수 있으므로 웬만하면 Bottom-up 방식 사용하기
* java, c - stack overflow가 나는 경우는 코드를 잘못 짠 경우밖에 없음. top-down, bottom-up 아무거나 선택해서 짜기.

 

나는 python을 사용하므로 bottom-up을 완벽히 익히도록 하겠다.

 

 

---

 

 

 

이제 문제를 풀어보자.

dp 문제를 풀 때에는 점화식과 초기값을 설정하고, 코드를 짜자.

 

BOJ 코드플러스 알고리즘 기초 강의에 달려있는 문제들을 차례대로 풀 것이다.

문제와 문제풀이는 다른 글로 다뤄야겠다.