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

총 학습 시간

공부 기록

알고리즘 문제 풀이

문제 명(블로그 링크)	소요 시간	난이도
86 ─에이티식스─ 1	1시간 10분	Gold 5
시간 관리	31분	Gold 5

 

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

 

회고

오늘로 인프런 챌린지를 시작한 지 절반이 지났다. 앞으로 아마 10일 정도 남았는데, 지난 11일 동안 한 것들이 이전 두 달 동안 한 것보다 훨씬 많은 것 같다. 다시금 느끼지만 인프런 챌린지를 시작하길 잘한 것 같다. 이걸 추천해 준 누군가에게 정말 고맙게 생각한다.

 

오늘은 백트래킹(브루트포스) 1문제, 그리디 1문제를 풀었는데 백트래킹 문제가 생각보다 쉽지 않았다.

 

단순히 대각선으로 이동하면서 최단 경로를 탐색하는 문제라고 생각해서 DFS로 풀다가 너무 많은 시간을 쏟았다…

 

40분 정도 삽질하다가 너무 피곤해서 잠깐 머리를 식히려고 샤워를 했다. 그런데 샤워하면서 갑자기 풀이 방법이 떠올랐고, 까먹기 전에 대충 씻고 나와서 바로 문제를 풀었다. 난 이럴 때마다 전구 떴다! 라고 말한다. 다들 이런 경험 있지 않나…?

 

문제를 풀고 나서 생각해 보니 시간 복잡도를 먼저 파악하지 않은 것이 실수였던 것 같다.
평소에는 항상 시간 복잡도를 간단하게 계산해 보면서 푸는데, 이 문제에서는 N = 100밖에 안 되니까 DFS도 당연히 돌아가지 않을까? 하고 넘겼던 게 패인이었다.

 

실전에서 같은 실수를 하지 않도록 항상 의식해야겠다.

 

그리디는 문제를 딱 보면 그리디라는 것이 바로 보인다는 점이 장점인 것 같다. 하지만 오히려 그렇기 때문에 더 힘이 빠지는 것 같기도 하다. 이번 문제도 별다를 것 없이 또 그리디네… 하면서 풀었는데, 엣지 케이스도 안틀리고 바로 풀었다.

 

그리디 문제를 이렇게 쉽게 푼건 정말 오랜만인가 싶었는데 또 골드 5라고 생각하니 쉬워서 그런가 싶기도 하고..