1. 서론
코딩 테스트는 많은 기업에서 지원자의 알고리즘적 사고와 문제해결 능력을 평가하기 위해
실시합니다. 다양한 주제와 난이도가 존재하는 문제들 중에서, “이친수 구하기”는
DP(Dynamic Programming) 기법을 활용할 수 있는 좋은 예시입니다. 이번 글에서는 이친수 구하는 문제를
상세히 설명하고, C#을 사용하여 문제를 해결하는 과정을 단계별로 진행해보겠습니다.
2. 문제 설명
이친수(Binary Number)는 0과 1로 이루어진 숫자 중에서,
두 개의 1이 연속으로 나타나지 않는 수를 의미합니다.
예를 들어, 0과 1로 이루어진 이친수의 예시는 다음과 같습니다:
0, 1, 010, 001, 100, 0101, 1010, 1001, 0001 등입니다.
반면 11, 00000이나 1111은 이친수가 아닙니다.
예를 들어 N이 주어질 때, N 길이의 이친수의 개수를 구하라는 문제가 주어집니다.
2.1. 입력 형식
– 첫 번째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 1,000)
2.2. 출력 형식
– N 길이의 이친수의 개수를 출력한다.
2.3. 예제
Input:
3
Output:
3
이 경우 이친수는 {001, 010, 100} 총 3가지가 있습니다.
3. 문제 해결 방안
이 문제를 해결하기 위해서는 다음과 같은 접근 방식이 필요합니다.
3.1. DP 배열 정의
우리는 Dynamic Programming을 활용하여 이 문제를 해결할 수 있습니다.
먼저, DP 배열을 정의하여 N 길이의 이친수의 개수를 저장합니다.
– DP[i]는 길이 i의 이친수의 개수를 저장합니다.
3.2. 상태 전이 식
현재 상태에서 다음과 같은 상태 전이 식을 도출할 수 있습니다.
– 길이 i의 이친수는 길이 (i-1)에서 마지막 자리가 0이라면 이어붙이기 가능하고,
– 길이 (i-2)에서 마지막 자리가 1이라면 10으로 이어붙일 수 있습니다.
따라서 다음과 같이 표현할 수 있습니다:
– DP[i] = DP[i-1] + DP[i-2]
3.3. 초기 조건 설정
– DP[1] = 2 (이친수: 0, 1)
– DP[2] = 3 (이친수: 00, 01, 10)
4. C# 코드 구현
위의 논리를 바탕으로 C# 코드를 구현해보겠습니다.
using System;
class Program
{
static void Main(string[] args)
{
int N = int.Parse(Console.ReadLine());
long[] dp = new long[N + 1];
// 초기 조건 설정
dp[1] = 2; // 이친수: 0, 1
if (N > 1)
{
dp[2] = 3; // 이친수: 00, 01, 10
}
// DP 배열 계산
for (int i = 3; i <= N; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
// 결과 출력
Console.WriteLine(dp[N]);
}
}
5. 코드 설명
위 코드에서는 사용자로부터 N을 입력받고, DP 배열을 초기화한 후
반복문을 통해 DP 배열을 채워나갑니다.
그리고 마지막에 DP[N]을 출력하면 N 길이의 이친수 개수를 확인할 수 있습니다.
5.1. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(N)입니다. N이 최대 1,000일 경우에도
빠르게 동작하여 많은 양의 데이터를 처리할 수 있습니다.
5.2. 공간 복잡도
공간 복잡도 또한 O(N)으로 DP 배열을 사용하는 만큼
메모리 요구량이 증가합니다. 그러나 N이 작기 때문에
메모리 사용량은 크게 문제가 되지 않습니다.
6. 마무리
이번 강좌에서는 “이친수 구하기” 문제를 다루어보았습니다.
Dynamic Programming의 기법을 통해 문제를 단계적으로 해결하는
과정과 C# 코드 구현을 설명했습니다.
이러한 유형의 문제는 실제 코딩 테스트에서 자주 출제되기 때문에,
연습을 통해 충분히 익혀두시면 좋습니다.
코딩 테스트를 준비하면서 더 많은 문제를 풀어보시고,
각 문제에 대해 다양한 접근 방식과 최적화를 고민해보시길 바랍니다.
감사합니다!