이쿼카

I am an amazing Quokka.

4 minute read

Baekjoon 사이트에서 단계별로 문제를 풀다가 동적계획법(Dynamic Programming) 문제를 풀다가 동적계획법 알고리즘에 대한 공부와 정리를 위해 포스트를 작성해야겠다고 생각하여 본 포스트를 작성하게 되었습니다. 동적계획법 문제는 수학적 사고력이 많이 필요한데 저는 그게 부족한지라 이런 문제를 잘 풀려면 결국 많은 문제를 풀어보고 해법을 겪어 보는 수 밖에 없는 것 같았습니다. 그리고 문제를 풀 때에는 풀이나 정답 코드를 봤을 때에는 이렇게 풀면 되겠네 하지만 조금만 시간이 지나도 어떻게 풀었는지 기억이 잘 안나곤 해서 이렇게 포스트로 정리라도 해보자고 생각해서 포스트로 정리하게 되었습니다.

1. 문제 소개

Baekjoon 사이트의 정책상 문제의 저작권은 문제를 만든 사람에게 있다고 합니다. 그래도 블로그에 문제와 관련해서 링크로 넣는 것은 상관 없다고 하여 문제 내용은 링크로 대체하겠습니다. 자세한 문제 내용은 링크를 통해 사이트를 방문하여 확인해 주시길 바랍니다.

1912

2. 문제 풀이

이 문제는 동적계획법을 이용해 푸는 문제입니다. 저는 이전에 학생 때 이론적으로만 배우고, 실제 구현은 많이 해보지 않았고, 많이 접해보지 않아 동적계획법 문제에 많이 약합니다. 그래서 해당 문제를 풀어보려고 했으나 풀지 못했습니다. 그래도 다음에라도 풀기 위해 정답 풀이를 봤고, 제가 이해한 정답 풀이 내용을 작성하였습니다.

풀이 내용

이 문제를 풀기 위한 핵심은 다음과 같습니다.

  • 동적계획법으로 풀 수 있는지 없는지 알아야 함.
  • 점화식 조건을 정할 때 어느 경우에 DP 배열에 값을 넣을 건지를 잘 고려해야 함

사실 DP 문제를 많이 풀어보시고 잘 푸시는 분들에게는 당연한 얘기일 겁니다. 그래도 저 같이 DP 문제에 약한 사람의 경우 저 두 가지를 잘 고려해야 합니다. 특히나 점화식을 세울줄 아느냐 모르느냐에 따라 문제를 풀 수 있느냐 없느냐로 정해진다고 생각합니다.

그럼 이 문제의 점화식을 세울 때 핵심적인 조건에 대해서 알아보도록 하겠습니다. 우선 문제에서 주어진 예제에서는 ‘12+21’이 가장 큰 연속합이 된다고 합니다. 즉, 이 말은 특정 조건을 성립하면 이전의 계산 결과값들을 이용하지 않아도 된다는 것입니다. 그렇다면 그 특정 조건은 이전에 계산된 연속합과 현재 위치의 숫자와의 합보다 현재 위치의 숫자가 더 클 경우, DP 배열의 현재 위치에는 현재 위치의 숫자값이 저장됩니다. 이를 점화식으로 나타내면 다음과 같습니다.

\[DP[i] = \max(A[i], DP[i-1] + A[i])\]

그러면 위 점화식과 실제 예제를 바탕으로 직접 DP 배열을 구해보도록 하겠습니다.

  • 숫자 리스트 : [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] (num_list)
  • DP 배열의 첫 번째 값만 10으로 초기화 합니다.

그럼 1부터 9까지 진행을 합니다.

1번째 위치일 때 계산 진행 :

  • DP[0] : 10
  • num_list[1] : -4
  • 두 수의 합 : 6
  • num_list[1] 과 DP[0] 와 num_list[1] 의 합 중 큰 값은 6이므로 DP[1] 에 6을 추가
  • DP -> [10, 6]

2번째 위치일 때 계산 진행 :

  • DP[1] : 6
  • num_list[2] : 3
  • 두 수의 합 : 9
  • num_list[2] 과 DP[1] 와 num_list[2] 의 합 중 큰 값은 9이므로 DP[2] 에 9를 추가
  • DP -> [10, 6, 9]

3번째 위치일 때 계산 진행:

  • DP[2] : 9
  • num_list[3] : 1
  • 두 수의 합 : 10
  • num_list[3] 과 DP[2] 와 num_list[3] 의 합 중 큰 값은 10이므로 DP[3] 에 10을 추가
  • DP -> [10, 6, 9, 10]

4번째 위치일 때 계산 진행:

  • DP[3] : 10
  • num_list[4] : 5
  • 두 수의 합 : 15
  • num_list[4] 과 DP[3] 와 num_list[4] 의 합 중 큰 값은 15이므로 DP[4] 에 15를 추가
  • DP -> [10, 6, 9, 10, 15]

5번째 위치일 때 계산 진행:

  • DP[4] : 15
  • num_list[5] : 6
  • 두 수의 합 : 21
  • num_list[5] 과 DP[4] 와 num_list[5] 의 합 중 큰 값은 21이므로 DP[5] 에 21을 추가
  • DP -> [10, 6, 9, 10, 15, 21]

6번째 위치일 때 계산 진행:

  • DP[5] : 21
  • num_list[6] : -35
  • 두 수의 합 : -14
  • num_list[6] 과 DP[5] 와 num_list[6] 의 합 중 큰 값은 -14이므로 DP[6] 에 -14를 추가
  • DP -> [10, 6, 9, 10, 15, 21, -14]

7번째 위치일 때 계산 진행:

  • DP[6] : -14
  • num_list[7] : 12
  • 두 수의 합 : -2
  • num_list[7] 과 DP[6] 와 num_list[7] 의 합 중 큰 값은 12이므로 DP[7] 에 12를 추가
  • DP -> [10, 6, 9, 10, 15, 21, -14, 12]

8번째 위치일 때 계산 진행:

  • DP[7] : 12
  • num_list[8] : 21
  • 두 수의 합 : 33
  • num_list[8] 과 DP[7] 와 num_list[8] 의 합 중 큰 값은 33이므로 DP[8] 에 33을 추가
  • DP -> [10, 6, 9, 10, 15, 21, -14, 12, 33]

9번째 위치일 때 계산 진행:

  • DP[8] : 33
  • num_list[9] : -1
  • 두 수의 합 : 32
  • num_list[9] 과 DP[8] 와 num_list[9] 의 합 중 큰 값은 32이므로 DP[9] 에 32를 추가
  • DP -> [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

위 과정을 끝내고 DP 배열 중 가장 큰 값을 출력하도록 하면 됩니다.

정답 코드

아래는 위 알고리즘을 기준으로 구현한 코드입니다.

import sys

_input = sys.stdin.readline

n = int(_input())

num_list = list(map(int, _input().split()))

_dp = [0 for _ in range(n)]
_dp[0] = num_list[0]

for i in range(1, n):
    _dp[i] = max(num_list[i], _dp[i-1]+num_list[i])

print(max(_dp))

위 코드를 제출하면 아래와 같이 결과로 ‘맞았습니다!!’ 가 뜨는 것을 확인하였습니다.

마치며

Baekjoon 에서 동적계획법 문제를 풀어보았습니다. 이번 1912 문제는 점화식만 알게 되면 굉장히 쉽게 풀 수 있는 문제였습니다. 하지만 문제에서 준 힌트를 가지고 이런 점화식을 생각해내는 것 자체가 굉장히 어렵다고 생각합니다. 수학적 사고력을 타고난 사람이 아니라면 굉장히 어렵지 않을까 생각합니다. 또한 이런 동적계획법 문제는 문제도 많이 풀어보아야 한다고 합니다. 하지만 저는 수학적 사고력이 부족하고, 학생일 때만 해도 기업의 코딩 테스트가 없었고, 졸업할 때쯤에 코딩 테스트를 보는 회사들이 많아져 알고리즘을 깊게 파보지 못해 아직까지 동적계획법 문제에는 많은 어려움을 겪고 있는 것 같습니다. 그래도 이렇게 하나씩 정리해 가다보면 어느 순간 혈이 뚫리는 날이 오지 않을까 합니다.

긴 글 읽어주셔서 감사드리며, 본문 내용 중에 잘못된 내용이나, 오타, 궁금하신 사항이 있으실 경우 댓글 달아주시기 바랍니다.

Comments

You May Also Enjoy