[코드트리 조별과제] 2회차(0722 ~ 0728)

2주 차는 DP에 대해 학습했습니다.

 

저는 DP, 이분탐색/이진탐색과 같이 최적화 관련 유형들을 제대로 풀지 못하기 때문에 이번 기회에 학습해 보려 합니다.

 

우선 DP의 개념에 대해 다시 정리하는 시간을 가졌습니다.

[ Dynamic Programming의 개념]

• DP( Dynamic Programming)
  • 하나의 큰 문제를 여러 개의 작은 문제로 나눠 점진적으로 해결하며 해당 결과를 이용해 기존의 큰 문제를 풀어내는 방법
    • 나눠진 문제는 규모만 작을 뿐 기존의 문제와 동일한 문제
  • 구현 방식
    • Memoization
      • Top-down
      • 재귀를 이용해 큰 수를 작은 수로 쪼갬
    • Tabulation
      • Bottom-up
      • 반복문을 이용해 작은 수에서 큰 수로 늘려감
    • 이론적으로 두 방식의 시간 복잡도는 동일하나, 일반적으로는 Tabulation이 더 빠름
      • Memoization의 구현 형태인 재귀의 특성상, Call stack으로 인한 성능 차이 발생

개념을 정리하면서 Tabulation이라는 단어를 처음 봤습니다. 또한 DP는 Memoization 방식을 사용하고, 이는 배열에 값을 저장해 가져다 쓰는 방식을 지칭하는 것이라고 알고 있었는데 단단히 잘못 알고 있었습니다.

 

[격자 안에서 한 칸씩 전진하는 DP]

https://www.codetree.ai/missions/2/problems/maximum-sum-path-in-square?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1년 전 이맘때쯤의 저와 비교했을 때, 확실히 성장을 했다는 것은 느낍니다. 해당 문제를 학습이 아닌, 코드트리의 평가를 통해 처음 접했었는데, 보자마자 DP 문제인 것을 눈치챘었습니다.

 

하지만 제가 알고 있는 기존의 방식과는 다른 방식의 문제였기 때문에 손을 대지 못했습니다. 어떻게든 풀어보고자 DFS를 이용해 시도를 해봤지만 시간 초과를 경험했었던 문제이기도 합니다. 또한 실제 모기업에서 시행했던 역량테스트에 유사한 문제가 출제되었으나 역시나 풀지 못했습니다.

 

제가 어려워했던 이유는 다음과 같습니다.

1. 기존에 접했던 유형은 1차원 배열을 통해 초기화를 수행하여 규칙을 찾으면 해결되는 문제들
2. 진행 방향이 일관적이고 단일 형태의 초기화가 이루어져야 한다는 고정관념 발생
   • 가로부터 초기화해야 하나? 세로부터 초기화해야 하나? 뭐가 됐든 이상한데?
3. 초기화부터 막혀 풀이 불가능

위와 같은 어려움이 이번에도 발생했지만, 문제를 계속 보다 오른쪽과 밑에 영향을 받는 값들을 우선적으로 처리하는 방법에 접근하게 되었습니다.

 

이때 다행히도 계산에 필요한 값들을 따로따로 초기화하면 될 거 같다는 생각이 들었고 간단하게 슈도 코드를 적어 검증을 한 후 풀이에 들어가게 되었습니다.

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = arr[0][0]

for i in range(1, n):
    dp[0][i] = arr[0][i] + dp[0][i - 1]

for i in range(1, n):
    dp[i][0] = arr[i][0] + dp[i - 1][0]

for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = arr[i][j] + max(dp[i - 1][j], dp[i][j - 1])

print(dp[-1][-1])

1. 문제에서 진행 방향은 고정, 많은 값을 가져가야 값을 최대로 만들기 가능
2. 시작점으로부터 진행방향에 맞춰 각각의 방향에 맞춰 값 누적
3. 문제에 맞출 수 있도록 점화식을 작성해 누적값을 제외한 나머지 값 계산
   • 밑으로 접근할 때 최대인지, 오른쪽에서 접근할 때 최대인지 선택

이번 기회를 통해 다양한 유형의 문제를 접하며 개념을 바로잡고 경험을 쌓을 수 있었습니다.