문제 : https://www.acmicpc.net/problem/11053
초기 구상과정
- "for문을 이용해서 앞선 숫자들과 비교해서 카운트를 세고 가장 큰 카운트를 출력하면 되겠다"라고 간단히 생각했다.
- 근데 왜 이게 DP?
초기 코드
초기 코드를 이번에는 날려버렸다. 이유는 지속적인 시간초과와 오답으로 인해서..(솔직히 화가 나기도 해서..)
구상 단계에서 적었듯이 이게 왜 DP로 해결해야하나?라고 의문점을 갖고 있었고 문제를 풀면서도 DP가 도대체 이해가 되지 않았다. 가장 작은 단위까지 내려가서 해결하며 점점 크기를 키워서 최종 결과를 도출한다고 하는데 이걸 이해하기가 너무 어려웠다. DP를 이해하고 넘어왔다고 생각했는데 그냥 전혀 모르고 있는 것이었다.
최종 코드
import sys
length = int(input())
nums = list(map(int, input().split()))
dp = [1] * length
result = 0
for a in range(length):
for b in range(a):
if nums[a] > nums[b]:
dp[a] = max(dp[a], dp[b] + 1)
print(max(dp))- 내가 이해하고 있었던, 다른 블로그나 문서들을 찾아봐서 이해했던 dp와는 꽤나 차이가 있는 코드였다.
- 매칭이 솔직히 아직도 잘 안되는 부분이 있다. memoization과 관련이 있다고 생각되는 코드였다.
- dp리스트를 추가해서 문제를 푸는 것이 확연한 차이점을 가져오는 것이 너무나도 신기했다. 결론적으로는 memoization도 dp의 한부분이라고 한다.
- 하나하나 카운트하는 것보다 그 자리에서 가지고 있는 최대의 수열 갯수를 dp에 저장해놓고 뒤로 움직이면서 그 자리 수보다 더 크면 단순히 1을 추가하고 기존에 가지고 있는 값이 더 크면 유지할 수 있도록 하는 코드가 답이었다.
솔직히 자괴감이 드는 건 내가 내 머리 속으로 해결하지 못해서 구선생님을 참고했다는 점.
느낀점
알고리즘에서 이해를 많이 하고 있다고 생각했는데 모르는 것이 너무나도 많고 이해하기 힘들다는 점과 이를 해결하는 방법이 도무지 떠오르지 않는다는 점이다. 많이 풀어보는 것도 장땡이 아니고 그저 풀지 못하는 문제를 계속해서 잡고만 있는 것도 능사는 아니라는 생각이 든다. 조금 스트레스 받는다...
interested in IT/tech