[codeplus 코드플러스] 백준 알고리즘 강의 기초 3강- 다이나믹 프로그래밍

알고리즘 강의를 듣다 보면 아무래도 기초 강의다 보니 학부 수업시간에 배운 내용이기도 하고, 혼자 알고리즘 문제를 풀면서 배운 것들이 많다. 그래도 처음 공부한다는 마음으로 공부하고 있는데 나름 정리가 되는 것 같아서 뿌듯하다.

오늘은 알고리즘 대회에서 꾸준히 출제되고 있는 다이나믹 프로그래밍이다.

 

다이내믹 프로그래밍이란?

 

큰 문제를 작은 문제로 푸는 알고리즘으로 다이내믹이라는 명칭은 알고리즘과 아무런 관련이 없다.(개발자가 그냥 멋있어 보여서.. 사용한 것이라고)

 

문제 해결 조건

 

큰 문제를 작은 문제로 쪼개서 풀 수 있고, 큰 문제를 작은문제와 같은 방법으로 풀 수 있으며, 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 사용 가능 한 방법이다.

ex) 피보나치수, 조합 등등

 

문제 해결 방법

 

- top down

1. 문제를 작은 문제로 나눔 

2. 작은 문제를 품

3. 나누어진 작은 문제를 합쳐서 큰 문제를 품

->재귀 호출로 쉽게 풀 수 있고, memoization을 사용한다.

 

- bottom up

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

2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 풀어나간다.

3. 큰 문제는 결국 작은 문제들로 이뤄졌기 때문에 큰 문제는 항상 풀 수 있다.

 

문제 풀이 전략

 

1. 문제에서 구하려고 하는 답을 문장으로 나타낸다.

2. 문장에 나온 변수의 개수만큼 메모하는 배열을 만든다.

3. 문제를 작은 문제로 나누고, 수식을 사용해서 문제를 표현한다.

 

 

dp에 대해서 풀어볼 문제

 

1463번(https://www.acmicpc.net/problem/1463)

1463번: 1로 만들기

- n번째 인덱스가 3으로 나눠떨어질때, 2로 나눠 떨어질 때, 둘 다 아닐 때로 나눈다.

- 점화식 dp[i] = min(dp[i-1],dp[i/3],dp[i/2])+1

 

11726번(https://www.acmicpc.net/problem/11726)

11726번: 2×n 타일링

- 작은 문제로 나눠서 생각해보자

- 점화식 dp[i]=dp[i-2]+dp[i-1]

 

11727번(https://www.acmicpc.net/problem/11727)

11727번: 2×n 타일링 2

- 2*n 타일링 문제와 매우 유사하다. 그대로 풀면된다.

- dp[i]=dp[i-2]*2+dp[i-1]

 

9095번(https://www.acmicpc.net/problem/9095)

9095번: 1, 2, 3 더하기

- 전형적인 dp문제

- 입력이 a,b,c라고 할 때, 점화식 dp[i]= min(dp[i-a],dp[i-b],dp[i-c])+1