/* 본 게시물은 ' ' 의 내용과 참고자료를 토대로 작성되었습니다. */
/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */
참고 자료
[AeroCode] 순열과 조합 알고리즘 : https://aerocode.net/376
[백준] 15649번 - N 과 M (1) : https://www.acmicpc.net/problem/15649
1. 순열이란?
표현 : nPr
정의 : 서로 다른 n개 중의 r개를 뽑을 때, 순서를 포함한 경우의 수
예시 : [1, 2, 3] 배열의 순열 경우의 수
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]2. 순열 구현 (with 백준 15649번)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
for 문을 사용한 순열 구현
for 문으로 순열을 구현하는 가장 간단한 방법은 for 반복문을 r번 중첩시키는 것이다. 이 때, r 개의 변수(i,j,k...)가 모두 다른 값을 가르키도록 한다. 코드는 다음과 같다.
// r: 뽑는 수, n: 개수,
fun makePermutationByForLoop1(r: Int, n:Int, arr: IntArray)= with(BufferedWriter(OutputStreamWriter(System.out))){
// M = 2
if (r == 2) {
for (i in 0 until n) {
for (j in 0 until n) {
if (i == j) continue //중복 배제
this.write("${arr[i]} ${arr[j]}\n")
}
}
}
// M = 3
if (r == 3) {
for (i in 0 until n) {
for (j in 0 until n) {
for (k in 0 until n) {
if (i == j || j == k || i == k) continue
this.write("${arr[i]} ${arr[j]} ${arr[k]}\n")
}
}
}
}
this.flush()
this.close()
}
fun main() {
readLine()!!.split(' ').map{it.toInt()}.let { (N, M) ->
val arr = IntArray(N) { i -> i + 1 }
makePermutationByForLoop1(3,N,arr)
makePermutationByForLoop2(N,arr)
}
}
for 문을 이용한 다른 방법으로는 booleanArray를 이용해 n번째 값을 확인하는 방법이다. 코드는 다음과 같다.
// r: 뽑는 수, n: 개수,
fun makePermutationByForLoop2(n:Int, arr: IntArray) = with(BufferedWriter(OutputStreamWriter(System.out))){
// n번 째 요소 사용
val isUsed = BooleanArray(n)
//r=3 인 경우
for (i in arr.indices){
if (isUsed[i]) continue
isUsed[i] = true
for (j in arr.indices){
if (isUsed[j]) continue
isUsed[j] = true
for (k in arr.indices){
if (isUsed[k]) continue
isUsed[k] = true
this.write("${arr[i]} ${arr[j]} ${arr[k]}\n")
isUsed[k] = false
}
isUsed[j] = false
}
isUsed[i] = false
}
this.flush()
this.close()
}위 두 코드를 보면 알 수 있듯이, r 값이 클 경우 코드도 길어질 수 밖에 없다. 즉, 이 방법은 r 값이 작을 때 유효한 방법이다.
재귀를 이용한 순열 구현
재귀를 이용해 순열을 구현할 경우 r 값이 클 때도 같은 코드로 처리할 수 있다.
fun makePermutationByRecursion(arr: IntArray, r: Int, temp: IntArray, depth: Int, isUsed: BooleanArray) {
if (r == depth) { // 탈출조건 : depth 가 r과 같아진 경우, 즉 하나의 순열 완성 tmp.size 써도 무방.
for (num in temp) print("$num ")
println()
} else {
for (i in arr.indices) {
if (isUsed[i]) continue
isUsed[i] = true
temp[depth] = arr[i]
makePermutationByRecursion(arr, r, temp, depth + 1, isUsed)
isUsed[i] = false
}
}
}
fun main() {
readLine()!!.split(' ').map{it.toInt()}.let { (N, M) ->
val arr = IntArray(N) { i -> i + 1 }
makePermutationByRecursion(arr, M, IntArray(M), 0, BooleanArray(N))
}
}* arr: 선택할 요소가 들어있는 배열 , r: 뽑는 횟수 , temp: 뽑은 요소를 추가할 임시 배열, depth: 현재(temp) 까지 뽑은 요소 개수, isUsed: booleanArray
실행 결과 (2128ms)
코드를 좀 더 효율적으로 만들어보자.
fun main(){
val (n,m) = readLine()!!.split(' ').map{it.toInt()}
val boolArr =BooleanArray(n+1)
val tmp = IntArray(m)
fun getPermutation(depth:Int){
if (m == depth) {
println(tmp.joinToString(" ")) // joinToString() 메서드 사용
}
else {
for(i in 1..n){ // 1..n 으로해서 boolArr 의 index가 값 자체를 의미
if(!boolArr[i]){
boolArr[i]=true
tmp[depth]=i;
getPermutation(depth+1);
boolArr[i]=false
}
}
}
}
getPermutation(0)
}재귀 함수의 파라미터로 depth 만 넘겨주도록 변경했다.
실행 결과(1332ms)
첫 번째가 범용적으로 쓰기 좋은 형태이다. (부수효과 x)
순열 완료
조합, 중복순열, 중복조합 도 구현해보자.
