깜작 스낵 알고리즘! - 백트래킹

김재형_LittleTale·2025년 8월 19일

들어가기에 앞서

사실 알고리즘을 블로그 글을
핀 레이아웃편을 준비 하고 있었는데
준비하면서 알고리즘도 같이 공부 하고 있었습니다.
이때 백트래킹이 정말 인상 깊었어서 잠깐 다루는 시간을 갖도록 하겠습니다.

백트래킹

사전적으로는
"가능한 해를 점진적으로 찾다가 해가 아니라면 되돌아가는 깊이 우선 탐색 + 가지치기 기법이다."
라고 정의가 되어 있기는 합니다.
사실 말로만 들으면 뭔말인지 저어어언혀 이해가 안갔어요 저는
저는 이정의를 좀더 심플하게 정의 해보고자 합니다.
반복해서 해를 찾는데 아니다 싶으면 되돌리기

예시 문제

백준 문제에서 괜찮다 싶은 문제 2개를 가져와 보았습니다.

N과 M 6번째 문제

문제: N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는
길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

N개의 자연수는 모두 다른 수이다.

N개의 자연수 중에서 M개를 고른 수열은 오름차순이어야 한다.

예시 입력

3 1
4 5 2

예시 출력

2
4
5

위에서 언급했다 싶이 조건을 만들고 조건이 맞다 싶으면 결과를 쌓을것이며 아니다 싶으면 돌아 가겠습니다.

let nm = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nm[0] // 총 갯수
let m = nm[1] // 고를수있는 갯수

let numbers = readLine()!.split(separator: " ").map { Int($0)! }.sorted()
var visited = Array(repeating: false, count: n)
var temp: [Int] = []
var answer: String = ""


func solution(start: Int) {
    if temp.count == m {
        answer += temp.map{ String($0) }.joined(separator: " ") + "\n"
        return
    }
    
    for i in start..<n {
        temp.append(numbers[i])
        solution(start: i + 1)
        temp.removeLast()
    }
}

solution(start: 0)
print(answer, terminator: "")

코드를 유심히 보시면
솔류션 함수에서 숫자를 검사합니다. 길이가 m과 같은지
같다면 돌아가는 형태죠?

그아래에 for문을 보시면
솔류션 함수를 다시 호출하고 있습니다.
재귀 함수구나! 를 접근이 가능하죠

이말은 즉 1,2,3,4,5 가 있다면 1,2,3,4,5 - 1,2,3,5,4.... 같이 모오든 경우의 수를 다 보겠다 라는 의미입니다.

로또 문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.
로또 번호를 선택하는데 사용되는 가장 유명한 전략은

49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우
이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

해당 문제는 위 문제보다 좀더 백트래킹에 대해 이해 할수 있을것 같아서 가져와 보았습니다.

var text: String = ""

while true {
    let numbers = readLine()!.split(separator: " ").map { Int($0)! }
    let k = numbers[0]
    if k == 0 {
        break
    } else if !text.isEmpty {
        text += "\n"
    }
    let lottoNumbers = Array(numbers[1...])
    var temp: [Int] = []
    solution(originalNumbers: lottoNumbers, current: &temp, start: 0, text: &text)
}

func solution(originalNumbers: [Int], current: inout [Int], start: Int, text: inout String) {
    if current.count == 6 {
        text += current.map { String($0) }.joined(separator: " ") + "\n"
        return
    }
    
    for i in start..<originalNumbers.count {
        current.append(originalNumbers[i])
        solution(originalNumbers: originalNumbers, current: &current, start: i + 1, text: &text)
        current.removeLast()
    }
}

print(text, terminator: "")