재귀함수와 동적 프로그래밍으로 코드를 짜는 것과 분할 정복으로 접근하는 것은 차원이 다르다.
백준에 있는 문제를 풀어가는 과정에서 단계별 문제 풀어보기를 2월 초부터 접근하고 있었고, 49단계까지 있지만 상황상 2월내에 25단계에 있는 투 포인터까지는 접근하자고 마음먹고 있었고, 그래도 몇 몇 문제를 제외하면 (DFS, BFS, 최단 경로) 종류 별로 하나씩은 다 풀어본 것 같다.
그런데 오늘 너무 충격적인 문제를 보고 와서 정리를 안 할 수가 없었다. 피보나치 문제가 어려워지면 한 없이 어려워질 수 있다는 걸 처음 느낀 문제인 백준 11444번, 피보나치 6 문제다.
일반적으로 피보나치 알고리즘 풀이를 생각하면 2가지 접근을 생각하게 된다. (가장 일반적이고, 초심자가 배우는 단계의 문제다)
- 재귀 함수
이 접근법은 인터넷에 정답도 많이 나와있고, 알고리즘 초심자라면 누구나 배우는 문항이라 설명을 길게 하지 않겠지만, 테스트 케이스로 주어진 수가 커지면 함수 호출 횟수가 기하급수적으로 늘어서 연산 속도가 매우 떨어지기 때문에 동적 프로그래밍 기법을 배우게 된다.
2. 동적 프로그래밍
백준 11444번 문제를 풀 때, 가장 먼저 나는 이 접근법을 사용했다. 사람마다 사용하기 나름이겠지만 fibo 변수를 나는 딕셔너리를 사용했지만, 리스트를 사용해 푸는 것도 꽤 일반적이다. 여기서 딕셔너리를 사용한 이유는 리스트를 사용했을 때, 메모리 초과가 나와서 혹시 몰라 딕셔너리로 시도해본 것이다.
도대체 뭐가 문제인가 싶더니, n은 1,000,000,000,000,000,000보다 작거나 같은 자연수 라는 조건 때문에 내가 떠올린 해결책으로는 주어진 연산을 해결할 수 없는 것이었다.
3. 분할정복과 행렬 곱을 활용 (진짜 미친듯이 어렵다. 아직 이해도 제대로 못했다)
아직 이해를 100% 한 건 아니지만, 여기서 중요한 건 분할 정복 기법으로 접근해서 행렬을 사용하면, 엄청나게 큰 수에 대해 O(logN)의 연산 속도로 풀이를 할 수 있다는 점이 상당히 강점인 것 같다.
솔직히 이 문제 풀이법은 생각도 못했고, 코드로 구현하는 방법은 더더욱 처음보는 형태였다.
다만, 분할 정복 파트에 있는 문제 목록을 보면 쿼드트리 → 행렬의 거듭제곱 형태로 가는 내용이라, 분할 정복에서 행렬의 거듭제곱을 쓰는 방식은 꽤 빈도 높게 나오는 것 같기는 하다.
하나씩 순서대로 푸는 형태로 접근해야겠다. 분할 정복은 진짜 어려워서 풀이 정리를 꼼꼼히 해야겠다.
11444번 문제 풀고 나니 백준 경험치가 갑자기 엄청나게 올랐다. 진짜 어려운 문제라는 것을 다시 체감하고, 문제 난이도가 골드 3이었다.
골드 레벨부터는 난이도가 확실히 달라지는 것 같다.
주말에 있을 코딩 테스트의 모의 환경 테스트를 오늘 진행했고, 3 문제 모두 정말 쉬워서 ‘아, 레벨 정말 많이 오르기는 했구나’ 생각하면서 흡족하고 있었는데, 순식간에 아직 넘어야할 벽이 있음을 통감하게 되었다.
갈 길이 멀지만 차근차근 가면 못 갈 것도 없다.
Ryan
