프루닝(Pruning)의 활용 방법

♦️백트래킹(Backtracking)에 활용

모든 경우를 탐색하지만, 가능성이 없는 경로는 미리 포기한다. 쓸데없는 재귀 호출을 줄여서 속도를 높일 수 있다.

 

예시 문제 [N-Queen] : N×N 체스판에 N개의 퀸을 놓을 수 있는 경우의 수를 구하라. 단, 퀸은 같은 행, 열, 대각선에 놓일 수 없다.

 

1. 백트래킹

• 한 줄씩 퀸을 배치하면서 모든 가능한 경우를 탐색
• 만약 조건을 만족하지 않으면 즉시 탐색을 중단 (Pruning)

2. 프루닝

• 같은 열이나 같은 대각선에 퀸이 있으면 가지치기!

def is_safe(row, col, queens):
    """현재 (row, col)에 놓을 수 있는지 체크"""
    for r, c in enumerate(queens):  # 이전에 놓은 퀸들의 위치
        if c == col or abs(r - row) == abs(c - col):
            # 같은 열 or 같은 대각선에 퀸이 있으면 배치 불가능
            return False
    return True


def backtrack(n, row, queens):
    """백트래킹으로 모든 경우 탐색하며 퀸 배치"""
    if row == n:  # 모든 퀸을 배치 완료한 경우
        return 1

    count = 0
    for col in range(n):  # 현재 행의 모든 열에 퀸 놓아보기
        if is_safe(row, col, queens):  # Pruning: 배치 가능한 경우에만 진행
            queens.append(col)
            count += backtrack(n, row + 1, queens)  # 다음 행으로 이동(재귀 호출)
            queens.pop()  # 되돌리기(백트래킹)

    return count


def solve_n_queens(n):
    return backtrack(n, 0, [])  # 0번째 행부터 시작


print(solve_n_queens(8))

 

 

 

♦️DP에 활용

예시 문제: 피보나치 수열

 

📍Pruning 없이 계산했을 때

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)  # 중복 계산 발생

문제점: 같은 값을 여러 번 계산해서 시간 초과가 발생할 수 있음.

 

📍 Pruning + 메모이제이션 사용

memo = {}


def fibonacci(n):
    if n == 0 or n == 1:
        return n
    if n in memo:  # Pruning: 이미 계산된 값이면 다시 계산하지 않음
        return memo[n]

    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]


print(fibonacci(50))  # O(n)으로 해결 가능!