[코딩 인터뷰 완전 분석] 재귀와 동적 프로그래밍

• 해당 문제를 작은 크기의 문제로 만들 수 있는가?
• n번째 ... 를 계산하는 알고리즘을 설계하여라.
• 첫 n개를 나열하는 코드를 작성하여라. 
• 모든 ... 를 계산하는 메서드를 구현하라.
• 재귀로 문제를 풀 수 있을 것 같아도 다른 방식으로 생각해보는 것을 게을리하면 안 됨!

 

상향식 접근법 bottom-up

우선 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작한다. 

ex. 원소 하나를 갖는 리스트에서 시작하여, 두 개, 세 개 늘려가며 풀이법을 찾는다. 

이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다. 

 

하향식 접근법 top-down

문제를 어떻게 하면 N개로 나눌 수 있는지 생각해본다. 부분문제끼리 겹치지 않아야 한다.

 

반반 접근법

데이터를 절반씩 나누는 방법.

ex. 이진 탐색 : 특정 원소를 찾을 때, 가장 먼저 왼쪽 절반과 오른쪽 절반 중 어디를 봐야 하는지 확인한다. 이와 같은 방식으로 절반씩 재귀적으로 탐색해나간다.

ex. 병합 정렬 : 배열 절반을 각각 정렬한 뒤 이를 하나로 병합해나간다.

 

---

 

• 재귀적 알고리즘을 사용하면 공간 효율성이 나빠질 수 있다. 한 번 call할 때마다 스택에 새로운 층을 추가해야 한다. 재귀의 깊이가 n일 때 O(n)만큼 메모리 사용함.
• 재귀적 알고리즘을 순환적으로 구현하는 것이 더 나을 수도 있다.