자료구조 및 알고리즘 면접 질문

자료구조 및 알고리즘 면접에서 다루는 내용

샘플 자료구조 및 알고리즘 면접 질문

• 배열에서 합이 타겟이 되는 두 숫자를 찾고 복잡도를 분석하세요.
  좋은 답변이 다루는 것

  • 해시맵을 사용한 O(n) 시간 복잡도
  • 공간 복잡도 O(n) 트레이드오프
  • 정렬 후 투 포인터 접근과의 비교 (O(n log n))
  • 한 번의 순회로 해결 가능
  • 중복 인덱스 처리 주의

  샘플 답변 보기

  가장 효율적인 방법은 해시맵을 사용하는 것입니다. 한 번의 배열 순회 동안 각 요소에 대해 타겟에서 현재 값을 뺀 보수를 해시맵에서 찾습니다. 존재하면 해당 인덱스들을 반환하고, 없으면 현재 값과 인덱스를 해시맵에 저장합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 정렬 후 투 포인터를 사용하는 방법은 O(n log n) 시간과 O(1) 공간이 필요하지만 인덱스를 반환해야 하는 경우 인덱스 보존 문제가 있습니다. 주의할 점은 동일한 요소를 두 번 사용하지 않도록 해야 하며, 해시맵에 현재 요소를 저장하기 전에 보수를 먼저 확인해야 합니다.

  def two_sum(nums, target):
      # 해시맵에 값과 인덱스 저장
      hashmap = {}
      for i, num in enumerate(nums):
          complement = target - num
          if complement in hashmap:
              return [hashmap[complement], i]
          hashmap[num] = i
      return []  # 문제 조건상 항상 존재

• 연결 리스트에서 사이클을 탐지하세요.
  좋은 답변이 다루는 것

  • 플로이드의 토끼와 거북이 알고리즘 (빠른 포인터, 느린 포인터)
  • O(n) 시간, O(1) 공간
  • 예외 처리 (빈 리스트, 단일 노드)
  • 사이클 진입점 찾기 확장
  • 해시셋 사용법과의 비교

  샘플 답변 보기

  연결 리스트에서 사이클을 탐지하는 가장 메모리 효율적인 방법은 플로이드의 순환 탐지 알고리즘입니다. 두 포인터 slow와 fast를 사용하여 slow는 한 칸씩, fast는 두 칸씩 이동합니다. 만약 fast가 None에 도달하면 사이클이 없는 것이고, slow와 fast가 만나면 사이클이 존재합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 해시셋을 사용한 방법은 O(n) 공간이 필요하지만 더 직관적입니다. 주의할 점은 fast가 next가 있는지 확인하는 것입니다. 사이클의 시작점을 찾으려면, 만난 지점에서 slow를 head로 옮기고 두 포인터를 같은 속도로 이동시키면 됩니다.

  class ListNode:
      def __init__(self, x):
          self.val = x
          self.next = None
  
  def has_cycle(head):
      if not head or not head.next:
          return False
      slow = head
      fast = head.next
      while slow != fast:
          if not fast or not fast.next:
              return False
          slow = slow.next
          fast = fast.next.next
      return True

• 반복 문자가 없는 가장 긴 부분 문자열을 찾으세요.
  좋은 답변이 다루는 것

  • 슬라이딩 윈도우와 해시맵/셋
  • O(n) 시간 복잡도
  • 왼쪽 포인터 이동 조건
  • 문자 인덱스 저장 갱신
  • 아스키 vs 유니코드 문자 처리

  샘플 답변 보기

  가장 효율적인 방법은 슬라이딩 윈도우와 해시맵을 사용하는 것입니다. 두 포인터 left와 right를 사용하여 right로 문자열을 확장하면서 각 문자의 마지막 인덱스를 해시맵에 저장합니다. 만약 현재 문자가 이미 해시맵에 있고 left보다 크거나 같은 인덱스에 있다면, left를 해당 인덱스+1로 이동시켜 중복을 제거합니다. 매 단계마다 윈도우 길이를 갱신합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(min(m, n))로 m은 문자 집합 크기입니다. 주의할 점은 left를 이동할 때 기존 문자를 삭제하지 않고 인덱스 비교로 처리하는 것입니다.

  def length_of_longest_substring(s: str) -> int:
      # 해시맵에 문자와 인덱스 저장
      char_index = {}
      left = 0
      max_len = 0
      for right, ch in enumerate(s):
          if ch in char_index and char_index[ch] >= left:
              left = char_index[ch] + 1
          char_index[ch] = right
          max_len = max(max_len, right - left + 1)
      return max_len

• 이진 트리의 레벨 순서(BFS) 순회를 수행하세요.
  좋은 답변이 다루는 것

  • 큐를 사용한 BFS
  • 각 레벨별로 리스트 구분
  • 시간 O(n), 공간 O(n)
  • 재귀적 DFS와의 비교
  • 이진 트리 레벨 순서의 응용

  샘플 답변 보기

  레벨 순서 순회는 큐를 사용하여 BFS로 구현합니다. 루트 노드를 큐에 넣고, 큐가 빌 때까지 반복합니다. 각 레벨마다 현재 큐의 크기만큼 노드를 처리하여 같은 레벨의 노드를 리스트에 저장하고, 자식 노드를 큐에 추가합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 재귀적 DFS로도 가능하지만, 레벨을 추적해야 합니다. 주의할 점은 레벨별로 구분하기 위해 반복문 내에서 큐 크기를 미리 저장해야 합니다.

  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  
  def level_order(root):
      if not root:
          return []
      result = []
      queue = [root]
      while queue:
          level_size = len(queue)
          level = []
          for _ in range(level_size):
              node = queue.pop(0)
              level.append(node.val)
              if node.left:
                  queue.append(node.left)
              if node.right:
                  queue.append(node.right)
          result.append(level)
      return result

• 그리드에서 섬의 개수(BFS/DFS).
  좋은 답변이 다루는 것

  • DFS 또는 BFS로 연결된 육지 탐색
  • 방문 표시 (in-place 수정 또는 별도 배열)
  • 시간 O(m*n), 공간 O(min(m,n)) (BFS 큐) 또는 O(m*n) (DFS 재귀)
  • 그래프 탐색의 기본 패턴
  • 행렬 경계 조건 처리

  샘플 답변 보기

  그리드에서 섬의 개수를 찾는 문제는 DFS 또는 BFS로 해결할 수 있습니다. 모든 셀을 순회하면서 '1'을 발견하면 섬 카운트를 증가시키고, 해당 위치에서 DFS/BFS로 연결된 모든 '1'을 방문 처리합니다. 방문 처리는 그리드 값을 '0'으로 변경하거나 별도의 방문 배열을 사용합니다. 시간 복잡도는 O(m*n)이며, 각 셀을 한 번씩 방문합니다. 공간 복잡도는 DFS 재귀의 경우 최악의 경우 O(m*n) 스택, BFS는 큐의 크기가 O(min(m,n))입니다. 주의할 점은 경계를 벗어나지 않도록 조건을 확인하는 것입니다.

  def num_islands(grid):
      if not grid:
          return 0
      rows, cols = len(grid), len(grid[0])
      count = 0
      
      def dfs(r, c):
          # 범위 밖이거나 물이면 리턴
          if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
              return
          grid[r][c] = '0'  # 방문 표시 (섬을 물로 변경)
          dfs(r + 1, c)
          dfs(r - 1, c)
          dfs(r, c + 1)
          dfs(r, c - 1)
      
      for i in range(rows):
          for j in range(cols):
              if grid[i][j] == '1':
                  count += 1
                  dfs(i, j)
      return count

• 계단 오르기 / 동전 교환(기본 동적 프로그래밍).
  좋은 답변이 다루는 것

  • 점화식 f(n) = f(n-1) + f(n-2)
  • 기본 DP, 피보나치 수열과 동일
  • 공간 최적화 (O(1))
  • 시간 O(n)
  • 재귀와 메모이제이션 비교

  샘플 답변 보기

  계단 오르기 문제는 전형적인 동적 프로그래밍 문제로, n번째 계단에 도달하는 방법의 수는 n-1번째와 n-2번째 계단에서 오는 방법의 합입니다. 즉, f(n) = f(n-1) + f(n-2)이며, 기본 조건은 f(1)=1, f(2)=2입니다. 이를 반복문을 사용하여 상향식으로 계산하면 시간 복잡도 O(n), 공간 복잡도 O(1)로 해결할 수 있습니다. 재귀 + 메모이제이션도 가능하지만 추가 공간이 필요합니다. 주의할 점은 n이 매우 클 경우 정수 오버플로우를 고려해야 하지만, 파이썬은 자동 처리됩니다.

  def climb_stairs(n: int) -> int:
      if n <= 2:
          return n
      prev2, prev1 = 1, 2  # f(1), f(2)
      for _ in range(3, n + 1):
          current = prev1 + prev2
          prev2 = prev1
          prev1 = current
      return prev1

준비 방법

• 문제가 아닌 패턴을 배우세요 — 대부분의 질문은 몇 가지 템플릿에 매핑됩니다.
• 항상 시간 및 공간 복잡도를 언급하고, 무차별 대입 방식이라면 더 나은 접근 방식을 찾으세요.
• 코딩 전에 계획을 설명하고, 마지막에 작은 예제로 테스트하세요.
• 자동 완성 없는 화이트보드나 일반 편집기에서 버그 없는 코드를 작성하는 연습을 하세요.

자주 묻는 질문