Dynamic programming 면접 질문

Dynamic programming 면접에서 다루는 내용

샘플 Dynamic programming 면접 질문

• DP에서 메모이제이션과 테이블화의 차이점을 설명하세요.
  좋은 답변이 다루는 것

  • 메모이제이션은 재귀 호출의 결과를 저장하여 중복 계산을 피하는 하향식 접근 방식입니다.
  • 테이블화는 반복문을 사용하여 작은 하위 문제부터 차례로 결과를 채워 나가는 상향식 접근 방식입니다.
  • 메모이제이션은 필요한 하위 문제만 계산하지만, 테이블화는 모든 하위 문제를 계산합니다.
  • 메모이제이션은 재귀 깊이로 인해 스택 오버플로우 위험이 있으나, 테이블화는 반복문을 사용하여 안정적입니다.
  • 시간 복잡도는 동일하지만 공간 최적화의 용이성에서 차이가 있습니다.

  샘플 답변 보기

  메모이제이션과 테이블화는 동적 프로그래밍의 두 가지 주요 구현 방식입니다. 메모이제이션은 하향식 접근으로, 재귀 함수가 호출될 때마다 결과를 캐시에 저장하고 동일한 입력이 다시 들어오면 저장된 값을 반환합니다. 이는 필요한 하위 문제만 해결하지만 재귀 호출로 인한 오버헤드와 깊이가 큰 경우 스택 오버플로우 가능성이 있습니다. 반면 테이블화는 상향식 접근으로, 가장 작은 하위 문제부터 시작하여 반복문으로 테이블을 채워 나갑니다. 모든 하위 문제를 계산하므로 불필요한 계산이 발생할 수 있지만 재귀 오버헤드가 없고 공간 최적화가 더 쉽습니다. 두 방식 모두 동일한 점화식을 기반으로 하며 시간 복잡도는 일반적으로 동일합니다. 선택은 문제의 특성과 메모리/스택 제약에 따라 달라집니다.

• DP(하향식 및 상향식 모두)를 사용하여 피보나치 수를 구현하세요.
  좋은 답변이 다루는 것

  • 하향식(메모이제이션)과 상향식(테이블화) 두 가지 방식으로 피보나치 수를 구현합니다.
  • 피보나치 수열은 dp[i] = dp[i-1] + dp[i-2]의 점화식을 따릅니다.
  • 하향식은 재귀 + 캐싱, 상향식은 반복문을 사용합니다.
  • 시간 복잡도는 O(n), 공간 복잡도는 하향식 O(n), 상향식 O(1)로 최적화 가능합니다.

  샘플 답변 보기

  피보나치 수를 구하는 문제는 동적 프로그래밍의 전형적인 예입니다. 하향식 구현에서는 메모이제이션을 사용하여 이미 계산된 피보나치 값을 딕셔너리나 배열에 저장하고 재귀 호출 시 이를 참조합니다. 상향식 구현에서는 반복문을 사용하여 작은 인덱스부터 순차적으로 값을 계산합니다. 공간 최적화가 가능하여 상향식에서는 두 개의 변수만으로도 구현할 수 있습니다. 두 방식 모두 O(n)의 시간 복잡도를 가지며, 하향식은 호출 스택으로 인해 추가적인 공간이 필요할 수 있습니다.

  # 하향식 (메모이제이션)
  def fib_top_down(n, memo={}):
      if n in memo:
          return memo[n]
      if n <= 1:
          return n
      memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
      return memo[n]
  
  # 상향식 (테이블화)
  def fib_bottom_up(n):
      if n <= 1:
          return n
      dp = [0] * (n+1)
      dp[1] = 1
      for i in range(2, n+1):
          dp[i] = dp[i-1] + dp[i-2]
      return dp[n]
  
  # 공간 최적화 상향식
  def fib_optimized(n):
      if n <= 1:
          return n
      a, b = 0, 1
      for _ in range(2, n+1):
          a, b = b, a + b
      return b
  
  # 시간 복잡도: O(n), 공간 복잡도: 하향식 O(n), 상향식 O(n), 최적화 O(1)

• 무게와 가치가 있는 항목 집합이 주어졌을 때, 최대 가치를 위한 0/1 배낭 문제를 해결하세요.
  좋은 답변이 다루는 것

  • 0/1 배낭 문제는 각 항목을 한 번만 선택할 수 있는 조합 최적화 문제입니다.
  • DP 테이블 dp[i][w]는 i번째 항목까지 고려하고 용량 w일 때의 최대 가치입니다.
  • 점화식: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) (w >= weight[i])
  • 시간 복잡도 O(n*W), 공간 복잡도 O(n*W)이며 공간 최적화가 가능합니다.

  샘플 답변 보기

  0/1 배낭 문제는 각 항목을 넣거나 빼는 두 가지 선택지를 가지며, 동적 프로그래밍으로 해결합니다. dp[i][w]를 i번째 항목까지 고려했을 때 무게 w 이하로 얻을 수 있는 최대 가치로 정의합니다. 각 항목에 대해 배낭에 넣지 않는 경우와 넣는 경우 중 더 큰 값을 선택합니다. 이를 위해 모든 i와 w에 대해 반복문을 수행합니다. 시간 복잡도는 항목 수 n과 최대 무게 W의 곱에 비례하며, 공간 복잡도도 동일합니다. 공간 최적화를 위해 1차원 배열을 사용할 수 있지만 무게를 역순으로 순회해야 합니다.

  def knapsack(weights, values, capacity):
      n = len(weights)
      dp = [[0] * (capacity + 1) for _ in range(n + 1)]
      for i in range(1, n + 1):
          for w in range(1, capacity + 1):
              if weights[i-1] <= w:
                  dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
              else:
                  dp[i][w] = dp[i-1][w]
      return dp[n][capacity]
  
  # 공간 최적화 버전
  def knapsack_optimized(weights, values, capacity):
      n = len(weights)
      dp = [0] * (capacity + 1)
      for i in range(n):
          for w in range(capacity, weights[i]-1, -1):
              dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
      return dp[capacity]
  
  # 시간 복잡도: O(n*capacity), 공간 복잡도: O(n*capacity) 또는 O(capacity)

• 배열에서 가장 긴 증가하는 부분 수열의 길이를 찾으세요.
  좋은 답변이 다루는 것

  • LIS 문제는 배열에서 순서를 유지하며 증가하는 부분 수열의 최대 길이를 찾습니다.
  • DP 정의: dp[i]는 i번째 원소를 마지막으로 하는 LIS의 길이입니다.
  • 점화식: dp[i] = 1 + max(dp[j]) for j < i and arr[j] < arr[i]
  • 시간 복잡도 O(n^2), 공간 복잡도 O(n)입니다.
  • 이진 탐색을 사용하여 O(n log n)으로 개선할 수 있습니다.

  샘플 답변 보기

  가장 긴 증가하는 부분 수열(LIS) 문제는 입력 배열의 원소 순서를 유지하면서 증가하는 부분 수열 중 가장 긴 것의 길이를 구합니다. 기본 DP 접근법에서는 dp[i]를 i번째 인덱스에서 끝나는 LIS의 길이로 정의하고, 각 i에 대해 이전의 모든 j를 확인하며 조건을 만족하는 경우 최대값을 갱신합니다. 이 알고리즘은 O(n^2) 시간이 소요됩니다. 더 효율적인 방법으로는 tails 배열을 사용하여 증가 부분 수열의 마지막 원소를 관리하고 이진 탐색으로 위치를 찾는 O(n log n) 알고리즘이 있습니다.

  # O(n^2) DP 솔루션
  def length_of_LIS(nums):
      if not nums:
          return 0
      n = len(nums)
      dp = [1] * n
      for i in range(n):
          for j in range(i):
              if nums[j] < nums[i]:
                  dp[i] = max(dp[i], dp[j] + 1)
      return max(dp)
  
  # O(n log n) 솔루션
  def length_of_LIS_optimized(nums):
      import bisect
      tails = []
      for x in nums:
          i = bisect.bisect_left(tails, x)
          if i == len(tails):
              tails.append(x)
          else:
              tails[i] = x
      return len(tails)
  
  # 시간 복잡도: 첫 번째 O(n^2), 두 번째 O(n log n) / 공간 복잡도: O(n)

• 두 문자열 사이의 편집 거리(Levenshtein 거리)를 계산하세요.
  좋은 답변이 다루는 것

  • 편집 거리는 두 문자열을 같게 만들기 위해 필요한 최소 연산 수(삽입, 삭제, 대체)입니다.
  • DP 테이블 dp[i][j]는 첫 번째 문자열의 처음 i글자와 두 번째 문자열의 처음 j글자 사이의 편집 거리입니다.
  • 점화식: dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost) (cost = 0 if 같으면 1 else 1)
  • 시간 복잡도 O(n*m), 공간 복잡도 O(n*m)이며 공간 최적화가 가능합니다.

  샘플 답변 보기

  Levenshtein 거리(편집 거리)는 두 문자열을 동일하게 만들기 위해 필요한 삽입, 삭제, 대체 연산의 최소 횟수입니다. 동적 프로그래밍을 사용하면 dp[i][j]를 첫 번째 문자열의 i번째까지와 두 번째 문자열의 j번째까지의 편집 거리로 정의하고, 점화식을 통해 값을 채웁니다. 기본 케이스는 빈 문자열에 대한 거리입니다. 이 알고리즘은 O(n*m) 시간과 공간이 필요하지만, 공간을 두 행만 사용하여 O(m)으로 줄일 수 있습니다.

  def edit_distance(str1, str2):
      n, m = len(str1), len(str2)
      dp = [[0] * (m+1) for _ in range(n+1)]
      # 초기화
      for i in range(n+1):
          dp[i][0] = i
      for j in range(m+1):
          dp[0][j] = j
      # DP 채우기
      for i in range(1, n+1):
          for j in range(1, m+1):
              if str1[i-1] == str2[j-1]:
                  cost = 0
              else:
                  cost = 1
              dp[i][j] = min(dp[i-1][j] + 1,      # 삭제
                             dp[i][j-1] + 1,      # 삽입
                             dp[i-1][j-1] + cost) # 대체
      return dp[n][m]
  
  # 시간 복잡도: O(n*m), 공간 복잡도: O(n*m)

• 동전 교환 문제를 해결하세요: 주어진 금액을 만들기 위한 최소 동전 수.
  좋은 답변이 다루는 것

  • 동전 교환 문제는 주어진 금액을 만들기 위해 필요한 최소 동전 개수를 구합니다.
  • DP 정의: dp[i]는 금액 i를 만들기 위한 최소 동전 수입니다.
  • 점화식: dp[i] = min(dp[i-coin] + 1 for coin in coins if coin <= i)
  • dp[0] = 0, 나머지는 큰 값으로 초기화합니다.
  • 시간 복잡도 O(amount * n), 공간 복잡도 O(amount)입니다.

  샘플 답변 보기

  동전 교환 문제(최소 동전 수)는 동전의 종류가 주어졌을 때 특정 금액을 만들기 위해 필요한 최소 동전의 개수를 구하는 문제입니다. 동적 프로그래밍을 사용하여 dp[i]를 금액 i를 만들기 위한 최소 동전 수로 정의합니다. dp[0]은 0으로 설정하고, 나머지는 충분히 큰 값으로 초기화합니다. 각 금액에 대해 모든 동전을 확인하며 더 작은 값을 갱신합니다. 이 알고리즘은 O(amount * n)의 시간 복잡도를 가지며, 공간 복잡도는 O(amount)입니다.

  def coin_change(coins, amount):
      dp = [float('inf')] * (amount + 1)
      dp[0] = 0
      for i in range(1, amount + 1):
          for coin in coins:
              if coin <= i:
                  dp[i] = min(dp[i], dp[i - coin] + 1)
      return dp[amount] if dp[amount] != float('inf') else -1
  
  # 시간 복잡도: O(amount * len(coins)), 공간 복잡도: O(amount)

• 한 번에 1步 또는 2步 계단을 오를 때 계단을 오르는 방법의 수를 세세요.
  좋은 답변이 다루는 것

  • 계단 오르기 문제는 n계단을 오를 때 1步 또는 2步로 오르는 방법의 수를 구합니다.
  • 점화식: f(n) = f(n-1) + f(n-2) (피보나치 수열과 동일)
  • 기본 케이스: f(1)=1, f(2)=2
  • DP로 O(n) 시간, O(1) 공간으로 해결 가능합니다.
  • 실제로는 피보나치 수를 구하는 문제와 동일합니다.

  샘플 답변 보기

  계단 오르기 문제는 전형적인 동적 프로그래밍 문제로, 피보나치 수와 동일한 점화식을 가집니다. f(n) = f(n-1) + f(n-2)이며, 기본 케이스는 n=1일 때 1가지, n=2일 때 2가지입니다. 반복문을 사용하여 상향식으로 계산하면 O(n) 시간에 해결할 수 있으며, 공간은 두 변수만 있으면 되므로 O(1)로 최적화 가능합니다. 이 문제는 재귀나 메모이제이션으로도 풀 수 있지만, 반복문이 가장 효율적입니다.

  def climb_stairs(n):
      if n <= 2:
          return n
      a, b = 1, 2
      for _ in range(3, n+1):
          a, b = b, a + b
      return b
  
  # 시간 복잡도: O(n), 공간 복잡도: O(1)

• 하위 문제 식별부터 솔루션 코딩까지 모든 DP 문제를 해결하는 단계별 접근 방식을 설명하세요.
  좋은 답변이 다루는 것

  • DP 문제 해결 단계: 1) 문제 이해 및 최적 부분 구조 확인, 2) 상태 정의, 3) 점화식 도출, 4) 기본 케이스 설정, 5) 구현 방식 선택(하향식/상향식), 6) 코드 구현 및 테스트.
  • 최적 부분 구조는 하위 문제의 최적해가 상위 문제의 최적해에 포함되어야 합니다.
  • 상태 정의는 중복되는 하위 문제를 식별하는 핵심입니다.
  • 점화식은 현재 상태와 이전 상태 간의 관계를 나타냅니다.
  • 기본 케이스는 더 이상 분할할 수 없는 가장 작은 문제의 해입니다.

  샘플 답변 보기

  모든 동적 프로그래밍 문제를 해결하는 체계적인 접근 방식은 다음과 같습니다. 첫째, 문제가 최적 부분 구조를 가지고 있는지 확인합니다. 즉, 큰 문제의 최적해가 작은 하위 문제들의 최적해로 구성될 수 있어야 합니다. 둘째, 상태를 정의합니다. 이는 하위 문제를 나타내는 변수(예: 인덱스, 무게, 금액 등)의 조합입니다. 셋째, 점화식을 도출합니다. 상태 간의 관계를 수식으로 표현합니다. 넷째, 기본 케이스를 설정합니다. 가장 작은 하위 문제의 해를 정의합니다. 다섯째, 구현 방식을 선택합니다. 하향식(메모이제이션)은 재귀 + 캐싱을, 상향식(테이블화)은 반복문을 사용합니다. 여섯째, 코드를 구현하고 경계 조건을 테스트합니다. 이 단계를 따르면 대부분의 DP 문제를 체계적으로 해결할 수 있습니다.

준비 방법

• 배낭, LCS, 그리드 문제와 같은 일반적인 DP 패턴을 마스터하세요.
• 코딩 전에 처음부터 점화식을 작성하는 연습을 하세요.
• 무차별 재귀로 시작한 다음 메모이제이션을 추가하고 필요하면 테이블화로 변환하세요.
• 공간 최적화 기술(예: 2D DP를 1D로 축소)을 사용하여 효율성을 향상시키세요.
• 각 패턴에서 최소 3-4문제를 풀어 DP 인식을 위한 직관을 구축하세요.

자주 묻는 질문