Coding Interview Prep · 강의

N-퀸과 제약 전파

Q: “N-퀸과 제약 전파” 강의는 무료인가요?

네 — “N-퀸과 제약 전파” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

Q: “N-퀸과 제약 전파” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

열 집합과 대각선 집합을 사용해 O(1) 시간에 제약을 확인하면서 N×N 체스판에 N개의 퀸을 배치하고, 해를 세는 것과 열거하는 것의 차이를 살펴봅니다.

N-퀸과 제약 전파은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

N-퀸 문제

N-퀸 문제(LeetCode 51/52)는 N×N 체스판에 서로 공격할 수 없는 N개의 퀸을 배치하는 문제입니다. 퀸은 행, 열, 양쪽 대각선 방향으로 공격합니다. N=4일 때 해는 정확히 2개입니다. 고전적인 버전인 N=8에서는 해가 92개입니다. 이 문제는 제약 조건 확인을 통해 탐색 공간을 크게 줄이는 대표적인 백트래킹 문제입니다.

# N-Queens constraints:
# 1. Exactly one queen per row
# 2. No two queens in the same column
# 3. No two queens on the same diagonal (top-left to bottom-right)
# 4. No two queens on the same anti-diagonal (top-right to bottom-left)

# For N=4, the 2 solutions:
sol1 = ['.Q..', '...Q', 'Q...', '..Q.']
sol2 = ['..Q.', 'Q...', '...Q', '.Q..']
print('N=4 solutions:')
for row in sol1: print(row)
print()
for row in sol2: print(row)

행마다 퀸 하나 배치

두 퀸이 같은 행을 공유할 수 없으므로 행마다 정확히 하나의 퀸을 배치합니다. 백트래킹은 행별로 재귀 호출을 수행하면서 각 행의 열을 선택합니다. 이렇게 하면 퀸 하나당 N²개의 선택지를 고려하는 대신 행마다 N개의 열만 고려하게 되어, 시작 분기는 N^N개가 됩니다. 하지만 제약 조건이 이 수를 크게 줄입니다. 재귀 깊이는 N이고(행마다 한 수준), 분기 수는 최대 N입니다.

def solve_n_queens(n):
    results = []
    queens = []  # queens[row] = column of queen in that row
    
    def backtrack(row):
        if row == n:
            # Build the board representation
            board = []
            for r in range(n):
                board.append('.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1))
            results.append(board)
            return
        for col in range(n):
            if is_valid(row, col):
                queens.append(col)   # CHOOSE
                backtrack(row + 1)   # EXPLORE
                queens.pop()         # UNCHOOSE
    
    def is_valid(row, col):
        for r, c in enumerate(queens):
            if c == col: return False             # same column
            if abs(row - r) == abs(col - c): return False  # diagonal
        return True
    
    backtrack(0)
    return results

print(len(solve_n_queens(4)), 'solutions for N=4')  # 2
print(len(solve_n_queens(8)), 'solutions for N=8')  # 92

집합을 이용한 O(1) 제약 조건 확인

배치된 모든 퀸을 순회하여 유효성을 확인하면 후보 하나마다 O(N)이 걸리므로 최악의 경우 전체 알고리즘은 O(N² × N!)이 됩니다. 세 집합을 유지하면 각 유효성 확인을 O(1)로 줄일 수 있습니다. cols는 점유된 열을, diag는 왼쪽 위 대각선의 행-열 값을, anti_diag는 오른쪽 위 대각선의 행+열 값을 저장합니다. 같은 대각선에 있는 퀸은 동일한 행-열 값을 공유하고, 같은 반대각선에 있는 퀸은 동일한 행+열 값을 공유합니다.

def solve_n_queens_fast(n):
    results = []
    cols = set()       # occupied columns
    diag = set()       # row - col (positive diagonal)
    anti = set()       # row + col (negative diagonal)
    queens = []
    
    def backtrack(row):
        if row == n:
            board = ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
            results.append(board)
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue  # PRUNE: constraint violated
            # CHOOSE
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            backtrack(row + 1)  # EXPLORE
            # UNCHOOSE
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    
    backtrack(0)
    return results

print(len(solve_n_queens_fast(8)))  # 92

대각선 불변식 설명

대각선에 관한 핵심 관찰은 다음과 같습니다. 왼쪽 위에서 오른쪽 아래로 이어지는 같은 대각선의 모든 칸은 row - col 값이 같습니다. 예를 들어 (0,0), (1,1), (2,2)는 모두 row-col=0입니다. 같은 반대각선의 모든 칸은 row + col 값이 같습니다. (0,2), (1,1), (2,0)는 모두 row+col=2입니다. 이러한 상수 시간 불변식을 사용하면 O(N) 선형 순회 대신 O(1) 집합 조회로 대각선 충돌을 확인할 수 있습니다.

# Visualise the diagonal invariants for a 4x4 board
n = 4
print('row-col values (same diagonal):')
for r in range(n):
    print([r-c for c in range(n)])

print('row+col values (same anti-diagonal):')
for r in range(n):
    print([r+c for c in range(n)])

# Verify: (0,0) and (2,2) share diag value 0
print('(0,0) diag:', 0-0, '| (2,2) diag:', 2-2)  # both 0
# Verify: (0,2) and (2,0) share anti-diag value 2
print('(0,2) anti:', 0+2, '| (2,0) anti:', 2+0)  # both 2

해 개수 세기: N-퀸 II

N-퀸 II(LeetCode 52)는 체스판을 반환하지 않고 해의 개수만 묻습니다. 따라서 체스판을 구성하는 단계를 건너뛰고 카운터만 증가시키는 방식으로 조금 최적화할 수 있습니다. 집합 대신 비트 마스크를 사용하면 연산당 시간을 O(1)에 가깝게 더 줄일 수 있습니다. 해의 개수는 단조롭게 증가하지 않습니다. 1(N=1), 0(N=2), 0(N=3), 2(N=4), 10(N=5), 4(N=6), 40(N=7), 92(N=8)입니다.

def total_n_queens(n):
    count = [0]
    cols = set(); diag = set(); anti = set()
    def backtrack(row):
        if row == n:
            count[0] += 1
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            backtrack(row + 1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col)
    backtrack(0)
    return count[0]

for n in range(1, 11):
    print(f'N={n}: {total_n_queens(n)} solutions')

속도를 위한 비트 마스크 N-퀸

매우 큰 N에서는 비트 마스크 구현이 훨씬 빠르게 실행됩니다. 세 정수를 비트 마스크로 사용합니다. cols, 각 행마다 왼쪽으로 이동하는 left_diag, 오른쪽으로 이동하는 right_diag입니다. 사용 가능한 열은 ((1<<n)-1) & ~(cols|left_diag|right_diag)로 구합니다. 각 사용 가능한 열을 bit = available & -available로 추출한 다음 재귀 호출을 수행합니다. 비트 연산을 사용하므로 제약 조건 확인을 연산당 O(1)에 수행할 수 있습니다.

def total_n_queens_bitmask(n):
    full = (1 << n) - 1  # all n columns set
    count = [0]
    def bt(cols, left_diag, right_diag):
        if cols == full:
            count[0] += 1
            return
        available = full & ~(cols | left_diag | right_diag)
        while available:
            bit = available & -available  # lowest set bit
            available &= available - 1   # remove lowest bit
            bt(cols | bit,
               (left_diag | bit) << 1,
               (right_diag | bit) >> 1)
    bt(0, 0, 0)
    return count[0]

for n in range(1, 13):
    print(f'N={n}: {total_n_queens_bitmask(n)}')

제약 전파 개념

제약 전파는 단순한 가지치기를 넘어섭니다. 퀸 하나를 배치한 후, 이후 행의 유효하지 않은 위치를 모두 즉시 추론하여 제거합니다. 이는 각 후보에서 유효성을 확인하는 것보다 더 적극적인 방식입니다. 분기하기 전에 검색 공간을 선제적으로 좁히기 때문입니다. 가장 유명한 예로 SAT 풀이기와 스도쿠 풀이기에서의 아크 일관성을 들 수 있습니다. 한 숫자를 배치하면 같은 행, 열, 3×3 상자에서 선택지를 제거합니다.

# Constraint propagation in Sudoku:
# After placing 5 in cell (0,0):
# - Row 0: no other cell can have 5
# - Column 0: no other cell can have 5
# - Box (0,0)-(2,2): no other cell can have 5
# This is propagated BEFORE branching further

# Simple demo: remaining valid columns after placing queens
def remaining_columns(n, queens):
    cols = set(q for q in queens)
    diags = set(r - q for r, q in enumerate(queens))
    anti_diags = set(r + q for r, q in enumerate(queens))
    row = len(queens)
    return [c for c in range(n)
            if c not in cols
            and (row-c) not in diags
            and (row+c) not in anti_diags]

print(remaining_columns(8, [0]))  # valid cols for row 1 after placing col 0 in row 0

스도쿠 풀이기

스도쿠는 제약 전파의 대표적인 문제입니다. 각 빈 칸에서 선택할 수 있는 유효한 숫자는 같은 행, 열 또는 3×3 상자에 이미 없는 숫자입니다. 백트래킹 풀이기는 첫 번째 빈 칸을 찾고, 각 유효한 숫자를 시도한 뒤 재귀 호출합니다. 모순에 도달하면(유효한 숫자가 없는 빈 칸이 생기면) backtrack을 수행합니다. 좋은 스도쿠 풀이기는 백트래킹을 수행하기 전에 제약 전파(후보 표시)도 적용합니다.

def solve_sudoku(board):
    def is_valid(r, c, num):
        for i in range(9):
            if board[r][i] == num: return False  # row
            if board[i][c] == num: return False  # col
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                if board[br+i][bc+j] == num: return False  # box
        return True
    
    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for d in '123456789':
                        if is_valid(r, c, d):
                            board[r][c] = d
                            if backtrack(): return True
                            board[r][c] = '.'
                    return False  # no valid digit found
        return True  # no empty cells: solved
    
    backtrack()
    return board

# Mini test with a solvable board (simplified)
print('Sudoku solver implemented')

가장 제약된 변수 휴리스틱

제약 만족 문제를 위한 핵심 최적화 방법은 가장 제약된 변수(유효한 선택지가 가장 적은 칸)를 항상 다음 변수로 선택하는 것입니다. 스도쿠에서 어떤 칸에 유효한 숫자가 하나만 있다면 즉시 채워야 하므로 백트래킹이 필요하지 않습니다. 이런 칸을 먼저 선택하면 검색 트리의 깊이를 크게 줄일 수 있습니다. 이는 인공지능 제약 프로그래밍에서 사용하는 최소 잔여 값(MRV) 휴리스틱입니다.

def solve_sudoku_mrv(board):
    '''Find cell with fewest valid choices (MRV heuristic).'''
    def valid_choices(r, c):
        nums = set('123456789')
        for i in range(9):
            nums.discard(board[r][i])
            nums.discard(board[i][c])
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                nums.discard(board[br+i][bc+j])
        return nums
    
    def find_mrv():
        best = (10, -1, -1, set())  # (choices_count, r, c, choices)
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    choices = valid_choices(r, c)
                    if len(choices) < best[0]:
                        best = (len(choices), r, c, choices)
        return best[1], best[2], best[3]
    
    def backtrack():
        r, c, choices = find_mrv()
        if r == -1: return True  # no empty cells
        for d in choices:
            board[r][c] = d
            if backtrack(): return True
            board[r][c] = '.'
        return False
    
    backtrack()
    return board

N-퀸 해 개수 표

N-퀸 해의 개수는 다음과 같이 잘 알려진 수열을 따릅니다. N=1: 1, N=2: 0, N=3: 0, N=4: 2, N=5: 10, N=6: 4, N=7: 40, N=8: 92, N=9: 352, N=10: 724입니다. 알려진 닫힌 형태의 공식은 없으므로 개수를 계산해야 합니다. N=27에서는 약 2.34 × 10^17개의 해가 존재합니다. 면접 문제에서는 일반적으로 N ≤ 9를 요구합니다. 지수적 증가를 이해하면 더 큰 N에서 비트 마스크 최적화가 중요한 이유를 알 수 있습니다.

def count_queens(n):
    '''O(1) per constraint check using sets.'''
    count = [0]
    cols = set(); diag = set(); anti = set()
    def bt(row):
        if row == n: count[0] += 1; return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            bt(row+1)
            cols.discard(col); diag.discard(row-col); anti.discard(row+col)
    bt(0)
    return count[0]

sequence = [count_queens(n) for n in range(1, 12)]
print('N-Queens counts:', sequence)
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]

N-퀸 보드 구성

면접관이 실제 보드를 반환하라고 요청하는 경우(LeetCode 51), queens 목록에서 각 보드를 구성합니다. 여기서 queens[r]는 r행에 있는 퀸의 열입니다. 문자열 구성은 각 행에 대해 '.' * col + 'Q' + '.' * (n - col - 1)을 사용하는 방식입니다. 이 O(n²) 구성은 재귀 트리의 단말 노드(N개의 퀸을 모두 배치한 시점)에서만 호출되므로 전체 복잡도에는 영향을 주지 않습니다.

def n_queens_boards(n):
    results = []
    queens = []
    cols = set(); diag = set(); anti = set()
    def build_board():
        return ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
    def bt(row):
        if row == n:
            results.append(build_board())
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            bt(row+1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    bt(0)
    return results

for board in n_queens_boards(4):
    for row in board: print(row)
    print()

빠른 확인

이 단원에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 이해했는지 test해 보십시오.

학습 내용 복습

이 단원에서는 다음을 배웠습니다. N-퀸은 행마다 퀸 하나를 배치하고, 열과 대각선(행-열), 반대 대각선(행+열)에 집합을 사용하여 O(1) 제약 확인을 수행합니다. 또한 비트 마스크를 사용하면 제약 확인을 더욱 빠르게 수행할 수 있고, 배치 탐색을 연산당 거의 O(1)에 수행할 수 있습니다. 그리고 제약 전파(MRV 휴리스틱)는 가장 제약된 변수를 항상 다음에 선택하여 검색을 줄입니다. 다음에는 탐욕법과 DP 접근법을 비교하고 각각을 언제 적용해야 하는지 알아봅니다.

자주 묻는 질문