티스토리 뷰
❗️이 글은 구종만 - 알고리즘 문제해결 전략 책을 참고하여 작성되었습니다.
📝 목차
1. 재귀 호출과 완전 탐색
2. 문제: 소풍
3. 문제: 게임판 덮기
4. 최적화 문제
5. 문제: 시계 맞추기
6. 많이 등장하는 완전 탐색 유형
알고리즘을 고안하기 위해서는 문제의 특성을 이해하고, 동작 시간과 사용하는 공간 사이의 상충 관계를 이해하여, 적절한 자료구조를 선택할 줄 알아야 한다.
알고리즘 설계 패러다임: 주어진 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점
알고리즘 문제를 풀면서 "어떻게 하면 무식하게 풀 수 있을까"에 대해 생각하는 것이 실수를 방지하는데 좋다.
"무식하게 풀기"는 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법으로 "완전 탐색"이라고 한다.
1. 재귀 호출과 완전 탐색
📍 재귀 호출
재귀 함수(재귀 호출): 수행할 작업을 유사한 형태로 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.
// 1부터 n까지의 합을 계산하는 반복 함수와 재귀 함수
// 필수 조건 n>=1
// 결과: 1부터 n까지의 합을 반환한다.
func sum(n: Int) -> Int{
var ret=0;
for i in 1...n{
ret += i
}
return ret
}// 필수 조건 n>=1
// 결과: 1부터 n까지의 합을 반환한다.
func recursiveSum(n: Int) -> Int{
if n==1 {
return 1
}
return n + recursiveSum(n: n-1)
}위의 두 코드는 1부터 n까지의 합을 반환하는 함수를 구현한 것이다.
- recursiveSum()함수는 재귀 호출을 이용해 sum()함수를 구현한 것이다.
- recursiveSum()함수를 보면 n==1일 때 1을 반환하는 것을 볼 수 있다.
=> 1이 "더 이상 쪼개지지 않는" 기저 사례이기 때문이다.
📍예제: 중첩 반복문 대체하기
0번부터 차례대로 번호 매겨진 n개의 원소 중 4개를 고르는 모든 경우를 출력하는 코드를 확인해보자.
for i in 0..<n {
for j in stride(from: i+1, through: n, by: 1){
for k in stride(from: j+1, to: n, by: 1){
for l in stride(from: k+1, to: n, by: 1){
print("\(i) \(j) \(k) \(l) ")
}
}
}
}만약 n개의 원소 중 5개를 골라야 한다면 5중 반복문을, 6개라면 6중 반복문을, 7개라면?
이렇게 점점 중첩 for문이 늘어나게 되는데 재귀 호출을 이용해 코드를 간결하고 유연하게 할 수 있다.
위 코드의 4중 반복문이 하는 작업을 4개의 조각으로 나눌 수 있다. 각 조각 별로 하나의 원소를 고른다.
원소를 고른 뒤, 남은 원소들을 고르는 작업을 자기 자신을 호출해 떠넘기는 재귀함수를 작성해보자.
남은 원소들을 고르는 '작업'을 다음과 같은 입력들의 집합으로 정의할 수 있다.
- 원소들의 총 개수
- 더 골라야 할 원소들의 개수
- 지금까지 고른 원소들의 번호
//코드 6.2 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
//n: 전체 원소의 수
//picked: 지금까지 고른 원소들의 번호
//toPick: 더 고를 원소의 수
//일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
func printPicked(_ picked: [Int]) {
for i in 0..<picked.count{
print("\(picked[i]) ")
}
}
func pick(_ n: Int, _ picked: inout [Int], _ toPick: Int) {
// 기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다.
if toPick == 0 {
printPicked(picked)
return
}
// 고를 수 있는 가장 작은 번호를 계산한다.
let smallest = picked.isEmpty ? 0 : picked.last! + 1
// 이 단계에서 원소 하나를 고른다.
for next in smallest..<n {
picked.append(next)
pick(n, &picked, toPick - 1)
picked.removeLast()
}
}
코드 6.2는 중첩 for문과 달리 우리가 n개의 원소 중에서 몇개를 고르든지 사용할 수 있다는 점이 있다.
📍 예제: 보글 게임(문제 ID: BOGGLE, 난이도: 하)
보글 게임은 밑의 그림 6.2와 같은 5×5 크기의 알파벳 격자를 가지고 하는 게임이다.
게임 목적은 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것이다.
각 글자들은 대각선으로 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있다.
주어진 칸에서 시작해 특정 단어를 찾을 수 있는지 확인하는 문제를 풀어보자.
고려해야할 점은 다음 글자가 될 수 있는 칸이 여러 개인 경우 어느 글자를 선택할 지 미리 알 수 없다는 것이다.
그림 6.2(e)에서 정가운데 칸에서 시작하는 단어 YES를 찾으려는 경우, Y의 주변에 E가 여덟칸 모두 들어있다.
어떤 E를 골라야할까?
=> 완전 탐색으로 원하는 단어 YES를 찾을 때까지 모든 인접한 칸을 다 탐색하자
문제의 분할
hasWord(y,x,word) = 보글 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환한다.
hasWord()함수가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다.
- 함수 호출시에 단어의 시작 위치를 정해주기 때문에 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 해결할 수 있다.
- 시작 위치에 쓰여있는 글자가 단어의 첫 글자와 다르다면 false를 반환하고 종료하면 된다.
- 그런 후 원래 단어 word에서 첫 글자를 뗀 word[1..]을 격자에서 찾아야 한다.
- word[1..]의 시작위치는 word의 시작위치 (y, x)와 인접한 여덟 칸 중 하나이다.
=> 결국 여덟 경우를 다 탐색하며 답을 찾아야 한다.
기저 사례의 선택
더 이상의 탐색 없이 답을 낼 수 있는 다음 경우들을 기저 사례로 선택해야 한다.
- 위치(y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
- (1이 아닌 경우) 원하는 단어가 한 글자인 경우 항상 성공
※ 두 조건의 순서가 바뀌면 안된다.
✏️ 간결한 코드 작성 팁
입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해 맨 처음에 처리한다.
그러면 함수를 호출하는 시점에서 오류를 검사할 필요가 없다.
재귀함수는 항상 한군데 이상에서 호출되기 때문에 이런 팁은 반복적인 코드를 제거하는 데 도움이 될 것이다.
위의 두 기저사례 외에 (현재위치가 보글 게임판을 벗어난 경우)와 (첫 글자가 일치하지 않는 경우)를 기저사례로 선택하자.
구현
// 코드 6.3 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘
let dx = [-1, -1, -1, 1, 1, 1, 0, 0]
let dy = [-1, 0, 1, -1, 0, 1, -1, 1]
// 5*5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환한다.
func hasWord(_ y: Int, _ x: Int, _ word: String) -> Bool {
// 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
if y < 0 || y >= 5 || x < 0 || x >= 5 { return false }
// 기저 사례 2: 첫 글자가 일치하지 않으면 실패
if board[y][x] != Array(word)[0] { return false }
// 기저 사례 3: 단어 길이가 1이면 성공
if word.count == 1 { return true }
// 인접한 여덟 칸을 검사한다.
for direction in 0..<8 {
let nextY = y + dy[direction]
let nextX = x + dx[direction]
// 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
if hasWord(nextY, nextX, String(word.dropFirst())) {
return true
}
}
return false
}
시간 복잡도 분석
완전 탐색 알고리즘의 시간 복잡도를 계산하는 것은 단순하다.
=> 가능한 답 후보들의 수를 전부 세어 보면 된다.
- 예를 들어 A로 가득찬 격자에서 AAAAAH를 찾는다고 하면, H가 격자에 존재하지 않기 때문에 탐색할 필요 없지만
- 완전 탐색은 모든 후보를 탐색하며 단어의 끝에 도달해야 답을 찾을 수 없다는 것을 안다.
이때 후보의 수는 마지막 글자에 도달하기 전까지 주변의 이웃 칸(8칸)에 대해 재귀호출 하니 8^N-1 = O(8^N)이다.
후보의 수는 단어의 길이에 따라 지수적으로 증가하기 때문에 단어의 길이가 짧은 경우에만 완전 탐색으로 해결 가능하다.
완전 탐색 레시피
어떤 문제를 완전 탐색으로 해결하기 위해 필요한 과정을 알아보자.
다음 과정들이 모든 문제에 항상 적용되는 것이 아니라, 처음에 어떤 식으로 문제에 접근할지를 알려주는 지침이 될 것이다.
- 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.
- 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
각 선택은 답의 후보를 만드는 과정의 한 조각이 된다. - 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
- 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다.
이론적 배경: 재귀 호출과 부분 문제
재귀 호출에서 짚고 넘어가야 할 중요한 개념은 문제와 부분문제의 정의이다.
- 문제: 주어진 자연수 수열을 정렬하라
- 문제: {16, 7, 9, 1, 31}을 정렬하라
위의 두 문제는 얼핏 같은 문제 같아보이지만 큰 차이가 있다.
전자는 특정한 입력을 지정하지 않았고, 후자는 전자의 반대이다.
재귀 호출에서 '문제'란? => 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다.
위의 두 정의 중 후자만이 문제의 정의라고 할 수 있다.
'부분 문제'란? => 원래 문제를 구성하는 조각들 중 하나를 뺀, 원래 문제의 일부이다.
2. 문제: 소풍
소풍을 가려고 할 때 선생님은 학생들을 두 명씩 짝을 지어 행동하려고 한다.
- 서로 친구가 아닌 학생들끼리 짝을 지우면 안된다. (서로 친구여야 함)
- 학생들을 짝 지을 수 있는 방법의 수 계산
☑️ 시간 및 메모리 제한
프로그램은 1초 내에 실행되어야 하며, 64MB 이하의 메모리만을 사용해야 한다.
☑️ 입력
입력의 첫 줄에는 테스트 케이스의 수 C(C<=50)가 주어진다.
각 테스트 케이스 첫 줄에는 학생의 수 n(2<=n<=10)과 친구 쌍의 수m(0<=m<=n(n-1)/2)이 주어진다.
그 다음 줄에 m개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어진다.
번호는 0부터 n-1 사이의 정수, 같은 쌍은 입력에 두 번 지어지지 않는다.
학생들의 수는 짝수다.
☑️ 출력
각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력한다.
☑️ 예제 입력
3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
☑️ 예제 출력
1
3
4
소풍 - 풀이
완전 탐색
가능한 조합의 수를 계산하는 문제를 푸는 가장 간단한 방법은 완전 탐색을 이용해 조합을 만들어 보는 것이다.
재귀 호출을 이용해 문제를 해결하려면 우선 각 답을 만드는 과정을 여러 개의 조각으로 나누어야 한다.
전체 문제를 n/2개의 조각으로 나눠 한 조각 마다 두 학생을 짝지어준다.
명단에서 서로 친구인 두 학생을 짝로 만들어주고, 남은 학생들을 짝지어준다.
중복으로 세는 문제
// 6.4 소풍 문제를 해결하는 (잘못된) 재귀 호출 코드
var n : Int
var areFriends : [[Bool]] = Array(repeating: Array(repeating: false, count:10 ), count: 10)
//taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
func countPairings(taken: inout[Bool]) -> Int{
var finished : Bool = true
for i in 0..<n{
if !taken[i]{
finished = false
}
}
if finished {return 1}
var ret = 0
// 서로 친구인 두 학생을 찾아 짝을 지어 준다.
for i in 0..<n{
for j in 0..<n{
if !taken[i] && !taken[j] && areFriends[i][j]{
taken[i] = true
taken[j] = true
ret += countPairings(taken: &taken)
taken[i] = false
taken[j] = false
}
}
}
return ret
}위의 코드의 문제점은 다음과 같다.
- 같은 학생 쌍을 두 번 짝지어 준다.
- (0, 1)과 (1, 0)을 따로 세고 있다.
- 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있다.
- 예를 들어 (0,1)후에 (2, 3)을 짝지어주는 것과 (2,3) 후에 (0,1)을 짝지어주는 것은 같은 방법인데 다른 경우로 세고 있다.
// 코드 6.5 소풍 문제를 해결하는 재귀 호출 코드
var n : Int
var areFriends : [[Bool]] = Array(repeating: Array(repeating: false, count:10 ), count: 10)
//taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
func countPairings(taken: inout[Bool]) -> Int{
//남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
var firstFree = -1
for i in 0..<n{
if !taken[i]{
firstFree = i
break
}
}
//기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
if firstFree == -1 {return 1}
var ret = 0
//이 학생과 짝지을 학생을 결정한다.
for i in 0..<n{
for j in 0..<n{
if !taken[i] && !taken[j] && areFriends[i][j]{
taken[i] = true
taken[j] = true
ret += countPairings(taken: &taken)
taken[i] = false
taken[j] = false
}
}
}
return ret
}
3. 문제: 게임판 덮기
H&W 크기의 게임판이 있다.
- 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양
- 이 중 모든 흰 칸을 세 칸짜리 L자 모양의 블록으로 덮고 싶다.
- 이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가면 안된다.
게임판이 주어질 때 이를 덮는 방법의 수를 계산해보자.
☑️시간 및 메모리 제한
프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 한다.
☑️ 입력
- 입력의 첫 줄에는 테스트 케이스의 수 C(C<=30)
- 각 테스트 케이스의 첫 줄에는 두 개의 정수 H, W(1<=H, W<=20)
- 다음 H 줄에 각 W 글자로 게임판의 모양이 주어진다.
- #은 검은 칸, .는 흰 칸을 나타낸다.
- 입력에 주어지는 게임판에 있는 흰 칸의 수는 50을 넘지 않는다.
☑️ 예제 입력
☑️ 예제 출력
풀이 - 게임판 덮기
게임판을 덮을 수 있는 모든 경우를 생성하는 완전 탐색을 이용해 해결할 수 있다.
입력으로 주어진 게임판에서 흰 칸의 수가 3의 배수가 아닐 경우에 무조건 답이 없으니 이 부분 따로 처리해야 한다.
이 외의 경우로 흰 칸의 수를 3으로 나눠서 내려 놓을 블록의 수 N을 얻은 뒤, 문제의 답을 생성하는 과정을 N 조각으로 나눠 한 조각에서 한 블록을 내려놓도록 하자.
=> 재귀함수로 주어진 게임판에 블록을 한개 내려놓고 남은 흰 칸들을 재귀호출을 이용해 덮도록 하면 된다.
중복으로 세는 문제
위와 같이 덮을 수 있는 방법의 수를 셀 수는 없다. 블록을 놓는 순서에 따라서 여러 번 세기 때문이다.
간편한 방법으로 재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗 줄 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 한다.
이렇게 하면 중복으로 세는 문제를 해결할 수 있다.
항상 빈칸 중에서 가장 위, 그 중에서 가장 왼쪽에 있는 칸을 처음 채운다고 가정해보자.
각 칸을 채우는 방법은 그림 6.3에서 보이는 바와 같이 모두 네 가지이다.
그림 추가ㅏㅏㅏㅏㅏㅏ
별표로 표시된 첫 번째 빈칸을 찾은 후 덮을 방법을 하나하나 시도한다. 이 방법이 달라질 때마다 서로 다른 배치가 되어, 원하는 답은 남은 게임판을 재귀 호출에 넘겨 얻은 경우의 수를 모두 더한 수가 된다.
답의 수의 상한
이 문제의 답은 최대 얼마일까?
그림 6.2에 따라 한 블록을 놓을 때 마다 모두 네 가지의 선택지가 있는데, 우리는 최대 [50/3] = 16개의 블록을 놓기 때문에 가능한 답의 상한은 4^16 = 2^32개가 된다.
2^32로 시간 내에 모두 생성할 수 없을 것 같지만, 실제 입력을 손으로 풀어봐 확인해보자.
- 예를 들어 흰 칸이 6칸 있는 입력이 주어진다면 이 이론 상으로는 4^2 = 16개의 방법이 있어야 하는데, 실제로는 두 개의 방법으로 밖에 배치할 수 밖에 없다.
구현
- 한 칸을 덮는 네 가지 방법을 각각의 코드로 구현한 것이 아니라 coverType[]에 배열에 저장한다.
- set()은 data에 따라 블록을 놓는 역할과 치우는 역할을 같이 할 수 있다.
- set()은 해당 위치에 블록을 놓을 수 있는지 여부도 같이 판단한다.
- 만약 두 개의 블록이 겹쳐있을 때 1을 더하여 겹침을 표시한다.
// 코드 6.6 게임판 덮기 문제를 해결하는 재귀 호출 알고리즘
// 주어진 칸을 덮을 수 있는 네 가지 방법
// 블록을 구성하는 세 칸의 상대적 위치(dy, dx)의 목록
var coverType = [
[[0,0], [1,0], [0,1]],
[[0,0], [0,1], [1,1]],
[[0,0], [1,0], [1,1]],
[[0,0], [1,0], [1, -1]]
]
func set(board: inout[[Int]], y: Int, x: Int, type: Int, delta: Int) -> Bool{
var ok : Bool = true
for i in 0..<3{
var ny = y + coverType[type][i][0]
var nx = x + coverType[type][i][1]
if ny < 0 || ny >= board.count || nx < 0 || nx >= board[0].count{
ok = false
}
else {
board[ny][nx] += delta
if board[ny][nx] > 1 {
ok = false
}
}
}
return ok
}
// board의 y,x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다.
// delta = 1이면 덮고, -1이면 덮었던 블록을 없앤다.
// 만약 블록이 제대로 덮이지 않은 경우(게임판 밖으로 나가거나,
// 겹치거나, 검은 칸을 덮을 때) fals를 반환한다.
func cover(board: inout[[Int]]) -> Int{
//아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
var y = -1
var x = -1
for i in 0..<board.count{
for j in 0..<board.count{
if board[i][j] == 0 {
y=i
x=j
break
}
}
if y != -1 {break}
}
// 기저 사례: 모든 칸을 채웠으면 1을 반환한다.
if y == -1 {return 1}
var ret = 0
for type in 0..<4{
//만약 board[y][x]를 type 형태로 덮을 수 있으면 재귀 호출한다.
if set(board: &board, y: y, x: x, type: type, delta: 1){
ret += cover(board: &board)
}
//덮었던 블록을 치운다
set(board: &board, y: y, x: x, type: type, delta: -1)
}
return ret
}
4. 최적화 문제
최적화 문제: 문제의 답이 하나가 아니라 여러 개로, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제를 의미한다.
- n개의 원소 중에서 r개를 순서 없이 골라내는 방법의 수 계산하는 문제
- n개의 사과 중에서 r개를 골라서 무개의 합을 최대화하는 문제
- 가장 무거운 사과와 가장 가벼운 사과의 무게 차이 최소화하는 문제
위의 예시 중 최적화 문제는 2번과 3번이다. 사과를 고르는 방법은 여러 개이지만, 특정 기준에 따라 가장 좋은 답을 고르기 때문이다.
최적화 문제를 해결하는 가장 기초적인 방법은 완전 탐색이다.
📍 예제: 여행하는 외판원 문제
어떤 나라에 n(2<=n<=10)개의 큰 도시가 있을 때, 한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다. 각 도시들은 모두 직선도로로 연결되어 있다고 하자.
그림 6.4(a)는 한 도로망의 예를 보여준다. 영업 사원이 여행해야 할 거리는 어느 순서로 각 도시들을 방문하냐에 따라 다르다.
그림 6.4(b)에 표시된 경로는 그림 6.4(c)에 표시된 경로보다 짧은 걸 확인할 수 있다.
그리미미미미밈ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
가능한 모든 경로 중 가장 짧은 경로 어떻게 찾을까?
무식하게 풀 수 있을까?
완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 있는지 확인하는 것이다.
시작한 도시로 돌아오는 경로를 찾기 때문에, 경로의 시작점은 신경 쓰지 않고 무조건 0번 도시에서 출발한다고 가정해도 경로의 길이는 다르지 않다.
n-1개의 도시를 나열하는 방법은 모두 (n-1)! 가지가 있다. 도시가 열 개라면 경로의 수는 9! = 362,880개가 된다.
재귀 호출을 통한 답안 생성
n개의 도시로 구성된 경로를 n개의 조각으로 나눠, 앞에서부터 도시를 하나씩 추가해 경로를 만들어 가기로 하자.
shortestPath(path) = path가 지금까지 만든 경로일 때, 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
// 코드 6.7 여행하는 외판원 문제를 해결하는 재귀 호출 알고리즘
// path: 지금까지 만든 경로
// visited: 각 도시의 방문 여부
// currentLength: 지금까지 만든 경로의 길이
// 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
let INF = Double.infinity
var n : Int
var dist = [[Double]]() // 두 도시 간의 거리를 저장하는 배열
func shortestPath(path: inout [Int], visited: inout [Bool], currentLength: Double) -> Double {
// 기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
if path.count == n {
return currentLength + dist[path[0]][path.last!]
}
var ret = INF // 매우 큰 값으로 초기화
// 다음 방문할 도시를 전부 시도해 본다.
for next in 0..<n {
if visited[next] { continue }
var here = path.last!
path.append(next)
visited[next] = true
// 나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
var cand = shortestPath(path: &path, visited: &visited, currentLength: currentLength + dist[here][next])
ret = min(ret, cand)
visited[next] = false
path.removeLast()
}
return ret
}
5. 문제: 시계 맞추기
그림ㄹ밀미림ㄹㅁ름ㄹ믈
그림과 같이 4×4개의 격자 형태로 배치된 열여섯 개의 시계가 있다.
- 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.
- 시계의 시간을 조작하는 유일한 방법은 열 개의 스위치를 조작하는 것
- 각 스위치들은 세 개에서 다섯 개의 시계에 연결되어 있다.
- 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다.
시계들이 현재 가리키는 시간들이 주어졌을 때 모든 시계를 12시로 돌리기 위해 최소한 스위치를 몇 번이나 눌러야 하는지 계산하는 코드를 구현해보자.
☑️ 시간 및 메모리 제한
프로그램은 10초 안에 실행되어야 한다. 64MB 이하의 메모리를 사용해야 한다.
☑️ 입력
첫 줄에 테스트 케이스의 개수 C(C<=30)
각 테스트 케이스는 한 줄에 16개의 정수로 주어진다,
각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.
☑️ 출력
각 테스트 케이스당 정 수 하나를 한 줄에 출력한다.
이 정수는 시계들을 모두 12시로 돌려놓기 위해 스위치를 눌러야 할 최소 횟수여야 하며, 만약 이것이 불가능할 경우 -1을 출력해야 한다.
☑️ 예제 입력
☑️ 예제 출력
풀이 - 시계 맞추기
문제 변형하기
예제 입출력 설명이 유도하는 방향과는 달리 스위치를 누르는 순서는 전혀 중요하지 않다.
=> "스위치를 몇번이나 누를지"만 계산하면 된다.
완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 열거할 수 있어야 하는데,
각 스위치를 몇번 누르는지는 상관 없고 그 조합 수는 무한하기 때문에 완전 탐색을 적용할 수 없다.
- 시계는 12시간이 지나면 제 자리로 돌아온다는 점을 이용해 무한한 조합의 수를 유한하게 바꿀 수 있다.
- 스위치 4번 누르기 => 연결된 시계 모두 12시간씩 앞으로 이동
- 따라서 최대 세 번 이상 누를 일이 없다. (각 스위치를 누르는 횟수는 0에서 3사이)
- 4^10 = 1,048,5746개로 모든 경우를 세어볼 수 있어 완전 탐색으로 풀 수 있다.
완전 탐색 구현하기
- 만약 답을 구할 수 없는 경우 재귀 함수의 반환 값은 문제의 출력 값인 -1이 아니라 매우 큰 값이 된다.
- save()는 재귀 호출이면서 가장 작은 출력 값을 찾게 되는데, 마지막에 답을 출력할 때 답이 매우 크면 -1을 대신 출력해준다.
- 어떤 스위치가 어떤 시계에 연결되어 있는지 2차원 배열에 저장
- 스위치가 i번째 스위치가 j번째 시계에 연결되었는지를 보려면 linked[i][j]를 보면 된다.
// 코드 6.8 시계 맞추기 문제를 해결하는 완전 탐색 알고리즘
let INF = 9999
let SWITCHES = 10
let CLOCKS = 16
// linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
// linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
let linked: [[Character]] = [
"xxx.............".map { $0 },
"...x...x.x.x....".map { $0 },
"....x.....x...xx".map { $0 },
"x...xxxx........".map { $0 },
"......xxx.x.x...".map { $0 },
"x.x...........xx".map { $0 },
"...x..........xx".map { $0 },
"....xx.x......xx".map { $0 },
".xxxxx..........".map { $0 },
"...xxx...x...x..".map { $0 }
]
// 모든 시계가 12시를 가리키고 있는지 확인한다.
func areAligned(_ clocks: [Int]) -> Bool {
return clocks.allSatisfy { $0 == 12 }
}
// swtch번 스위치를 누른다.
func push(_ clocks: inout [Int], _ swtch: Int) {
for clock in 0..<CLOCKS {
if linked[swtch][clock] == "x" {
clocks[clock] += 3
if clocks[clock] == 15 {
clocks[clock] = 3
}
}
}
}
// clocks: 현재 시계들의 상태
// swtch: 이번에 누를 스위치의 번호
// 가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
// 만약 불가능하다면 INF 이상의 큰 수를 반환한다.
func solve(_ clocks: inout [Int], _ swtch: Int) -> Int {
if swtch == SWITCHES {
return areAligned(clocks) ? 0 : INF
}
// 이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
var ret = INF
for cnt in 0..<4 {
ret = min(ret, cnt + solve(&clocks, swtch + 1))
push(&clocks, swtch)
}
// push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
return ret
}
6. 많이 등장하는 완전 탐색 유형
'알고리즘' 카테고리의 다른 글
| [Algorithm Strategy] - 8. 동적 계획법 (7) | 2023.08.15 |
|---|---|
| [Algorithm Strategy] - 7. 분할 정복 (0) | 2023.08.07 |
| [Algorithm Strategy] - 5. 알고리즘의 정당성 증명 (0) | 2023.07.25 |
| [Algorithm strategy] - 4. 알고리즘의 시간 복잡도 분석 (0) | 2023.07.10 |
| [Algorithm strategy] - 3장 코딩과 디버깅에 관하여 (0) | 2023.07.04 |