스위프트 코딩테스트 강좌, 이친수 구하기

작성자: 조광형

날짜: [날짜]

1. 이친수(이진 친화수)란?

이친수란, 다음의 조건을 만족하는 이진수 문자열을 의미합니다:

  • 0과 1로만 구성된다.
  • 연속된 두 자리 수에 1이 오지 않는다. 즉, ’11’ 이라는 부분 문자열이 존재하지 않아야 합니다.
  • 문자열의 양 끝은 0으로 끝나야 합니다.

예를 들어, ‘010’, ‘0010’, ‘1000’은 이친수이다. 반면에 ’11’, ‘110’, ‘0110’, ‘0001’은 이친수가 아니다.

2. 이친수 문제 정의

주어진 자연수 n에 대해, 길이가 n인 이친수의 개수를 구하는 문제를 정의합니다. 이 문제는 동적 프로그래밍(Dynamic Programming)을 활용하여 효율적으로 해결할 수 있습니다.

3. 문제 예시

예를 들어, 길이가 1인 이친수는 ‘0’과 ‘1’ 총 2개입니다. 하지만 길이가 2인 이친수의 경우는 ’00’, ’01’, ’10’ 총 3개가 있습니다. 길이가 3인 이친수는 ‘000’, ‘001’, ‘010’, ‘100’, ‘101’ 총 5개이며, 길이가 4인 이친수는 ‘0000’, ‘0001’, ‘0010’, ‘0100’, ‘0101’, ‘1000’, ‘1001’, ‘1010’ 총 8개입니다. 이런 식으로 패턴을 찾아갈 수 있습니다.

4. 문제 접근법

이 문제는 다음과 같은 재귀적 성질을 갖습니다:

  • 길이가 n인 이친수는 길이 n-1의 이친수로부터 유도할 수 있으며, 양 끝이 0으로 끝나는 경우와 1로 끝나는 경우가 있습니다.
  • 따라서, dp[n] = dp[n-1] + dp[n-2]의 관계로 표현할 수 있습니다.

5. 동적 프로그래밍을 이용한 구현

이제 위의 관계를 바탕으로 Swift 언어로 이친수를 구하는 코드를 작성해 보겠습니다. 아래는 Swift 코드 예시입니다:

            
                func countBinaryFriends(n: Int) -> Int {
                    guard n > 1 else { return n }
                    
                    var dp = [Int](repeating: 0, count: n + 1)
                    dp[1] = 2 // 0, 1
                    dp[2] = 3 // 00, 01, 10
                    
                    for i in 3...n {
                        dp[i] = dp[i - 1] + dp[i - 2]
                    }
                    
                    return dp[n]
                }

                let n = 4 // 예시 입력
                print(countBinaryFriends(n: n)) // 이친수 개수 출력

6. 시간 복잡도 및 공간 복잡도

위의 알고리즘은 n에 대해 O(n)의 시간 복잡도를 가집니다. 또한, dp 배열을 이용 하므로 O(n)의 공간 복잡도를 가집니다. 이를 최적화 할 경우 필요한 이전 값 두 개만 기억할 수 있도록 하여 O(1)로 공간 복잡도를 줄일 수 있습니다:

            
                func optimizedCountBinaryFriends(n: Int) -> Int {
                    guard n > 1 else { return n }
                    
                    var prev1 = 2 // dp[1]
                    var prev2 = 3 // dp[2]
                    var current = 0

                    for i in 3...n {
                        current = prev1 + prev2
                        prev1 = prev2
                        prev2 = current
                    }
                    
                    return current
                }

                let n = 4 // 예시 입력
                print(optimizedCountBinaryFriends(n: n)) // 최적화된 이친수 개수 출력

7. 결론

위의 과정을 통해 이친수를 구하는 문제를 해결할 수 있었습니다. 이 문제는 동적 프로그래밍의 기초를 이해하는 데 좋은 예시입니다. 이친수를 구하는 과정에서 발생하는 패턴을 잘 이해하고 기억하여, 이와 유사한 문제를 해결하는 데 도움이 되기를 바랍니다.

8. 추가 학습 자료

추가적으로 알고리즘과 데이터 구조에 관한 정리와 연습 문제를 풀어보는 것도 중요합니다. 아래는 추천 자료입니다: