Hyun's_Devlog

https://www.acmicpc.net/problem/17208

동적계획법으로 접근한 문제다.

풀이 방법

2차원 배열 dp를 생성. x열은 소유하고 있는 버거를, y행은 소유하고 있는 감자튀김이다.

따라서 dp[x][y]는 버거 x개와 감자튀김 y개를 가지고 있을 경우 받을 수 있는 최대 주문의 수를 의미한다.

M행 K열의 2차원배열을 생성해야 하는데, 인덱스로 접근하기 편하게 dp[M+1][K+1] 배열로 선언하였다.

입력된 주문이 버거 M개 혹은 감자튀김 K개를 초과한다면 해당 주문은 탐색할 필요가 없다.

dp[M][K]부터 dp[0][0]까지 역순으로 탐색하여 (동일 주문은 하나만 받을 수 있다.)

주문을 받지 않고 남아있는 음식을 아낄 것인지 (dp[x][y]) 혹은

해당 주문을 받을 것인지 (dp[x-현재 주문의 버거 개수][k-현재 주문의 감자튀김 개수]+1)

둘 중 더 큰 값을 선택하여 현재 탐색 중인 곳을 갱신하면 된다.

따라서 현재 보유 중인 버거가 x개, 감자튀김이 y개이며 현재 요청된 주문의 버거 개수가 dx, 감자튀김의 개수가 dy일 경우, 점화식은 다음과 같다.

dp[x][y] = max(dp[x-order.dx][y-order.dy]+1,dp[x][y])

정답 코드

https://www.acmicpc.net/problem/2533

동적 계획법 문제다.

풀이

동적 계획법을 기본으로 그래프탐색을 통해 접근해야 한다. 부모 노드가 얼리어답터라면 자식노드는 얼리어답터 여부와 상관없이 해당 부분의 부모와 자식에게는 아이디어 전파가 가능하다. 반대로 부모가 얼리어답터가 아니라면 자식은 반드시 얼리어답터 이어야 한다. 

두 개의 자식을 가진 부모노드가 얼리어답터가 경우 아이디어가 전파되려면 그림과 같은 4개의 경우의 수가 만들어진다. 해당 부분에서의 정답은 가장 첫 번째의 경우가 최소조건임을 알 수 있다. 

하지만 반대로 부모가 얼리어답터가 아닐 경우, 자식들은 모두 얼리어답터 이어야만 조건이 맞다. 즉 우리는 부모노드가 얼리어답터인지, 일반인인지의 경우를 따져 얼리어답터의 수를 계산할 수 있게 된다.

그래프는 다음과 같이 두 개의 값을 가지는 형태로 구현한다. 0번 인덱스에는 자신이 일반인일 경우 얼리어답터의 수, 1번 인덱스에는 자신이 얼리어답터일 경우 얼리어답터의 수. 처음에는 당연히 자기 자신만 얼리어답터인 경우로 1로 초기화되어 있다.

먼저 부모가 얼리어답터가 아닐 경우부터 살펴본다. 해당경우는 자식노드가 무조건 얼리어답터이어야 하기 때문에 자식의 수만큼 더해진 값이 얼리어답터의 최소 개수다.

하지만 부모가 얼리어답터인 경우, 자식이 얼리어답터의 여부와 상관없이 최솟값을 가져오면 조건이 성립된다.

parent[0] += child_0[1] + child_1[1]...child_N[1]
parent[1] += min(child_0[0],child_0[1]) + ... min(child_N[0],child_N[1]))

즉 모든 노드가 [0,1] 형태로 초기화되어있을 경우, 해당 점화식을 사용하여 리프 노드의 정보를 통해 루트 노드까지 최소 얼리어답터의 수를 구할 수 있게 된다.

예제의 경우 다음과 같은 형태로 결과가 나오며, 출력은 루트노드의 두 개의 값 중 최솟값을 출력하면 된다. 코드로 보는 것이 이해하기 더 쉽다.

정답 코드

https://www.acmicpc.net/problem/11054

동적계획법으로 접근 가능한 문제다.

풀이

크기 A인 두 개의 dp 배열을 만든다. 하나는 0부터 해당 인덱스까지 증가하는 부분수열의 최대 개수, 다른 하나는 A-1번부터 해당 인덱스까지 감소하는 부분수열의 최대개수를 담아내어 ans배열에 두 배열의 값을 합쳐서 최댓값을 계산하면 된다.

i는 0부터 A까지, 즉 구하고자 하는 대상의 인덱스, k는 0부터 i까지 즉 처음부터 자기 앞번호까지의 원소를 순회할 때 점화식은 다음과 같다.

if arr[k] < arr[i] 
dp[i] = max(dp[i], dp[k]+1)

즉 자신보다 작은 원소로 끝나는 증가하는 부분 수열에 원소 i를 붙이기만 하면 해당 원소로 끝나는 증가 부분 수열이 완성되기에 해당 조건 내에서 최댓값으로 갱신하면 답을 구할 수 있는 것이다. 예제를 기준으로 구한 dp 배열은 다음과 같다.

감소하는 부분수열의 경우는 해당 배열을 역순으로 탐색하면 구할 수 있다. 주의할 점은 증가하는 부분수열의 개수에서 자기 자신을 포함하여 계산했기에 1로 초기화했으나 감소하는 부분수열은 자기 자신을 포함하지 않은 0으로 초기화해야 중복을 피할 수 있다. 

마지막에는 해당 배열의 총합을 더하여 최댓값을 출력해 주면 된다.

정답 코드

https://www.acmicpc.net/problem/2056

위상정렬과 동적계획법으로 접근가능한 문제다.

풀이법

처음에는 단순히 위상정렬을 통해 큐에 접근할 때마다 가장 오래 걸린 작업시간들을 더하면 될 것이라 생각했다. 하지만 해당방법은 틀린 방법이 다.

후속이 없는 작업의 경우, 다음 탐색에  영향을 끼치지 않아야 하는데, 처음생각한 방법은 이러한 부분을 제외시키지 못했다. 따라서 해당 작업을 완료하는데 걸리는 총시간을 담은 dp 배열을 생성한 뒤, 동적계획법으로 접근해야 한다. next는 다음 작업, curr는 현재작업을 의미할 때, 점화식은 다음과 같다. 여기서 time배열은 순수 작업시간을 의미한다.

dp[next] = max(dp[next], dp[curr]+time[next])

위상정렬을 통한 그래프탐색 이후, dp배열의 최댓값을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/2096

처음엔 그래프 탐색으로 접근했지만, DP로 해결한 문제다.

풀이

최대 점수를 담는 3칸 크기 배열과 최소 점수를 담는 3칸 크기 배열을 생성한 뒤 매 입력마다 최대, 최소 점수를 누적해 나가면 된다.

단, 갱신되는 주체가 무엇인지를 잘 생각해야한다. 예제를 기준으로 표를 그려봤다.

첫 입력은 당연히 그대로 입력받고 두번째 입력부터 비교를 시작한다. 현재 입력값 기준으로 이전 입력값들의 비교를 통해서 값을 경신해야 한다. 본인은 아무 생각 없이 이전 배열을 기준으로 새로 입력받은 값을 경신해서 오답을 받았다.

마지막 결과인 [12 18 19] 배열 중 가장 큰값이 최댓값이 된다. 최솟값은 반대로 최솟값들로 연상하여 갱신하면 된다.

정답 코드

https://www.acmicpc.net/problem/1915

dp문제다. 완전 탐색으로 시도했지만 역시나 시간 초과. 점화식을 생각해내는 데에 시간이 걸렸던 문제다.

풀이

최소한의 정사각형을 만들 수 있는 칸부터 시작해야 한다. 2차원 배열 map에 대해서 x와 y의 값이 모두 1 이상이고 map[x][y]의 값이 0보다 커야 한다. 해당 좌표의 상, 좌, 좌대각선 칸 중 최솟값 + 1로 갱신해나가면 된다.

map[x][y] = min(min(map[x-1][y], map[x][y-1]), map[x-1][y-1]) + 1

정답 코드

https://www.acmicpc.net/problem/2011

답이 생각나지 않아 점화식을 찾아보고 코드를 적어봤는데, 풀이를 이해하고서도 예외처리를 제대로 하지 못해서 오답 판정을 받았다. 결국 코드까지 찾아보고 난 후에야 풀 수 있었던 문제. 역시나 DP문제는 다양한 시점으로 생각하는 연습이 필요한 것 같다.

풀이

암호화된 문자의 길이가 n일 경우, dp:[Int] 배열은 총 n개의 배열로 dp[i]는 0번째 숫자부터 i번째 숫자까지로 만들수 있는 암호의 갯수가 담긴 배열이다. 입력된 암호문구를 순회하면서 현재 숫자가 0보다 크다면 dp[i-1]번째 경우의 수를 이어가면 되고, 추가로 직전 숫자가 0보다 크다면 현재 숫자와 합쳐 두 자리수의 대체 가능한 알파벳을 만들수 있다면 dp[i-2]번째 경우의 수를 추가로 이어가면된다. 즉 점화식은 아래와 같다.

현재 암호가 0보다 크다면,
dp[i] += dp[i-1]
추가로 직전 암호가 0보다 커서 현재 암호와 이어 붙였을 시 10 이상 26 이하라면,
dp[i] += dp[i-2]

점화식을 알았을 때는 간단하게 풀면 되겠다 싶었는데, 문제는 중간에 나오는 0에 대한 처리 부분이었다. 처음에는 중간에 flag 변수를 만들어 분기 처리를 하였는데, 생각보다 처리해야 할 경우가 많아서 오답처리를 받았다. 다른 유형의 문제들은 많은 문제를 풀면서 패턴에 적응해가는 과정을 통해 성장해가는 게 느껴지는 반면, DP문제는 다양한 시각에서 문제를 바라봐야 한다는 점이 여러모로 어렵게 느껴진다. 풀이는 해당 블로그에서 찾았다. 이해하기 쉽게 풀이에 대한 이미지도 있다.

정답 코드