[코딩 테스트] 11일차: 재귀와 백트래킹

재귀 (Recursion)

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 재귀 함수는 하나 이상의 종료 조건(Base Case)과 자기 자신을 호출하는 재귀 단계(Recursive Case)를 포함합니다.

재귀 함수의 주요 개념

• 기저 조건(Base Case): 재귀 호출을 멈추는 조건
• 재귀 단계(Recursive Case): 함수를 반복적으로 호출하는 단계

예제: 재귀를 이용한 팩토리얼 계산

JavaScript

function factorial(n) {
  if (n === 0) {
    return 1; // 기저 조건
  }
  return n * factorial(n - 1); // 재귀 단계
}

console.log(factorial(5)); // 120

Python

def factorial(n):
    if n == 0:
        return 1 # 기저 조건
    return n * factorial(n - 1) # 재귀 단계

print(factorial(5)) # 120

예제: 재귀를 이용한 피보나치 수열

JavaScript

function fibonacci(n) {
  if (n <= 1) {
    return n; // 기저 조건
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 단계
}

console.log(fibonacci(6)); // 8

Python

def fibonacci(n):
    if n <= 1:
        return n # 기저 조건
    return fibonacci(n - 1) + fibonacci(n - 2) # 재귀 단계

print(fibonacci(6)) # 8

백트래킹 (Backtracking)

백트래킹은 가능한 모든 경우를 탐색하며 해를 찾는 방법입니다. 주로 재귀를 사용하여 문제를 해결하며, 조건을 만족하지 않으면 이전 단계로 되돌아가 다른 경로를 탐색합니다.

백트래킹의 주요 개념

• 상태 공간 트리(State Space Tree): 모든 가능한 상태를 트리 구조로 표현
• 가지치기(Pruning): 조건을 만족하지 않는 경로를 제거

예제: N-Queens 문제

JavaScript

function solveNQueens(n) {
  let result = [];
  let board = new Array(n).fill().map(() => new Array(n).fill('.'));

  function isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
      if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;
      if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;
    }
    return true;
  }

  function solve(row) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 'Q';
        solve(row + 1);
        board[row][col] = '.';
      }
    }
  }

  solve(0);
  return result;
}

console.log(solveNQueens(4));

Python

def solve_n_queens(n):
    result = []
    board = [["."] * n for _ in range(n)]

    def is_safe(row, col):
        for i in range(row):
            if board[i][col] == "Q":
                return False
            if col - (row - i) >= 0 and board[i][col - (row - i)] == "Q":
                return False
            if col + (row - i) < n and board[i][col + (row - i)] == "Q":
                return False
        return True

    def solve(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = "Q"
                solve(row + 1)
                board[row][col] = "."

    solve(0)
    return result

print(solve_n_queens(4))

예제: 부분 집합 구하기

JavaScript

function subsets(nums) {
  let result = [];

  function backtrack(start, path) {
    result.push([...path]);

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

console.log(subsets([1, 2, 3]));

Python

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(list(path))

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))

연습 문제

문제 1: 수열의 모든 순열 구하기

주어진 수열의 모든 순열을 구하는 프로그램을 작성하세요.

JavaScript

function permute(nums) {
  let result = [];

  function backtrack(path, used) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      path.push(nums[i]);
      used[i] = true;
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([], Array(nums.length).fill(false));
  return result;
}

console.log(permute([1, 2, 3]));

Python

def permute(nums):
    result = []

    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(list(path))
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            path.append(nums[i])
            used[i] = True
            backtrack(path, used)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

print(permute([1, 2, 3]))

문제 2: 조합 구하기

주어진 수열에서 길이가 k인 모든 조합을 구하는 프로그램을 작성하세요.

JavaScript

function combine(n, k) {
  let result = [];

  function backtrack(start, path) {
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(1, []);
  return result;
}

console.log(combine(4, 2));

Python

def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(list(path))
            return

        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combine(4, 2))

결론

이번 글에서는 코딩 테스트 준비를 위해 재귀와 백트래킹에 대해 배웠습니다. 이를 통해 재귀 함수의 개념과 예제, 백트래킹의 개념과 예제를 익힐 수 있었습니다. 다음 글에서는 그래프 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!