Algorithm(알고리즘) 기본 수학(조합, 순열, 소수 등) 정리 feat. kotlin

1.  조합(★★★★★)

정의 - 서로 다른 n개의 원소가 모인 집합에서 r개로 이루어진 집합을 뽑는 경우의 수

 

컴퓨터의 데이터를 다룰때 기본적으로 자료구조(배열, 리스트...등) 데이터를 담아서 조합을 이용한다.

즉, 그래서 index를 선택함으로 구현한다. 

완전탐색 문제에서 자주 사용된다.

* n C r =  n C n-r 

 

구현

r이 3이하인 경우 반복문으로 구현.

fun main() {

    val arr = Array(4){ it }
    
    // n = arr.size r = 3 일때 
    for (i in 0 until arr.size){
        for (j in i+1 until arr.size){
            for (k in j+1 until arr.size){
                println("i:$i j:$j k:$k")
            }
        }
    }
}

r이 4이상인 경우 재귀로 구현.

val combinationList = mutableListOf('a', 'b', 'c', 'd')
var combinationTotalCnt = 0

// 조합의 결과 뽑은 index를 담을 배열.
val resultList: MutableList<Int> = mutableListOf()
fun combination(n: Int, r: Int, start: Int = 0) {

    if (resultList.size == r) {
        /*
            logic

        * */
        combinationTotalCnt += 1
        println(resultList.joinToString(" "))
        return
    }

    for (i in start until n) {
        // 뽑고 -> 다음 idx 부터 뽑도록 start param i+1로 증가 
        resultList.add(i)
        combination(n, r, start = i + 1)
        // 원복.
        resultList.removeLast()
    }
}

fun main() {
    combination(combinationList.size, 3)
    println("combinationTotalCnt: ${combinationTotalCnt}")
}

 

2.  순열(★★★★☆)

정의 -  서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수.

 

완전탐색문제에서 자주 사용되지만, 상대적으로 조합보다 덜 사용된다.

조합과 달리 순서가 변경되면 다른 경우의 수로 취급을 하여 뽑아야되기 때문에, "뽑고 다음것을 뽑고 원복"  하는 조합 코드와는 다르다.

조합은 다음 재귀호출에서 이전에 뽑은 idx에 +1 부터 반복을 시작하여 중복을 선택하지 않으면서, 순서도 고려하지 않고 뽑을 수 있었지만, 순열은 순서를 고려해야되기 때문에 항상 매 재귀마다 idx = 0 부터 뽑되, 중복 선택을 막기 위한 체크를 위한 배열이 필요하다.

var isSelect = BooleanArray(permutationArr.size) { false }

구현

val permutationArr = arrayOf(
    'a', 'b', 'c', 'd', 'e'
)

var isSelect = BooleanArray(permutationArr.size) { false }

// result 항상 index 담아둔다.
val permutationResult = mutableListOf<Int>()
var permutationTotalCnt = 0

fun permutation(n: Int, r: Int) {

    // 카운트 숫자를 매개변수로 주어 뽑으려는 수까지 cnt를 세게되면 메서드 종료
    if (permutationResult.size == r) {
        /*
            logic
         */
        permutationTotalCnt += 1
        println(permutationResult.joinToString(" "))
        return
    }

    //매번 재귀 마다 반복문 시작이 0부터 시작함.

    for (i in 0 until n) {
        // 중복 선택을 방지한다.
        if (isSelect[i]) continue

        permutationResult.add(i)
        isSelect[i] = true

        permutation(n = n, r = r)

        permutationResult.removeLast()
        isSelect[i] = false
    }
}

fun main() {
    permutation(n= permutationArr.size, r= 4)
    println("PermutationTotalCnt: $permutationTotalCnt")
}

 

3.  소수(★★★☆☆)

정의 - 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수

 

자주 출제되지는 않지만, 출제되어 효율성을 묻는 문제라면, 특히, 에라스토테네스의 체를 사용해야된다면, 효율성을 통과하지 못할 가능성이 높다. 코드가 간단하기에 외우도록 하자.

/*
 *  정의에 충실한 단순 구현 
 *  가장 단순하고 비효율적인 방법
 *  시간 복잡도 O(N)
 */
 
fun isPrimeV1(n: Int): Boolean {
    if (n == 1) return false
    if (n == 2) return true

    for (i in 2 until n) {
        if (n % i == 0) return false
    }
    return true
}

효율성 개선

import kotlin.math.sqrt

/*
 *  곱의 절반인 sqrt(n.toDouble()).toInt()까지만 반복.
 *  시간 복잡도 O(logN)
 */
 
fun isPrimeV2(n: Int): Boolean {
    if (n == 1) return false
    if (n == 2) return true

    val end = sqrt(n.toDouble()).toInt()

    for (i in 2..end) {
        if (n % i == 0) return false
    }
    return true
}

 

에라토스 테네스의 체

 

/*
 * 특정 정수 n까지 모든 정수에 대한 소수를 미리 판별해 놓고,
 * 여러번 오는 쿼리에 대해서 빠르게 처리한다.
 * O(1)
 *
 */
 
val primes = mutableListOf<Int>()
fun eratos(n: Int) {

    /* idx = 해당 수를 의미하고
    * arr[idx] = 1 이면 소수
    * arr[idx] = 0 이면 소수가 아님을 뜻한다.
    * 초기화 - 모든 값을 1로 초기화 한다.
    * 0, 1은 소수가 아니다.
    */
    val arr = IntArray(n + 1) { 1 }
    arr[0] = 1
    arr[1] = 0

    // 2 .. n 까지 반복
    for (i in 2..n) {
        // 이미 0이면 건너뜀.
        if (arr[i] == 0) continue
        // 자신을 제외한 배수를 arr[idx] = 0 로 만들어 준다.
        for (j in i*2 ..n step i){
           arr[j] = 0
        }
    }

    // 소수로 판명된 것들은 리스트에 담음.
    for (i in 2..n) {
        if (arr[i] != 0) {
            primes.add(i)
        }
    }
}

fun main() {
    eratos(10000)
    println(primes.joinToString(" "))
}

 

4.  최대 공약수, 최소 공배수(★★☆☆☆)

정의

최소 공배수  -  두개의 정수 a, b의  공통 배수 중에서 최소인 것

최대 공약수 -   두개의 정수 a, b의  공통 약수 중에서 최대인 것

 

/*
    gcd - 최대 공약수

    두 수 a, b 있고 a > b다면, val r = a / b
    a와 b의 최대 공약수는 b와 r의 공약수와 같다.

    lcm - 최소 공배수
    
    (a * b) / 최대 공약수
 */

fun gcd(num1: Int, num2: Int): Int {

    var (a, b) =
        if (num1 > num2) {
            num1 to num2
        } else {
            num2 to num1
        }

    while (b != 0) {
        val r = a % b
        a = b
        b = r
    }
    return a
}

fun lcm(a: Int, b: Int): Int {

    return a * b / gcd(a, b)
}

fun main() {
    println(gcd(200, 160))
    println(lcm(200,160))
}