이 글들은 백준 온라인 저지의 백준님이 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
'공부 > 백준 2020년 1~2월 알고리즘' 카테고리의 다른 글
5번째 수업 (0) | 2020.01.22 |
---|---|
4번째 수업 (0) | 2020.01.19 |
3번째 수업 (0) | 2020.01.15 |
1번째 수업 복습 (0) | 2020.01.08 |
1번째 수업 (0) | 2019.12.31 |