책너두 (코딩 인터뷰 완전분석) 24일차 (~197p, 8.1, 8.2, 8.3)

메모

8. 재귀와 동적 프로그래밍

• 재귀 관련 문제는 상당수가 패턴이 비슷함.
  • 주어진 문제가 재귀 문제인지 확인해 보는 좋은 방법은 해당 문제를 작은 크기의 문제로 만들 수 있는지 보는 것임.
• 다음과 같은 문장으로 시작하는 문제는 재귀로 풀기 적당한 문제일 가능성이 높음.
  • “n번째 … 를 계산하는 알고리즘을 설계하라”
  • “첫 n개를 나열하는 코드를 작성하라.”
  • “모든 … 를 계산하는 메서드를 구현하라.”

사람들이 직감적으로 이 문제가 재귀 문제 같다! 라고 했을 때, 실제로 그문제가 재귀 문제인 경우는 보통 50% 정도였음. 따라서, 재귀로 문제가 풀릴것 같더라도, 다른 방식으로 생각해보는 것을 게을리하면 안됨.

접근법

• 재귀적 해법 → 부분문제(subproblem)에 대한 해법을 통해 완성됨.
  • ex) f(n-1) 에 무언가를 더하거나, 빼거나, 해답을 변경해서 f(n)을 계산함
  • 혹은, 데이터를 반으로 나눠 각각에 대한 문제를 푼 뒤 병합(merge) 하기도 함.
• 주어진 문제를 부분문제로 나누는 방법도 여러가지가 있음.
  • 가장 흔하게 사용되는 세 가지 방법
    • 상향식(bottom-up)
    • 하향식(top-down)
    • 반반(half-and-half)

상향식 접근법

• 가장 직관적인 경우가 많음.
• 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작됨.
  • ex) 리스트 1개일때, 2개일때 …. N개일때

하향식 접근법

• 덜 명확해서 복잡해 보일 수 있음.

  • 하지만 가끔 이 방법이 문제에 대해 생각해 보기에 가장 좋은 방법이기도 함.

  • ex) N에 대한 문제를 부분 문제로 나눌 수 있지 않을까?

    → 나뉜 부분문제의 경우 서로 겹치지 않도록 주의한다.

반반 접근법

• 데이터를 절반으로 나누는 방법도 종종 유용함.
  • ex) 이진 탐색은 반반 접근법을 이용한 탐색 방법임.
    • 정렬된 배열에서 특정 원소를 찾을 때, 가장 먼저 왼쪽 절반과 오른쪽 절반 중 어디를 봐야 하는지 확인한다.
    • 절반의 재귀적으로 탐색해 나간다.
  • 병합 정렬(merge sort) 또한 반반 접근법을 이용한 정렬 방법임.
    • 배열 전반을 각각 정렬한 뒤, 이들을 하나로 병합한다.

재귀적 해법 vs 순환적 해법

• 재귀적 알고리즘을 사용하면 공간 효율성이 나빠질 수 있음.
  • 재귀 호출이 한 번 발생할 때마다 스택에 새로운 층(layer)을 추가해야 함.
  • 이는 재귀 깊이가 n일때 O(n) 만큼 메모리를 사용하게 됨.
  • 이런 이유로, 재귀적(recursive) 알고리즘을 순환적(iterative)으로 구현하는 것이 더 나을 수 있음.
• 모든 재귀적 알고리즘은 순환적으로 구현될 수 있음.
  • 순환적으로 구현된 코드는 때로 훨씬 더 복잡함.
  • 두 방법 사이에 어떤 방법이 좋을지 타협점을 찾을 필요가 있음.

동적계획법 & 메모이제이션

• 동적 프로그래밍 문제가 어렵다고 하는데, 실제로, 감을 한번 잡으면 쉽게 풀 수 있음.
• 거의 대부분 재귀적 알고리즘과 반복적으로 호출되는 부분문제를 찾는 것이 관건임.
  • 찾은 다음, 나중을 위해 현재 결과를 캐시에 저장해 놓으면 됨.
• ex) 피보나치 수열

int fibonacci(int i) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonacci(i - 1) + fibonacci(i - 2);
}

• 수행 시간을 생각해보려면, 함수가 호출되는 경로를 재귀 트리로 그려보면 도움이 됨.

재귀 호출을 트리로 그려보는 것은 재귀적 알고리즘의 수행 시간을 알아내는 데 굉장히 효과적임.

• 루트 노드와 그 자식노드 2개가 있다.
  • 노드 n개만큼 반복되므로, O(2^n) 시간이 걸림.
  • 수행 시간이 n이 커지면 기하급수적으로 커지므로 최적화할 방법을 찾아야 함.

하향식 동적 프로그래밍(메모이제이션)

• 위 피보나치는 노드마다 중복된 계산이 많이 일어남.
• 사실, fib(n)을 호출할 때, 탐색할 경우의 수가 O(n) 이므로, fib는 O(n)번 이상 호출되면 안됨.
  • 따라서, 매번 fib(i)를 계산할 때마다 캐시에 저장하고, 나중에 저장된 값을 사용하는 것이 좋음.
    • 이를 바로 메모이제이션(memoization) 이라고 함.

int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) return i;
    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return memo[i];
}

• 캐시를 사용하여 O(N) 시간에 돌아가게끔 만듦.

상향식 동적 프로그래밍

• 구현을 상향식으로 할 수도 있음.
• 초기 사례인 fib(1)과 fib(0)을 계산함.
• 이 둘을 이용해 fib(2)를 계산하고, 차례로 fib(3)과 fib(4)를 이전의 결과를 이용해 계산한다.

면접 문제

8.1 트리플 스텝

• 어떤 아이가 n개의 계단을 오른다. 한 번에 1계단 오르기도 하고, 2계단이나 3계단을 오르기도 한다. 계단을 오르는 방법이 몇 가지가 있는지 계산하는 메서드를 구현하라.

8.2 격자판(grid)상의 로봇

• 행의 개수는 r, 열의 개수는 c인 격자판의 왼쪽 상단 꼭짓점에 로봇이 놓여 있다고 상상해 보자. 이 로봇은 오른쪽 아니면 아래쪽으로만 이동할 수 있다. 하지만 어떤 셀(cell)은 ‘금지 구역’으로 지정되어 있어서 로봇이 접근할 수 없다. 왼쪽 상단 꼭짓점에서 오른쪽 하단 꼭짓점으로의 경로를 찾는 알고리즘을 설계하라.

8.3 마술 인덱스

• 배열 인덱스 A[0 … n-1]에서 A[i] = i인 인덱스를 마술 인덱스(magic index)라 정의한다. 정렬된 상태의 배열이 주어졌을 때, 마술 인덱스가 존재한다면 그 값을 찾는 메서드를 작성하라. 배열 안에 중복된 값은 없다.