https://www.acmicpc.net/problem/1182
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
백트래킹의 연습을 위해서 문제를 풀었습니다. 가장 중요한 구조는 N과 M(1) 의 문제를 기초로 문제에서 원하는 조건 과 분기를 설정하여 백트래킹을 하는 것입니다.
fun main(){
val (n,m) = readLine()!!.split(" ").map{it.toInt()}
val num = IntArray(m) {0}
val used = BooleanArray(n+1) {false}
fun bt(par : Int){
if(m==par) {
println(num.joinToString(" "))
return
}
for(i in 1..n){
if(!used[i]){
num[par] = i
used[i]= true
bt(par+1)
used[i]=false
}
}
}
bt(0)
}n을 사용되는 숫자의 범위 m을 출력될 자리수로 생각하면 bt함수의 첫번째에서는 우선 자리수(m)만큼 bt함수가 재귀 되었는가를 판단하고 만약 그만큼 재귀되었다면 채워진 num IntArray를 출력하는 것입니다.
이후 for문에서는 used라는 BoolenArray를 통해서 해당 숫자가 사용되었는가 아닌가를 판단하면서 사용되지 않았다면 해당 숫자를 num에 채우고 다음 숫자를 매개변수로 재귀 호출 합니다.
이와 같은 구조를 기초로 N-Queen, 부분수열의 합등의 문제를 풀었습니다.
이외 풀이 코드는 https://github.com/IslandofDream/Baekjoon_Practice/tree/main/%EB%B0%B1%EC%A4%80 를 참고해주시면 감사하겠습니다.
참고링크
[실전 알고리즘] 0x0C강 - 백트래킹
이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는
blog.encrypted.gg
https://youngest-programming.tistory.com/221
[알고리즘] 백준 N과 M (1) -백트랙킹- 자바 코틀린
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
youngest-programming.tistory.com