이번 커밋에서는 알고리즘 스터디의 9주차 과제로 백트래킹을 활용한 두 가지 문제를 해결했습니다. N-Queens 문제와 부분집합 합 문제를 각각 `5.1.nqueens_problem.py`와 `5.4.sumofsubsets_problem.py` 파일에 구현하고 테스트 케이스를 추가했습니다.

20260512-backtracking: 백트래킹 알고리즘 구현 및 테스트

이번 커밋에서는 알고리즘 스터디의 9주차 과제로 백트래킹을 활용한 두 가지 문제를 해결했습니다. N-Queens 문제와 부분집합 합 문제를 각각 5.1.nqueens_problem.py와 5.4.sumofsubsets_problem.py 파일에 구현하고 테스트 케이스를 추가했습니다.

요약

이번 커밋은 "20260512-backtracking"이라는 메시지로 두 개의 파이썬 파일을 추가하며 진행되었습니다. N-Queens 문제와 부분집합 합 문제에 대한 백트래킹 알고리즘이 구현되었으며, 기존 코드의 변경 없이 새로운 기능이 216 라인 추가되었습니다. 작업은 2026년 5월 12일에 완료되었습니다.

배경 및 목적

알고리즘 스터디의 9주차 과제는 백트래킹 알고리즘을 이해하고 실제 문제에 적용하는 것이었습니다. N-Queens 문제는 체스 보드 위에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이며, 부분집합 합 문제는 주어진 집합에서 합이 특정 목표 값과 같은 부분집합을 찾는 문제입니다. 이 두 문제를 해결함으로써 백트래킹의 기본적인 탐색 방식과 재귀 호출을 활용한 문제 해결 능력을 향상시키는 것이 목적입니다.

구현 내용

5.1.nqueens_problem.py

이 파일에는 N-Queens 문제를 해결하기 위한 백트래킹 알고리즘이 구현되었습니다.

주요 변경사항:
- promising 함수: 현재 행에 놓인 퀸이 이전 행에 놓인 퀸들과 충돌하는지 (같은 열, 대각선) 검사하는 로직이 추가되었습니다.
- nqueens 함수: 재귀적으로 각 행에 퀸을 배치하고, promising 함수를 통해 유망한 경우에만 다음 행으로 탐색을 진행합니다. 가능한 모든 해법을 찾아 solutions 리스트에 저장합니다.
- 테스트 케이스 test_nqueens 함수가 추가되어 N=2, 4, 5, 6에 대한 결과를 검증합니다.
변경된 파일 목록:
- Week09_problem/5.1.nqueens_problem.py
추가/삭제된 코드 라인 수:
- 추가: 95 라인
- 삭제: 0 라인
핵심 코드 설명:
nqueens(i, n, col, solutions) 함수는 i번째 행에 퀸을 놓는 과정을 재귀적으로 수행합니다. promising 함수를 통해 이전 퀸들과의 충돌이 없는지 확인한 후, 충돌이 없다면 i == n인지 확인하여 해답을 찾았는지 판단합니다. 해답을 찾지 못했다면, for j in range(1, n + 1) 루프를 통해 i+1번째 행에 퀸을 j열에 놓아보고 재귀 호출합니다.

def nqueens(i, n, col, solutions):
    """모든 N-Queens 해법을 찾기 위한 재귀적 백트래킹 함수."""
    if promising(i, n, col):  # 지금까지의 배치가 괜찮을 때만 다음 단계로 간다.
        if i == n:  # n번째 행까지 모두 퀸을 놓았으면 해답 하나를 찾은 것이다.
            solutions.append(col[1:].copy())  # 현재 배치를 해답 목록에 저장한다.
            print("found=", col[1:])  # 찾은 해답을 화면에 출력한다.
        else:  # 아직 더 놓아야 할 행이 남아 있다.
            for j in range(1, n + 1):  # 다음 퀸을 1열부터 n열까지 하나씩 시도한다.
                col[i + 1] = j  # 다음 행의 퀸을 j열에 놓아본다.
                nqueens(i + 1, n, col, solutions)  # 재귀적으로 다음 행을 탐색한다.

5.4.sumofsubsets_problem.py

이 파일에는 부분집합 합 문제를 해결하기 위한 백트래킹 알고리즘이 구현되었습니다.

주요 변경사항:
- promising 함수: 현재까지의 합 weight와 남은 항목들의 총합 total을 이용하여 목표 합 W에 도달할 가능성이 있는지 판단하는 로직이 추가되었습니다.
- sumofsubsets 함수: 재귀적으로 부분집합을 구성하며, promising 함수로 가능성을 확인하고 목표 합 W에 도달하면 해답을 찾습니다.
- sumofsubsets_solver 함수: 전역 변수를 초기화하고 sumofsubsets 함수를 호출하는 헬퍼 함수입니다.
- 테스트 케이스 test_sumofsubsets 함수가 추가되어 다양한 입력에 대한 결과를 검증합니다.
변경된 파일 목록:
- Week09_problem/5.4.sumofsubsets_problem.py
추가/삭제된 코드 라인 수:
- 추가: 121 라인
- 삭제: 0 라인
핵심 코드 설명:
sumofsubsets(i, weight, total) 함수는 i번째 항목까지 고려한 상태에서 현재까지의 합 weight와 남은 항목들의 합 total을 인자로 받습니다. promising 함수를 통해 현재 상태가 유망하면, weight == W인지 확인하여 해답을 찾았는지 판단합니다. 해답을 찾지 못했다면, 다음 항목(i+1)을 포함하는 경우와 포함하지 않는 경우를 재귀적으로 탐색합니다.

def sumofsubsets(i, weight, total):
    """합이 `W`가 되는 부분집합들을 열거하는 백트래킹 함수."""
    global n, W, w, include, solutions
    if promising(i, weight, total):  # 현재 상태가 가능성 있는 경우에만 재귀를 진행한다.
        if weight == W:  # 목표 합에 정확히 도달하면 해답 하나를 찾은 것이다.
            print("found:", [w[j] for j in range(n) if include[j]])  # 선택된 수들을 출력한다.
            solutions.append([w[j] for j in range(n) if include[j]])  # 해답 목록에 저장한다.
        else:  # 아직 목표 합에 도달하지 못했으면 다음 수를 선택해 본다.
            include[i + 1] = 1  # 다음 수를 포함하는 경우를 먼저 탐색한다.
            sumofsubsets(i + 1, weight + w[i + 1], total - w[i + 1])  # 포함했을 때의 상태로 재귀 호출한다.

            include[i + 1] = 0  # 같은 위치에서 이번에는 포함하지 않는 경우를 탐색한다.
            sumofsubsets(i + 1, weight, total - w[i + 1])  # 제외했을 때의 상태로 재귀 호출한다.

배운 점 및 개선점

이번 작업을 통해 백트래킹 알고리즘의 핵심 원리를 이해하고, 재귀 호출을 사용하여 탐색 공간을 효율적으로 줄이는 방법을 익혔습니다. 특히 promising 함수를 통해 불필요한 탐색을 미리 차단하는 것이 백트래킹 성능에 중요하다는 것을 알게 되었습니다.

향후 개선할 점은 다음과 같습니다.

시간 복잡도 분석: 구현된 알고리즘의 시간 복잡도를 분석하고, 더 효율적인 알고리즘이 있는지 탐색할 필요가 있습니다.
일반화: 두 문제 모두 특정 입력에 대해 해법을 찾는 것을 목표로 했으나, 더 복잡하거나 대규모의 입력에 대해서도 잘 동작하는지 확인하고 필요시 최적화해야 합니다.
가독성 향상: 코드에 더 명확한 주석을 추가하고, 변수 이름을 좀 더 직관적으로 변경하여 가독성을 높일 수 있습니다.

다음 단계로는 백트래킹을 활용하는 다른 알고리즘 문제들을 풀어보며 적용 범위를 넓힐 계획입니다.

참고 자료

(없음)