Skip to content

Week4

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

Week4

readme.md

파일명 분류 설명
combinations.py 알고리즘 순서에 상관없이 주어진 원소들 중에서 특정 개수(k)를 뽑는 모든 '조합(Combination)'을 찾는 방법을 백트래킹으로 구현합니다. 재귀 호출 시 다음 탐색 시작점을 현재 인덱스 다음으로 넘겨주어, 한 번 고려했던 원소는 다시 보지 않는 방식으로 중복을 효과적으로 제거합니다.
generate_parentheses.py 알고리즘 n개의 괄호 쌍으로 만들 수 있는 모든 '유효한' 괄호 조합을 생성하는 문제를 백트래킹으로 해결합니다. '여는 괄호는 n개까지만 추가'하고, '닫는 괄호는 현재까지 사용된 여는 괄호 수보다 많지 않을 때만 추가'한다는 두 가지 단순한 규칙(제약 조건)을 통해 유효한 조합만을 효율적으로 찾아냅니다.
knights_tour.py 알고리즘 체스판의 나이트(Knight)가 모든 칸을 정확히 한 번씩만 방문하는 경로를 찾는 고전적인 '나이트의 경로' 문제를 백트래킹으로 해결합니다. 현재 위치에서 나이트가 이동할 수 있는 8가지 경로를 탐색하고, 막다른 길에 도달하면 이전 선택으로 돌아가 다른 경로를 시도하는 과정을 반복합니다.
n_queens.py 알고리즘 백트래킹의 대표적인 예제인 N-Queens 문제를 풉니다. N x N 체스판에 N개의 퀸을 서로 공격할 수 없도록(같은 행, 열, 대각선에 위치하지 않도록) 배치하는 모든 경우의 수를 찾습니다. 각 행에 퀸을 하나씩 놓아보며, 유효한 위치가 아니면 이전 행으로 돌아가 퀸의 위치를 재조정하는 과정을 보여줍니다.
permutations.py 알고리즘 주어진 원소들의 순서를 바꿔 만들 수 있는 모든 경우의 수, 즉 '순열(Permutation)'을 찾는 알고리즘을 백트래킹으로 구현합니다. 각 숫자의 사용 여부를 boolean 배열 등으로 기록하여, 이미 순열에 포함된 숫자는 다시 사용하지 않도록 제어하는 것이 핵심입니다.
phone_letter_combinations.py 알고리즘 전화번호 키패드에 매핑된 숫자 문자열(예: "23")이 주어졌을 때, 만들 수 있는 모든 문자 조합("ad", "ae", "af"...)을 찾는 문제를 백트래킹으로 해결합니다. 각 숫자 자리에 해당하는 문자들 중 하나를 선택하고, 다음 자리로 넘어가 동일한 과정을 반복하는 재귀 구조를 보여줍니다.
subset_sum.py 알고리즘 주어진 숫자 집합의 부분집합 중, 그 합이 특정 목표값(target)과 같아지는 경우가 있는지 확인하는 '부분집합 합' 문제를 백트래킹으로 풉니다. 각 숫자를 부분집합에 '포함하는 경우'와 '포함하지 않는 경우'로 나누어 재귀적으로 탐색하며, 합이 목표값을 초과하면 더 이상 탐색하지 않는 '가지치기'를 통해 효율을 높입니다.
subsets.py 알고리즘 어떤 집합의 원소들로 만들 수 있는 모든 부분집합을 구하는 문제를 백트래킹으로 해결합니다. 각 원소에 대해 '포함한다'와 '포함하지 않는다'는 두 가지 선택을 재귀적으로 반복하며, 탐색 과정에서 만들어지는 모든 중간 결과가 각각 하나의 부분집합이 되는 원리를 보여줍니다.
sudoku_solver.py 알고리즘 9x9 스도쿠 퍼즐을 푸는 알고리즘을 백트래킹으로 구현합니다. 빈칸을 찾아 1부터 9까지의 숫자를 넣어본 뒤, 스도쿠 규칙(가로, 세로, 3x3 박스 중복 금지)에 맞으면 다음 빈칸으로 넘어가고, 막다른 길에 다다르면 이전 선택을 취소하고 다른 숫자를 시도하는 과정을 통해 해를 찾습니다.
word_search.py 알고리즘 2차원 문자 격자 안에서 상하좌우로 인접한 문자들을 이어 특정 단어를 만들 수 있는지 확인하는 문제를 DFS와 백트래킹으로 해결합니다. 한 번 사용한 칸은 다시 방문하지 못하도록 임시로 표시하고, 탐색이 끝나면 원래대로 복원하는 백트래킹의 핵심적인 과정을 보여줍니다.