/* 본 게시물은 ' ' 의 내용과 참고자료를 토대로 작성되었습니다. */
/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */
1. 참고 자료
[백준] 15650번 - N과 M (2) : https://www.acmicpc.net/problem/15650
[AeroCode] 순열과 조합 알고리즘 : https://aerocode.net/376
2. 1. 조합이란?
표현 : nCr
정의 : 서로 다른 n개 중의 r 개를 뽑을때, 순서의 상관없이 뽑는 경우의 수
예시 : [1,2,3,4] 중 2개 뽑을 때
<kotlin />
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
3. 2. 조합 구현
백준 15650번 문제를 통해 조합을 구현해보자.
4. 문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
5. 입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
6. for 을 이용한 조합 구현
<kotlin />
fun combinationByForLoop(){
val arr = IntArray(4){i -> i + 1 }
for (i in arr.indices){
for (j in i+1 until arr.size)
for (k in j+1 until arr.size){
println("${arr[i]} ${arr[j]} ${arr[k]}")
}
}
}
순열과 마찬가지로 for 을 이용했을 때 뽑는 개수에 따라 변수(i,j,k)를 이용해 for 문을 중첩한다. 단, 순열과 다른 점은 j = i+1, k = j+1 로 설정한다.
7. 재귀를 이용한 조합 구현
<kotlin />
fun main() {
val (n,m) = readLine()!!.split(' ').map{ it.toInt() }
val tmpArr = IntArray(m)
fun getCombination(depth: Int, start: Int){
if (m == depth){
println(tmpArr.joinToString(" "))
}
else {
for (i in start..n){
tmpArr[depth] = i
getCombination(depth + 1, i + 1)
}
}
}
getCombination(0,1)
}
순열과 다르게 조합 구현은 간단하다. 함수의 파라미터로 시작점을 넘겨주면 된다.
반응형
