[인프런] 3월 무한 작심삼일 챌린지 - 10일차

총 학습 시간

공부 기록

알고리즘 문제 풀이

문제 명(블로그 링크)	소요 시간	난이도
경로 찾기	1시간 30분	Gold 2

 

소프트웨어 마에스트로 면접 준비

회고

오늘 푼 문제는 DP였다. 근데 난생 처음 풀어본 DP 문제였다..

 

이 문제는 4차원 배열을 사용해야 하는 문제다. 나는 지금까지 3차원 DP까지는 풀어봤는데 갑자기 4차원 DP가 나와서 너무 어렵게 느껴졌다. 솔직히 플래티넘 문제보다 훨씬 더 어렵다고 생각했다.

 

보통같았으면 1시간정도 오버하면 풀이를 보고 문제를 이해하는데, 뭔가 점화식이 거의 나올 듯 말듯 하니까 답답해서 계속해서 문제를 풀다보니 1시간 30분이나 걸렸다.

 

그래도 어렵다고 악명높은 DP 문제인데, 4차원 DP를 정답을 보지 않고 풀었다는 것에 약간의 성취감도 있었던 것 같다.

DP문제는 점화식을 세우는게 정말 어렵다. 특히 처음 접하면 이해가 하나도 안될 정도로 어려운데, 계속해서 DP문제를 풀어보고 높은 난이도의 문제도 풀다 보니까 점화식을 세우는 팁? 같은게 느껴지는 것 같다.

 

말로 설명하기는 어려운데 이건 어느순간 스스로가 어떻게 점화식을 세워야 하는지 깨우치는 날이 오는 것 같다.