안녕하세요, 여러분! 이번 강좌에서는 코틀린을 사용하여 “이친수”를 구하는 문제를 해결해 보겠습니다. 이친수는 0과 1로 이루어진 수열로, ‘0’과 ‘1’이 교차하는 조건을 만족하는 수를 의미합니다. 이 문제는 동적 프로그래밍(Dynamic Programming) 기법을 통해 효율적으로 해결할 수 있습니다.
1. 문제 정의
이친수를 구하는 문제는 다음과 같이 정의할 수 있습니다:
주어진 정수 N에 대해 길이 N인 이친수의 개수를 구하시오.
예시
- N = 1: 이친수는 “0”, “1” 두 개 → 개수: 2
- N = 2: 이친수는 “00”, “01”, “10”, “11” (단, ’00’은 이친수가 아니므로 제외) → 개수: 1 (01, 10만 가능)
- N = 3: 이친수는 “001”, “010”, “100”, “101”, “110” → 개수: 5
2. 문제 이해
이 문제를 해결하기 위해서는 이친수가 어떻게 구성되는지를 이해하는 것이 중요합니다. 이친수는 다음과 같은 조건을 가집니다:
- 0으로 시작할 수 없다.
- 0이 연속해서 2개 이상 나타날 수 없다.
- 1이 연속해서 2개 이상 나타날 수 없다.
따라서 이친수의 길이 N이 주어졌을 때, 이친수의 마지막 자리를 0으로 두었을 경우, 그 앞의 자리는 반드시 1여야 합니다. 반대로 마지막 자리를 1로 두었을 경우, 그 앞 자리는 0이나 1이 될 수 있지만, 이 친수가 되기 위한 조건은 여전히 유지되어야 합니다.
3. 동적 프로그래밍 접근법
이 문제는 동적 프로그래밍을 통해 효율적으로 풀 수 있습니다. 우리는 두 가지 상태로 나누어서 배열을 구성할 것입니다. 여기서:
- dp[i]는 길이 i인 이친수의 개수를 나타냅니다.
- dp0[i]는 길이 i의 이친수가 0으로 끝나는 경우의 수입니다.
- dp1[i]는 길이 i의 이친수가 1로 끝나는 경우의 수입니다.
점화식
따라서 다음과 같은 점화식을 세울 수 있습니다:
- dp0[i] = dp1[i-1]
- dp1[i] = dp0[i-1] + dp1[i-1]
- dp[i] = dp0[i] + dp1[i]
초기값
초기값으로는 다음과 같습니다:
- dp[1] = 2 (이 친수는 0과 1)
- dp0[1] = 1 (1로 끝나는 경우)
- dp1[1] = 1 (0으로 끝나는 경우)
4. 코드 구현
이제 코틀린을 사용하여 이친수를 구하는 코드를 구현해 보겠습니다.
fun countBinaryFriends(n: Int): Int {
if (n == 1) {
return 2
}
val dp0 = IntArray(n + 1)
val dp1 = IntArray(n + 1)
dp0[1] = 1
dp1[1] = 1
for (i in 2..n) {
dp0[i] = dp1[i - 1]
dp1[i] = dp0[i - 1] + dp1[i - 1]
}
return dp0[n] + dp1[n]
}
fun main() {
val n = readLine()!!.toInt()
println(countBinaryFriends(n))
}
5. 코드 설명
위 코드는 길이 N인 이친수를 구하는 함수 countBinaryFriends를 정의하고 있습니다. 입력으로 정수 N을 받고, 그에 대한 이친수의 개수를 반환합니다. 먼저 길이가 1일 때의 경우를 처리한 후, 동적 프로그래밍을 활용하여 배열 dp0와 dp1를 업데이트합니다. 마지막으로, dp0[n]과 dp1[n]을 합쳐서 결과를 반환합니다.
6. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(N)입니다. 배열을 한 번 순회하면서 값을 계산하므로 효율적으로 풀 수 있습니다. 공간 복잡도도 O(N)이며, 이친수를 구하는 데 필요한 메모리를 동적으로 관리할 수 있습니다.
7. 마무리
이번 강좌를 통해 코틀린을 사용하여 이친수를 구하는 문제를 해결해 보았습니다. 이 문제는 동적 프로그래밍을 이해하는 데 좋은 예제이며, 실전 코딩 테스트에서도 자주 출제되는 문제 중 하나입니다. 동적 프로그래밍의 기본 원리를 알고 활용할 수 있다면, 다양한 문제를 접근하고 해결할 수 있는 능력이 향상될 것입니다.
앞으로도 다양한 알고리즘 문제를 함께 해결해 나가며 코딩 능력을 쌓아가길 바랍니다. 감사합니다!