DP
오늘은 DP(Dynamic Programming) 문제들을 풀었다. 어제 구상했던 '동전(9084)' 을 더 보완해서 구현했는데, 풀이를 찾아보니 2차원 배열이 아닌 1차원 배열로도 해결이 가능한 문제여서 더욱 공부가 되었다. 'LCS(9251)' 문제는 지지난주에 풀었던 LIS와 유사하다고 생각했는데, 그 때는 이진 탐색으로 풀었어서 풀이방식을 다시 공부했다. 친구가 큰 힌트를 주었고, 마침 교재인 'Introduction to algorithm' 에도 이 내용을 다루어서 좋은 참고가 되었다. '아주 평범한 배낭(12865)' 은 문제 제목 그대로 기본적인 '배낭 문제'였다. '배낭 문제' 자체에 관해 다룬 글들이 많아서 공부하고 풀었다.
DP 문제에 대해 Top-Down 방식이 아닌 Bottom-Up 방식을 쓰려고 노력하고 있는데, 이는 python에서 재귀 횟수 제한 오류가 나타날 수 있기 때문이다. 이러한 문제는 sys 라이브러리의 setrecursionlimit() 메서드로 해결할 수 있으나 그래도 다들 Bottom-Up을 권장했는데, Top-Down의 풀이 방식으로만 해결할 수 있는 문제가 있다고 들었다. Top-Down으로도 풀어봐야겠다.
여담
오늘은 친구들과 자전거를 타고 다이소에 갔다왔다(팀원인 형에게 빌렸다). 잘못 구매한 운동기구를 환불하고 새로운 운동기구를 구매했는데 만족도가 굉장히 높다. 가슴 안쪽을 운동하려고 구매했는데, 어깨운동도 할 수 있다고 표기되어있어서 설렌다.
오랜만에 자전거를 타니 너무 재밌었다. refresh하는 기분도 들고 내 운전실력이 아직 쓸만함을 검증할 수 있었다.
내일은 저녁부터 외출을 할 예정이다. 문제들을 몇 개 풀어놔서 다행이지만 걱정이다. 그래도 쉬기로 한 만큼 잠시만 노트북도 내려놓고 나갔다 올 예정이다. 모레 돌아와서 다시 열심히 하자.
