(7/31) 6일차 - IOI 출제동향(동적계획법 최적화) 문제

IOI 출제동향이라고 템플릿에 적혀있었지만 코치장님께서 LIS, LCS 등 대표적인 동적계획법의 활용과 최적화 방법에 대해 가르쳐 주셨습니다. 문제는 총 13문제였습니다.

https://bas.ioikorea.cc/problems/list

2022 여름학교 처음반

1. 최대 부분 합     O

간단히 DP[i] = max(DP[i-1]+a[i], a[i])라는 식으로 DP식을 세워줄 수 있습니다.

 

2. 계단 오르기     O

가장 유명하고 기본적인 DP문제 중 하나입니다. 탑다운과 바텀업 방식 둘다 가능하지만 저는 바텀업 방식을 사용했습니다. i를 1부터 N까지 증가시키면서 dp[i+1], dp[i+2], dp[i+3]에 dp[i]값을 더해주는 방식으로 구현하였습니다.

 

3. 최장 공통 부분열    O

LCS 입니다. O(N*M)의 풀이가 가장 잘 알려져 있으며 N*M의 2차원 DP로 구현했습니다. i와 j에 대해 같은 문자라면 DP[i][j] = DP[i-1][j-1]+1 이고 다른 문자라면 DP[i]j[j] = max(DP[i-1][j], DP[i][j-1])입니다.

최종적으로 DP[N][M]에 담기는 값이 최장 공통 부분열의 길이이며 최장 공통 부분열을 찾기 위해서는 역추적 과정을 거쳐야 합니다. 

역추적은 (N, M)에서 출발하여 (N-1, M) , (N, M-1) 중 동일한 값을 가지고 있는 쪽으로 이동하고 둘다 다른 값을 가진다면 i와 j가 가리키는 문자를 vector에 push해주고 (N-1, M-1)로 이동합니다.

역추적이 종료된 이후 vector를 reverse해서 출력해주면 최장 공통 부분열을 출력할 수 있습니다.

 

4. 최장 증가 부분 수열    O

LIS 문제입니다. N <= 100,000이기 때문에 O(N logN) LIS를 구현해주어야 합니다. lis와 ans라는 배열을 만들어서 이전보다 값이 커졌다면 이어서 삽입해주고 아니라면 이진탐색으로 적절한 위치를 찾아 lis에 넣어주었습니다. 동시에 ans에는 i가 lis배열에서 몇번째 인덱스에 들어갔는지를 넣어주었습니다. 최종적으로 만들어진 lis배열의 길이가 최장 증가 부분 수열의 길이이며 ans배열을 뒤에서부터 탐색하면서 ans[i] == cur 를 만족해주는 값을 찾아 재구성해주면 됩니다.

 

5. 행렬 곱    O

N*N짜리 2차원 DP를 구현해주어야 합니다. i가 1~N까지 갈때 j가 1~i-1까지 이동하고 k가 j~j+i까지 이동하면서 DP[j][j+1] = (DP[j][j+1], DP[j][k]+DP[k+1][j+i]+a[j]*a[k+1]*a[j+i+1])이라는 DP식을 짤수 있습니다. 이 식이 의미하는 바는 기존값과 j~k까지의 행렬곱과 k+1~j+i까지의 행렬곱을 곱했을 때의 값을 비교해주는 연산입니다.

 

6. 괄호 ㄴㄴ문자열    X

3차원 DP[i][j][k]를 만들어주어야 합니다. 각각 (i : 현재 인덱스값, j : 괄호문자열의 합, k: 올바른 괄호 문자열인지 여부)

아직 해결하지 못함. 작성중

 

7. Bitonic Tour    X

i -> n -> i로 가는 경로
dp[i][j] (i > j) : i+1을 가는 경로에 넣는다면 +(i, i+1) -(i, n) +(i+1, n)

아직 해결하지 못함. 작성중

 

8. 마스크    X

최종적으로 0-1 Knapsack Problem의 형태로 변환해주어야 합니다.

아직 해결하지 못함. 작성중

 

9. 최장 공통 부분열 2    X

LIS 2번째 알고리즘을 사용하여 O(N*M) --> O(min(N*M)^2) 의 형태로 바꿔주는 문제입니다.

dp[i][j] --> s[1...i], T[1...k] 의 LCS 길이가 j가 되는 최소의 k

dp[i][j] --> min(dp[i-1][j], T에서 dp[i-1][j-1] 보다 뒤에 등장하는 s[i] 문자의 위치) 의 형태로 변형해주어야 합니다.

아직 해결하지 못함. 작성중

 

10. Distributing Candles     X

아직 해결하지 못함. 작성중

 

11. Fountain Parks    X

d번째 날의 차단봉의 상태만 알면 되지 않을까
dp[i][j] --> d-1일 동안 i, j를 방문한 횟수
i, j를 방문 --> i, j-1을 방문했을 때 y축으로 차단기 설치 or i-1, j를 방문했을 때 x축으로 차단기 설치

아직 해결하지 못함. 작성중

 

12. Dungeons Game    X

아직 해결하지 못함. 작성중

 

13. 미술 시간    X

아직 해결하지 못함. 작성중