백준 알고리즘 강의 후기(코드플러스): 고급으로1 - 다이나믹 프로그래밍4 (DP4)
● 1320 - 다이나믹 프로그래밍 4
강의: DP4-1
1. 비트마스크 + 다이나믹
2. 행렬 + 다이나믹
에 대해서 배우겠습니다.
백준 2133 타일채우기
타일채우기 ( 비트마스크 다이나믹 알아보기 )
기준은 열로 하겠다.
열마다 2^3 경우의 수 가능. 왜냐하면 3xn 이기 때문이다.
열기준으로 1부터 ...n까지 채우겠다.
0~7까지 상태 중, 그 앞에 올수있는 상태 찾기. 상태는 사실비트마스크다. 000, 001, 010 이런식.
3xi를 채운다는것.
i열은 빈칸이 있어도 되지만, 1~ i-1 열은 빈칸이 없어야 한다.
점화식 만들고, 정답은 D[N][7] 에 있다.
백준 2098 외판원 순회
타일구하기는 모든 상태를 다 만들어보고 이전식을 구했다. 그건 2^3이라서 가능했지만, 이건 2^16이라서 그렇게 하는건 불가능함.
한 도시에서 출발해서 N개의 도시를 거쳐 다시 원래 도시로 돌아오는 순회경로의 최소값 구하기
W[i][j]는 i->j 비용
총 방법의 수는 N! 인데 그걸 다하려면 N을 곱해야되서 N!XN 그래서 N<=10 일때만 가능하다.
* 시작을 1로 고정해본다.
1->2->3, 2->3->1의 비용이 같기때문이다.
* 부분 최소비용
1->2->3->4와 1->3->2->4중 비용이 작은것 하나만 있으면 되고, 큰것은 더 해볼필요가 없다.
1->4->2->3 과 위에거를 비교한다고 해서 알수가없다.
즉, 마지막도시와 이제까지 방문한도시의 비용의 합을 알아야 한다.
D[S][i] = 도시를 방문한 상태가 S이고, 현재 있는 위치가 i일때 최소값
0->.,....->i->j라고 해보자.
상태: S에서 i를 뺌, 비트마스크로는 S - (1<< i) 이것을 좀 더 올바르게 쓴다면 s&~(1 << i)
D[S-(1<<i)][j] + W[j][i]
조건1 i는 S에 포함
s&(1 << i) != 0
조건 2 j 는 s에 포함
s&(1 << j) != 0
시간복잡도 : s에 대해서는 전체 (2^N x N)이 가능, 여기에 i를 반영해주면 N이니, (2^N X N) X N = 즉 O(2^N X N^2)
두번째 방법
0->,,,->i까지 왔고, 이제 j를 가는것
상태 : S | ( 1<<j)
D[s|(1<<j)][j] = min(D[s][i] + W[i][j])
위의 두 소스코드는 모두 비슷하고 점화식 구하는 부분이 가장 어려움
타일과 외판원은 큰 차이가 있다, 타일은 가장 기초고 외판원은 조금 더 어려운 문제였다.
강의: DP4-2
백준 1562 계단 수
0~9가 등장한다, 등장하지 않는다 니까 비트마스크 사용가능
등장했다가 등장안했다가 하는게 아니고, 한번 등장하면 계속 등장하기 때문에 비트마스크 사용가능
쉬운 계단수 문제
앞뒤 차이가 1인 계단 만들기
다른 풀이도 존재: 상태가 꼭 비트마스크일 필요는 없다.
상태다이나믹을 이용하는 문제의 정의를 확실히 알아야 한다.
백준 1014 컨닝
cnt 학생의 수를 세어줌
강의: DP4-3
백준 1684 격자판 채우기
앞에는 3xN 인데, 여기는 NXM
비트다이나믹은 2가지스타일로 나뉘어지는데
1. 앞에서 봤던 스타일이랑
2. 격자판 스타일로 나뉜다.
3xN에서는 열을 기준으로 앞에 올수 있는 열을 찾아줬고,
컨닝문제는 행기준으로 했는데,
격자판은 Ni행에 올수있는 상태가 j고 i-1행에 있는 상태k를 찾을 경우, 시간복잡도는 컨닝과 같이 NX2^2M -> 14X2^18하면 너무커서
좀더 적은 복잡도인 NMX2^M으로 해야함
다음강의에서..
상태다이나믹
1칸을 채울지 말지 결정하면서 다이나믹을 진행.
상태를 어떻게 기록하냐?
D[num][s] = num번 칸을 채울것이고, num번 칸부터 M개의 상태가 s일 때, 경우의 수
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
0은빈칸 1은 도미노가 이미 있음
4방향 고려하지 않고, 오른쪽이랑 아랫쪽으로 확장하는 영역만 처리할 것이다.
백준 14389 4블록
-1과 -2를 이용하여 4블록을 검사한다. 와우!
강의: DP4-4
백준 12960 체스판
타일을 놓을수 없는 칸이 입력으로 주어진다.
격자판과 비슷하지만, 놓을수있는 모양이 다르기 때문에 주위의 어떤칸이 비어있는지 알아본다.
백준 14390 타일 놓기
가로를 놓을지 세로를 놓을지 정하는것이고, 스테이트는 현재까지의 타일 개수.
가로를 놓는다는것은 새로운 타일이라는 뜻이다. 세로인 타일은 위에서 내려왔다는 뜻이기 때문이다.
행렬과 다이나믹
가장유명한것: 피보나치수열
백준 13976 타일 채우기 2
행렬을 사용하는 다이나믹 응용
백준 14440 정수 수열
그냥 구해주면 되는데 N제한이 너무 커서 행렬의 표현으로 변환해준다.
피보나치와 같은 원리로 할수있다.
주기 찾는 문제라고도 볼수있다.
● 1321 - 다이나믹 프로그래밍 4 (연습)
강의: 연습1
발전소
007
타일 채우기
강의: 연습2
체스로 도미노를 타자
박성원
소수 만들기
네 부분문자열
강의: 연습3
두부장수 장홍준
동민 수열
체스판 이동
팀 연습
강의: 연습4
팀 연습 더
직사각형 색칠 2
나이트
● 1322 - 다이나믹 프로그래밍 4 (도전)
강의: 도전
다이어그램과 태블로
직사각형 색칠
도로 건설
백준 알고리즘 강의 후기(코드플러스): 기초1 - 다이나믹 프로그래밍1 (DP1)
백준 알고리즘 강의 후기(코드플러스): 중급2 - 다이나믹 프로그래밍2 (DP2)
백준 알고리즘 강의 후기(코드플러스): 중급3 - 다이나믹 프로그래밍3 (DP3)
-
