[백준]15652 N과 M(4)

문항번호: 15652 N과 M(4)

1. 문제 분석

• 1 ~ N의 자연수 중 M개를 고른 수열
• 같은 수 여러번 고르기 가능.
• 고른 수열은 비 내림차순이어야 함.
• A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK

2. 풀이 계획

• 1부터 N까지 가면서 출력을 하게 된다.
• Back-tracking : 불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법
• 이미 탐색한 값보다 작은 값의 경우, 다음 input으로 들어올 수 없으므로, 반복문 안에서 더 낮은 숫자의 반복문이 돌지 않도록 설정해주어야 하겠다.
  -> for 문의 시작점을 현재의 current Value부터 시작하도록 설정해서 위 조건을 만족 시킴.
• 

사실 전형적인 DFS 문항이라고 생각했지만, 문제의 분류표를 살펴보고 난 후, 백트래킹 알고리즘이라는 것을 알 수 있었다.

백트래킹 알고리즘은 솔루션을 찾는 과정에서, 유망(promising)하지 않은 후보해에 대해 대해 빠르게 포기하고 이전 단계로 되돌아(back track)가 다른 후보해를 찾는 알고리즘 기법을 말한다.

DFS와의 차이를 생각해보면, DFS의 경우 완전 탐색을 기본으로 하는 그래프의 순회 기법을 말하며, 모든 노드의 방문이 목적이라면, Back-Tracking은 불필요한 탐색은 하지 않도록 한다. (더 이상 진행할 수 없다면, 이전 단계로 되돌아 나온다.)

나도 이 두 알고리즘의 방향에 대해서 문제 풀이를 하면서 경험한 바로는 둘 다 재귀 호출을 하고 있다고 느껴졌고, 구현하는 부분도 크게 다르지 않게 느껴졌다.

BackTracking은 불필요한 탐색을 하지 않기 위해, 유망하지 않는 경우의 수를 줄이는 것을 목표로 한다.

3. 계획 검증

• 시간 복잡도는 고려하지 않았다. ( 1 ≤ M ≤ N ≤ 8 )
• 
• 충분히 넉넉한 시간이 배분되었다고 생각한다.

4. 소스 코드

import Foundation

let value = readLine()!.split(separator: " ").map { Int(String($0))! }  
let N = value\[0\], M = value\[1\]  
var result = ""

func dfs(currentValue: Int, count: Int, result: String) {  
// 반환 구문  
    if count == M {  
        print(result)  
        return  
    }  
    for num in currentValue...N {  
        dfs(currentValue: num, count: count+1, result: result + "(num) ")    
    }
}

dfs(currentValue: 1, count: 0, result: result)

5. 돌아 보기

백트래킹 알고리즘이 무엇인지를 확인해볼 수 있었다. 그동안 백트래킹 알고리즘과 DFS에 대한 구분을 제대로 하고 있지 않았다는 생각이 든다.

백트래킹 알고리즘과 DFS에 대한 비교글에 대해서
하단 블로그에 잘 정리가 되어 있는 듯해서 링크를 같이 걸어본다.
백트래킹 vs DFS

tag: problem solving 백트래킹