자바스크립트 코딩테스트 강좌, 부녀회장이 될 테야

문제 정의

오늘의 문제는 “부녀회장이 될 테야”입니다. 이 문제는 층과 호에 대한 정보가 주어지면, 특정층의 특정호에 사는 사람의 수를 계산하는 문제입니다.

부녀회장은 다음과 같은 규칙으로 관리합니다. 각 호에는 한 가구가 살고 있으며, 각 층의 1호에는 항상 1명이 살고 있습니다. 이후 각 호의 인원 수는 그 아래 층의 동일한 호 인원과 그 아래 층의 바로 왼쪽 호 인원 수의 합으로 계산됩니다.

문제 설명

입력:
– 첫 번째 입력 값은 테스트 케이스의 수 T (1 <= T <= 1000)입니다.
– 각 테스트 케이스는 두 개의 정수 K (0 <= K <= 14)와 N (1 <= N <= 14)로 구성됩니다.
– K는 층의 수, N은 해당 층의 호수를 나타냅니다.

출력:
각 테스트 케이스마다 K층 N호의 사람 수를 출력해야 합니다.

예시 입력 및 출력

문제 풀이 과정

1. 결합 함수 이해하기

이 문제의 핵심은 동적 계획법(Dynamic Programming)을 이용하여 인원 수를 계산하는 것입니다. 기본적으로 아래층의 호수의 인원 수를 이용해 현재 층의 사람 수를 계산합니다. 계산 과정은 다음과 같습니다.

계산 방법

def count_people(K, N):
    if K == 0:
        return N
    if N == 1:
        return 1
    return count_people(K-1, N) + count_people(K, N-1)

2. 반복문을 통한 진행

재귀 함수는 코드가 복잡해질 수 있기 때문에 반복문을 통해 효율적으로 계산하는 방법을 사용하겠습니다. 먼저 K층의 사람 수를 미리 저장한 2차원 배열을 생성합니다.

3. 구현

function countPeople(T, cases) {
    const results = [];
    const dp = Array.from(Array(15), () => Array(15).fill(0));

    for (let i = 0; i <= 14; i++) {
        dp[0][i] = i;  // 0층의 경우 i명
    }
    
    for (let k = 1; k <= 14; k++) {
        dp[k][1] = 1;  // 1호의 경우 무조건 1명
        for (let n = 2; n <= 14; n++) {
            dp[k][n] = dp[k-1][n] + dp[k][n-1];  // 위층과 왼쪽 호수 사람 수를 합함
        }
    }

    for (let i = 0; i < T; i++) {
        let k = cases[i][0];
        let n = cases[i][1];
        results.push(dp[k][n]);
    }
  
  return results;
}

const T = 2;
const cases = [[1, 3], [2, 3]];
console.log(countPeople(T, cases)); // 출력 결과: [3, 6]

결론

우리가 구현한 함수는 T개의 테스트 케이스에 대해 정확하고 빠르게 각 층과 호수의 인원 수를 계산합니다. 이 문제는 동적 계획법의 기본 개념을 잘 보여주는 예제입니다. 동적 계획법을 적절히 사용하면, 같은 유형의 문제를 효율적으로 해결할 수 있습니다.

이 알고리즘을 통해 코딩 테스트를 준비하면서 프로그래밍의 여러 측면을 강화할 수 있습니다. 이번 강좌를 통해 자바스크립트 코딩 테스트에 대한 이해도를 높이길 바랍니다.