코틀린 코딩테스트 강좌, 부녀회장이 될 테야

코딩테스트는 많은 기업들이 후보자를 평가하기 위해 사용하는 중요한 도구입니다.
특히 알고리즘 문제는 코딩 실력과 문제 해결 능력을 측정하는 데 효과적입니다.
이번 강좌에서는 ‘부녀회장이 될 테야’라는 알고리즘 문제를 다루어 보겠습니다.
이 문제를 통해 코틀린의 기본 문법과 알고리즘적 사고를 발전시킬 수 있을 것입니다.
문제의 본질, 접근 방법, 코드 구현 및 최적화 방법에 대해 자세히 설명하겠습니다.

문제 설명

어느 날, 부녀회장이 되고 싶은 한 사람은 아파트에 살고 있습니다.
이 아파트의 구조는 다음과 같습니다:

0층: 1호, 2호, 3호, …, n호에 거주하는 사람 수는 각각 1명입니다.
1층: 1호에는 1층 사람 수를 더해서 2층 사람 수를 만들고, …
k층: n호에는 0층부터 k층까지 각 층의 인원 수를 모두 더한 수가 거주합니다.

이러한 아파트 구조에서, 주어진 층과 호수에 따라 해당 호수에 거주하는 인원 수를 구하는 문제입니다.

입력 형식

첫째 줄: 테스트 케이스의 수 T (1 ≤ T ≤ 10)
각 테스트 케이스마다 두 개의 정수 K (0 ≤ K ≤ 14)와 N (1 ≤ N ≤ 14)가 주어집니다.

출력 형식

각 테스트 케이스마다 해당 호수에 거주하는 사람 수를 출력합니다.

문제 접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 이용하여 해결할 수 있습니다.
다음과 같은 방법으로 접근할 수 있습니다:

아파트 구조의 특성을 이해하고 0층의 각 호수에는 1명씩 거주하고 있다는 것을 기억합니다.
그러면 1층의 사람 수는 0층의 사람 수를 반복적으로 더하는 방식으로 결정됩니다.
K층의 N호수에 거주하는 인원 수는 (K-1)층의 1호 + (K-1)층의 2호 + … + (K-1)층의 N호수의 합입니다.
이는 재귀적인 성질을 가지고 있기 때문에 재귀 호출을 통해 해결할 수 있습니다.
구현 시, 특정 층과 호수에 대한 인원 수를 저장하는 2차원 배열을 생성하여 결과를 메모이제이션(memoization)할 수 있습니다.

코드 구현

아래는 위의 알고리즘을 코틀린으로 구현한 코드입니다.


        fun main() {
            val t = readLine()!!.toInt()
            val results = IntArray(t)

            for (i in 0 until t) {
                val (k, n) = readLine()!!.split(' ').map { it.toInt() }
                results[i] = calculateResidents(k, n)
            }

            for (result in results) {
                println(result)
            }
        }

        fun calculateResidents(k: Int, n: Int): Int {
            // 14층 14호 구조체를 초기화
            val dp = Array(15) { IntArray(15) }

            // 0층은 1명씩 거주
            for (j in 1..14) {
                dp[0][j] = 1
            }

            // 각 층과 각 호수에 대해 반복
            for (i in 1..k) {
                for (j in 1..n) {
                    // (i-1)층 j호의 사람 수를 더함
                    for (m in 1..j) {
                        dp[i][j] += dp[i - 1][m]
                    }
                }
            }

            return dp[k][n] // k층 n호의 주민 수 반환
        }

코드 설명

위 코드에서 `calculateResidents` 함수는 주어진 K층 N호에 거주하는 인원 수를 계산합니다.
이 함수는 다음과 같은 단계로 진행됩니다:

2차원 배열 `dp`를 만들어 15×15 구조를 초기화합니다.
0층에서는 모든 호수에 1명씩 거주하고 있음을 설정합니다.
K층과 N호에 대해서, 모든 호수에서 (K-1)층의 인원 수를 합산하여 누적합니다.
최종적으로 DP 테이블에서 K층 N호의 사람 수를 반환합니다.

시간 복잡도 분석

이 문제의 시간 복잡도는 O(K * N^2)입니다. K는 최대 14이므로,
전체적인 시간 복잡도는 상수로 취급할 수 있습니다. 따라서 문제를 빠르고 효율적으로 해결할 수 있습니다.
코드를 최적화하고 메모리를 절약하면서 구현하는 것이 중요합니다.

결론

‘부녀회장이 될 테야’ 문제는 동적 계획법을 통해 해결할 수 있는 전형적인 알고리즘 문제입니다.
코틀린의 문법을 활용하고, DP를 통해 문제를 해결하는 과정에서 알고리즘적 사고를 기를 수 있습니다.
이러한 문제를 풀며 코딩테스트에서의 경쟁력을 높일 수 있을 것입니다.
이 강좌를 통해 배운 내용이 실제 코딩테스트 준비에 도움이 되기를 바랍니다!