⚙️ 알고리즘/코딩테스트 준비
[알고리즘] 백트래킹 유형 정리
dev_zoe
2023. 7. 13. 15:44
반응형
백트래킹 문제 풀때 유형별 풀이가 너무 헷갈려서 정리하는 포스팅
1. 단순 순열(순서가 다르면 겹치는게 있어도 다른 케이스로 간주, ab != ba)
- 모든 케이스를 다 돌기는 해야하는데, 현재 루프에서 이미 방문한 노드는 제외해야할 때
- 1부터 9를 중복없이 채운다는 전제하에 1 9 와 9 1은 다른 케이스일 수 밖에 없음. 여기에 행/열/사각형에 중복이 없는지에 대한 조건 추가하는 응용만 제외하면 아래 원리와 동일
알고리즘 틀
// 구현해놓은 Permutation 연습
func permute(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
var result = [[Int]]()
var visited = [Bool](repeating: false, count: nums.count)
func permutation(_ nowPermute: [Int]) {
if nowPermute.count == targetNum {
result.append(nowPermute)
return
}
for i in 0..<nums.count {
if visited[i] == false {
visited[i] = true
permutation(nowPermute + [nums[i]])
visited[i] = false
}
}
}
permutation([])
return result
}
2. 단순 조합(겹치는 순간 같은 케이스로 간주, ab = ba)
- 뽑는 수에 중복이 없다는 것이 공통적
알고리즘 틀
func combi(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
var result = [[Int]]()
func combination(_ index: Int, _ nowCombi: [Int]) {
if nowCombi.count == targetNum {
result.append(nowCombi)
return
}
for i in index..<nums.count {
combination(i + 1, nowCombi + [nums[i]])
}
}
combination(0, [])
return result
}
반응형