윤굥굥
yg323
윤굥굥
전체 방문자
오늘
어제
  • 굥굥 DEV
    • Computer Science
      • 자료구조 및 알고리즘
      • 운영체제
      • 네트워크
      • 데이터베이스
    • Programming Language
      • Java
      • Kotlin
    • Android
      • with Kotlin
    • Algorithm
      • with Kotlin
    • 하나씩 습득하는 중

블로그 메뉴

  • ↓백준 모아보기 ↓
  • 💚 플레티넘 문제 모아보기
  • 💛 골드 문제 모아보기
  • 🤍 실버 문제 모아보기
  • 🤎 브론즈 문제 모아보기

공지사항

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.
윤굥굥

yg323

Algorithm/with Kotlin

[코틀린] 조합, 순열 구현하기

2022. 2. 5. 14:30

백트래킹을 공부하면서, 백트래킹 대표 입문 문제인 N과 M을 풀어보았다. Python으로 조합과 순열을 사용할 때가 나오면, 이미 구현된 라이브러리를 사용했었다. 그럼 Kotlin에서는 조합, 순열을 사용하려면 어떻게 해야될까 생각을 하였고, 미리 템플릿(?)을 만들어두기로 했다. 

평소에 수학 문제를 풀때 처럼 array와 n, r 값만 입력하면, List 형태로 결과가 나오고 이를 가공해서 편한대로 사용할 수 있다. 

순열 \(_nP_r\)

private fun <T> permutation(array: Array<T>, n: Int, r: Int): List<List<T>> {
    val nArray = array.sliceArray(0 until r) //reified type을 쓰지 않고, Array<T>를 사용하기 위해 작성
    val visited = BooleanArray(n)
    val list = mutableListOf<List<T>>()

    fun recursionPermutation(depth: Int = 0) {
        if (depth == r) {
            list.add(nArray.toList()); return
        }

        array.forEachIndexed { index, t ->
            if(!visited[index]) {
                visited[index] = true
                nArray[depth] = t
                recursionPermutation(depth + 1)
                visited[index] = false
            }
        }
    }

    recursionPermutation()
    return list
}
더보기

 

🐯 array를 변경해서 테스트 해보세요!! 코드 편집 가능합니다!

 

조합 \(_nC_r\)

private fun <T> combination(array: Array<T>, n: Int, r: Int): List<List<T>> {
    val list = mutableListOf<List<T>>()

    fun recursionCombination(depth: Int = 0, index: Int = 0, resultArray: Array<T> = array.sliceArray(0 until r)) {
        if (depth == r) {
            list.add(resultArray.toList()); return
        }

        for (arrayIndex in index until n) {
            resultArray[depth] = array[arrayIndex]
            recursionCombination(depth + 1, arrayIndex + 1, resultArray)
        }
    }

    recursionCombination()
    return list
}

fun main() {
    combination(arrayOf(1, 2, 3, 4), 4, 3).forEachIndexed { _, ints -> println(ints.joinToString(" ")) }
    combination(arrayOf('a', 'b', 'c'), 3, 2).forEachIndexed { _, ints -> println(ints.joinToString(" ")) }
}
더보기

 

🐯 array를 변경해서 테스트 해보세요!! 코드 편집 가능합니다!

 

저작자표시 비영리 변경금지 (새창열림)
    'Algorithm/with Kotlin' 카테고리의 다른 글
    • [백준][코틀린] 15650 N과 M (2)
    • [백준][코틀린] 15649 N과 M (1)
    • [백준][코틀린] 11729 하노이 탑 이동 순서
    • [백준][코틀린] 2447 별 찍기 - 10
    윤굥굥
    윤굥굥

    티스토리툴바