2번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.

---

● 다이나믹 프로그래밍

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

 

두가지 특성을 만족해야 다이나믹 프로그래밍으로 풀 수 있다.

1. Overlapping Subproblem

- 문제를 작은 문제로 쪼갤 수 있고, 큰문제와 작은 문제를 같은 방법으로 풀 수 있다.

2. Optimal Substructure

- 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

 

각 문제를 한 번만 푼다.

정답을 한 번 구했으면, 메모를 해놓는다 = Memoization

 

● 구현방식

- 구현방식에는 두가지가 있다.

1. Top-Down

- 재귀호출을 이용

2. Bottom-Up

- 반복문을 이용

 

● 문제풀이 전략

- 문제에서 구하려고 하는 답을 점화식으로 나타낸다.

- 점화식을 먼저 세워라.

- 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현해야 한다.(=점화식)

 

▲ 문제풀이

 

1로 만들기

- D[i] = i를 1로 만드는데 필요한 최소 연산 횟수

- D[N] = min( D[N/3] + 1, D[n/2] + 1, D[N-1] + 1) = min(  D[N/3], D[n/2], D[N-1] ) + 1

- 초기값 설정 : D[1]=0

- 시간복잡도 : 문제의 개수(배열의 크기) * 문제 1개 푸는 시간 = N * O(1) = O(N)

 

2 × n 타일링

- D[n] = 2xn 직사각형을 채우는 방법의 수

- 가장 오른쪽에 타일을 놓을 수 있는 방법은 2가지

- 1. 세로로 하나 : D[n-1] (직사각형을 채우는 방법의 수)

- 2. 가로로 두개 : D[n-2]

- D[n] = D[n-1] + D[n-2];

 

1, 2, 3 더하기

- D[n] = n을 1, 2, 3의 합으로 나타내는 방법의 수

- ○+○+...+○+○ = n 일때, 합 = n-1 + 1 = n-2 + 2 = n-3 + 3

- D[n] = D[n-1] + D[n-2] + D[n-3]

- 초기값. D[1]=1, D[2]=2, D[3]=4

 

카드 구매하기

- D[N] = 카드 N개를 구매하는 비용의 최대값

- ○, ○, ○, ○ = N , 주목할 부분은 마지막 카드팩. 몇장이 들어있을까?

- N = 카드 N-1장 + 1장
     = 카드 N-2장 + 2장
     = 카드 N-3장 + 3장
     = ...................N장

- j장이 들어있다고 가정, 앞에서 구매해야 하는 카드는 N-j장. N-j장을 최대 비용으로 잘 구매 + j장 카드 구매 = N장

- 점화식 : D[N] = max(D[N-j] + P[j])

 

1, 2, 3 더하기 5

- 같은 수를 연속해서 사용하면 안됨

- D[i][j] = i를 1, 2, 3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j

- D[i][1] = D[i-1][2] + D[i-1][3], D[i][2] = D[i-2][1] + D[i-2][3]

 

쉬운 계단 수

- 인접한 자리의 차가 1이 나는 수 = 계단수

- D[N] = 길이가 N인 계단수

- 0이오면 앞에 올 수 있는 수는 1  ,,  1이오면 앞에 올 수 있는 수는 2, 0

- D[N][L] = 길이가 N인 계단수 & 마지막 수 L

- D[N][L] = D[N-1][L-1] + D[N-1][L+1]  (1 ≤ L ≤ 8) 
            = D[N-1][L+1]  (L=0)
            = D[N-1][L-1]   (L=9)

 

이친수

- D[N][L] = 길이가 N인 이친수, 마지막수 L
- D[N][0] = 길이가 N인 이친수, 마지막수 0

- N-1에 올 수 있는 수. 0, 1

- D[N][0] = D[N-1][0] + D[N-1][1]
- D[N][1] = D[N-1][0]

- D[1][0] = 0 (올바른 이친수가 아님), D[1][1] = 1