[크래프톤 정글 2기] Day 26

오늘의 글귀

아무리 좋은 것일지라도 우리에게 쾌락을 가져다주는 것들이라면 반드시 버려야 하네. 그렇지 않으면 용기는 사라지고 끊임없는 유혹만이 남게 되어, 영혼의 위대함도 사라지고 말지. 군중이 멸망하는 사소한 것들을 경멸하지 않는 한, 영혼의 위대함은 결코 그 모습을 드러내지 않는 법이네.

(세네카, 도덕에 관한 서한)

회고

오늘은 평소보다 늦잠을 잤다. 테스트 다음날이라 마음이 늘어진 듯 하다. 오늘부터는 4주차 알고리즘 과제를 푼다. 4주차 과제의 카테고리는 DP와 그리디 알고리즘이다. 둘 다 예전에 많이 풀어보았던 유형이라 술술 풀거라 생각했지만, 생각보다 어려웠다. 분명 풀었던 문제인데 어떻게 풀어야할지 하나도 생각이 나질 않았다. 그러고보니 DP가 원래 그랬지. 이름부터가 왜 동적 프로그래밍인지 몰라서 예전에도 한창 고민하다가 솔루션을 보고 풀었었다. 동적 프로그래밍에 대해서 지금 알고 있는 것은 "하나의 문제를 단 한번만 푼다"는 것 뿐이다. 경험적으로 점화식처럼 현재의 답을 이전의 답으로 구할 수 있는 경우 DP로 풀 수 있다. DP는 어떤 코드 구현 양식이 있는 것이 아니라 하나의 방법론이기 때문에 특히 문제에 적용하기가 어렵다. 개념은 알아도 이걸 어떤식으로 써먹어야할지를 알 수가 없는 것이다. 문제에 대한 솔루션을 보면 신박할 뿐이다.

지금으로선 최대한 많이 문제를 풀어보면서 문제 유형을 머리속에 박아넣는 것만이 유일한 방법이다. 풀었던 문제도 또 풀고, 솔루션을 완전히 이해할 때까지 들여다봐야한다.

나에게 가장 어려운 문제 유형은 DP인 것 같다. 구현과 그래프, 분할정복, 이분탐색 등은 어떻게 푸는 방법을 떠올릴 순 있었지만 DP는 그게 안된다. DP 다음으로 어려운 유형은 문자열..이지만, 문자열 알고리즘 자체가 어려운 것들이 많기도 하다.

오늘은 운동을 가지 않았다. 비가 와서 헬스장까지 자전거를 타고 가기가 힘들기도 했고 오늘 특히 피곤하기도 했다. 그래서 공부를 적당히 마치고 쉬려고했다.

공부를 마치고 동료들과 맥주 한 잔 하러왔다. 입소 3일차의 뒤풀이 이후 3주만에 술을 먹으러 왔다. 오랜만에 맥주를 마시는 것만으로 스트레스가 풀린다. 공부하는 동료들을 생각하면 죄책감이 들기도 했지만 오늘 하루 리프레쉬하고 내일은 더 열심히 하기로 하며 생맥주를 들이켰다. 그래봤자 1시간도 안 마시고 복귀했다. 다음엔 치맥이다.

TIL

• DP에 대해 복기했다. DP는 "한 번 푼 문제는 다시 풀지 않는다."는 기본 원칙 위에서 구현된다. 메모이제이션 기법이 사용되며, 큰 문제를 작은 문제로 분할하여 프로그래밍 실행 중에 얻게된 작은 문제의 정답을 큰 문제를 해결하는데 사용하는 것이다. DP 문제 유형은 정말 다양한데, 문자열, 수학, 점화식 등등이다. [[플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)]]]] 처럼 다른 알고리즘에 사용되기도 한다.
• 그리디 알고리즘은 언제나 최선의 이득만을 추구하는 알고리즘이다. 개념도 쉽고 문제 난이도도 크게 어렵지 않은 편이다. 대신 어려운 문제는 한없이 어려운 유형이다. "입문은 쉽지만 마스터는 어려운" 것이다.