본 글에서는 자바스크립트로 이친수를 구하는 알고리즘 문제를 다루겠습니다. 이친수는 중복 괄호와 같은
구조적 개념과 관련된 수학적 개념으로, 이 문제는 프로그래밍 면접에서 종종 등장합니다.
따라서 이 문제를 확실히 이해하고 풀 수 있는 방법을 찾아보겠습니다.
이친수란?
이친수는 0과 1로 구성된 길이 N의 문자열 중에서 다음의 규칙을 따르는 것들입니다:
- 문자열의 첫 번째와 마지막 문자는 0이어야 한다.
- 문자열 내 1의 개수는 항상 1개 이상이어야 하며, 연속된 1은 없으며, 각 1은 반드시 0으로 둘러싸여 있어야 한다.
예를 들어, 길이 5의 이친수는 00000, 01000, 00100, 00010, 00001,
01010, 01100, 10000 등이 있습니다. 이친수는 피보나치 수열과 같으며,
N 길이에 따라 다른 개수를 받을 수 있습니다.
문제 설명
자연수 N이 주어질 때, 길이가 N인 이친수의 개수를 출력하는 문제입니다.
예를 들어, N = 5일 경우, 이친수의 개수를 구해야 하며,
그 결과는 8이어야 합니다.
해법
이 친수를 구하기 위해 재귀 호출이나 다이나믹 프로그래밍(DP) 방법을 사용할 수 있습니다.
아래는 이친수를 구하는 공식입니다.
- p(n) = p(n-1) + p(n-2) (n ≥ 2, p(0) = 1, p(1) = 1)
이 공식은 이친수를 재귀적으로 계산하는 방법입니다.
주의할 점은 n이 0일 때 1을 반환해야 한다는 점입니다.
또한, p(n-1)과 p(n-2)의 관계를 통해 이전 이친수 개수를 의미합니다.
알고리즘 구현
// 자바스크립트로 이친수를 만드는 함수입니다.
function countCatalanNumbers(n) {
// 이친수를 저장할 배열
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // 길이 0인 경우
dp[1] = 1; // 길이 1인 경우
// 다이나믹 프로그래밍을 사용해 이친수를 계산합니다.
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n]; // n 길이의 이친수 개수를 반환합니다.
}
// 함수 호출 예시
const n = 5; // N 값
console.log(`길이 ${n}의 이친수 개수는: ${countCatalanNumbers(n)}`);
진행 과정 설명
- 문제 이해하기: 자연수 N에 대해 이친수를 구하는 문제입니다.
- 다이나믹 프로그래밍 접근: 이친수를 구조적으로 정의합니다.
- 배열 초기화: dp 배열을 생성하여 기본 값을 설정합니다.
- 반복문 실행: 이친수의 개수를 배열에 저장하며 계산합니다.
- 결과 검증: 함수 출력으로 결과가 올바른지 검증합니다.
실행 결과
// 입력: N = 5
// 출력: 길이 5의 이친수 개수는: 8
결론
이 친수를 구하는 방법에 대해 알아보았으며, 다이나믹 프로그래밍을 통해 효율적으로 문제를 해결할 수 있었습니다.
이 문제는 프로그래밍 인터뷰에서 자주 출제되므로 알고리즘의 원리를 이해하고 구현할 수 있는 능력을 기르는 것이 중요합니다.