안녕하세요! 이번 강좌에서는 이친수를 구하는 알고리즘 문제를 다루어 보겠습니다. 이친수란 0과 1로 이루어진 수 중에서 두 개의 1이 연속해서 나타나지 않는 수를 말합니다. 예를 들어, 3자리의 이친수는 000, 001, 010, 100, 101, 110로, 총 6개가 존재합니다.
문제 설명
주어진 정수 N에 대하여, N자리 이친수를 모두 구하고 그 개수를 출력하는 문제를 해결하겠습니다.
문제
N을 입력받아 N자리 이친수를 모두 구하고 그 개수를 출력하라.
예시 입력
N = 3
예시 출력
6
문제 접근 방법
이 문제를 해결하기 위해서는 두 가지 접근 방법이 있습니다. 첫 번째는 재귀를 이용한 DFS(Depth-First Search)를 사용한 방법이고, 두 번째는 동적 프로그래밍(Dynamic Programming)을 이용한 방법입니다. 각 방법을 자세히 살펴보도록 하겠습니다.
1. 재귀 DFS를 이용한 방법
재귀를 사용하는 방법은, 이친수를 생성하기 위해 다음의 두 가지 규칙을 따릅니다:
- 현재 자리의 숫자가 0이라면 다음 자리에 0 또는 1을 모두 배치할 수 있습니다.
- 현재 자리의 숫자가 1이라면 다음 자리에 0만 배치할 수 있습니다.
이 규칙에 따라서 이친수를 생성하는 재귀 함수를 작성할 수 있습니다. 다음은 그 구현입니다:
def count_ichin(N, current_sequence, last_digit):
if len(current_sequence) == N:
return 1
count = 0
if last_digit == 0:
count += count_ichin(N, current_sequence + '0', 0)
count += count_ichin(N, current_sequence + '1', 1)
else:
count += count_ichin(N, current_sequence + '0', 0)
return count
N = 3
result = count_ichin(N, '', 0)
print(result)위 코드는 이친수를 생성하기 위한 재귀함수 count_ichin()을 정의하였고, 초기값으로 N과 빈 문자열을 전달합니다. 마지막 자리 숫자는 0으로 시작합니다.
2. 동적 프로그래밍을 이용한 방법
이친수를 구할 때, 동적 프로그래밍을 사용하면 메모이제이션을 통해 보다 효율적으로 문제를 해결할 수 있습니다. 이친수(I(n))의 개수는 다음과 같은 점화식으로 정의할 수 있습니다:
I(n) = I(n-1) + I(n-2)이 식의 의미는 다음과 같습니다:
- n-1의 자리에 0을 둘 경우: 이친수의 개수는 I(n-1)이다.
- n-2의 자리에 10을 둘 경우: 이 친수의 개수는 I(n-2)이다.
이제 이 점화식을 바탕으로 동적 프로그래밍을 구현하겠습니다:
def find_ichin_count(N):
if N == 1:
return 1
elif N == 2:
return 1
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = 1
for i in range(3, N + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[N]
N = 3
result = find_ichin_count(N)
print(result)위 코드를 통해, 이친수를 구하는 동적 프로그래밍 방식도 효율적으로 구현되었습니다.
비교 및 선택
재귀 방식은 이해하기 쉬우나, 큰 N 값에 대해서는 비효율적일 수 있습니다. 반면, 동적 프로그래밍 방식은 메모리를 사용하여 이전 계산 결과를 재사용하기 때문에 성능이 좋습니다. 일반적으로 N 값이 클 경우 동적 프로그래밍을 사용하는 것이 좋습니다.
결론
이번 강좌에서는 이친수 구하기 문제에 대해 다루어 보았습니다. 재귀와 동적 프로그래밍 두 가지 방법을 통해 이친수를 구하는 방법을 배웠습니다. 이 문제를 통해 알고리즘 문제 해결 능력을 키울 수 있기를 바랍니다.
감사합니다!