기술면접 — 재귀, 다이나믹 프로그래밍, 백트래킹
재귀
정의
자신을 재참조하는 함수
WHY
- 재귀의 호출은 하위 문제에 대해 이루어져야 합니다. 어떤 문제를 해결하기 위해, 문제의 범위보다 약간 좁은 하위 문제를 해결합니다. 그 다음에 하위 문제에 대한 해답을 이용하여 원래 문제를 해결합니다. (Top-Down 방식)
- 재귀 알고리즘이 실제로 작동하려면, 범위가 더 좁은 하위 문제가 base case에 도달하여, 재귀 함수가 끝날 수 있어야 합니다.
작은 문제와 종료조건에 대한 명확한 정의가 필요하다.
특징
재귀는 활성레코드에 호출스택이 누적되어, 성능 상의 문제가 있지만, 코드의 가독성이 높다.
다이나믹 프로그래밍
정의
시간에 따라 변하는 데이터를 고려하여, 큰 문제를 작은 문제로 쪼개서 푸는 방식이다. 함수대신 배열의 이미 연산된 작은 값들을 활용하여 큰 값들을 반복적으로 채워나가는 방식이다.
- 다이나믹(Dynamic): 동적 메모리(시간에 따라 변하는 메모리)
- 프로그래밍(Programming): 다단계(큰 문제 안에서 작은 문제들이 중첩된)로 이루어진 문제 풀이(계획)
WHY
지수시간의 시간복잡도를 갖는 재귀함수를 사용할 때, 메모이제이션(Memoization)이라는 캐시 기능을 활용하면, 시간복잡도를 O(N)으로 줄일 수 있다. (시간복잡도와 공간복잡도 — 함수의 활성레코드 — 의 성능향상)
WHEN, WHERE
- 부분적으로는 O(n³) 등 다항식 수준의 시간복잡도를 O(n*logn) 등의 로그 수준으로 줄여 성능을 높일경우 DP를 활용할 수 있을지 판단해야 한다.
- 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
- 강화학습, NLP에 있어서 DP의 문제 해결방식은 큰 도움을 준다.
HOW
- 문제를 하위 문제를 사용해, 하향식으로 정의
→ 재귀 함수는 전체 작업의 일부만 수행하고, 나머지는 재귀 호출에 위임합니다. - 제일 하위인 Base, 혹은 종료 조건을 정의
- 메모 전략을 시도
재귀와의 차이점
Top-Down 방식을 주로 이용하는 재귀와는 달리, DP에서는 Bottom-Up 방식을 이용한다.
개념
- 메모이제이션(memoization)(Top-Down): 하위 문제에 대한 정답을 계산했는지 확인해가면서 문제를 자연스러운 방식으로 풀어나간다.
- 타뷸레이션(tabulation)(Bottom-Up): 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다.
백트래킹
정의
상태 공간을 트리로 나타낼 수 있을 때, 모든 경우의 수를 전부 고려하는 알고리즘. 트리 탐색 알고리즘 처럼 BFS, DFS, Heuristic Search 가 있다.
여기서 포인트는, 유망하지 않으면 배제를 하고, 부모 노드로 되돌아가면서 풀이 시간이 단축된다. → 최종 결정에 영향을 주지 않는 부분을 쳐 내면서, 경우의 수를 줄여 나간다.(Pruning)
일반적으로 DFS가 편리하지만(BFS의 경우, 큐에 넣어야 할 데이터의 양을 고려해야 한다.) 트리의 깊이가 무한대가 될 때는, DFS를 사용하면 안된다.
HOW
- 헬퍼함수를 어떤 식으로 이용하여 ‘특정조건(유망성)’을 따질 것인가?
- 조건에 부합하지 않는 경우는 어떤 식으로 넘어갈 것인가?
