코테 - 파스칼 삼각형 n번째 행 반환 5가지 방법

파스칼 삼각형의 n번째 행은 이항계수를 나타내며, 각 요소는 C(n,k)로 계산됩니다. 아래는 C 언어를 사용해 n번째 행을 반환하는 5가지 방법으로, 코딩 테스트 준비에 유용합니다. (n은 0-based 인덱스)

방법 1: 조합 공식 사용

이항계수 C(n,k)를 직접 계산하여 n번째 행을 생성합니다.

#include 
#include 

long long binomial(int n, int k) {
    if (k < 0 || k > n) return 0;
    long long res = 1;
    for (int i = 0; i < k; i++) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

int* getRow(int n, int* returnSize) {
    *returnSize = n + 1;
    int* row = (int*)malloc((n + 1) * sizeof(int));
    for (int k = 0; k <= n; k++) {
        row[k] = (int)binomial(n, k);
    }
    return row;
}

int main() {
    int n = 4, returnSize;
    int* row = getRow(n, &returnSize);
    printf("행 %d: ", n);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", row[i]);
    }
    printf("\n");
    free(row);
    return 0;
}
        

방법 2: 이전 행에서 계산

파스칼 삼각형의 속성을 이용해 이전 행의 값을 사용해 다음 행을 계산합니다.

#include 
#include 

int* getRow(int n, int* returnSize) {
    *returnSize = n + 1;
    int* row = (int*)malloc((n + 1) * sizeof(int));
    row[0] = 1;
    for (int i = 1; i <= n; i++) {
        int* prev = (int*)malloc((i + 1) * sizeof(int));
        for (int j = 0; j < i; j++) prev[j] = row[j];
        prev[i] = 1;
        for (int k = 1; k < i; k++) {
            row[k] = prev[k - 1] + prev[k];
        }
        row[i] = 1;
        free(prev);
    }
    return row;
}

int main() {
    int n = 4, returnSize;
    int* row = getRow(n, &returnSize);
    printf("행 %d: ", n);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", row[i]);
    }
    printf("\n");
    free(row);
    return 0;
}
        

방법 3: 단일 배열 최적화

단일 배열을 사용해 메모리를 절약하며, 이전 값을 참조해 다음 값을 계산합니다.

#include 
#include 

int* getRow(int n, int* returnSize) {
    *returnSize = n + 1;
    int* row = (int*)calloc((n + 1), sizeof(int));
    row[0] = 1;
    for (int i = 1; i <= n; i++) {
        int prev = row[0];
        for (int k = 1; k < i; k++) {
            int temp = row[k];
            row[k] = prev + row[k];
            prev = temp;
        }
        row[i] = 1;
    }
    return row;
}

int main() {
    int n = 4, returnSize;
    int* row = getRow(n, &returnSize);
    printf("행 %d: ", n);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", row[i]);
    }
    printf("\n");
    free(row);
    return 0;
}
        

방법 4: 재귀적 접근

재귀적으로 이전 행을 계산하여 n번째 행을 구합니다.

#include 
#include 

void generateRow(int* prev, int prevSize, int* curr, int currSize) {
    if (currSize == 0) return;
    curr[0] = 1;
    for (int k = 1; k < currSize - 1; k++) {
        curr[k] = prev[k - 1] + prev[k];
    }
    curr[currSize - 1] = 1;
}

int* getRow(int n, int* returnSize) {
    *returnSize = n + 1;
    int* row = (int*)calloc((n + 1), sizeof(int));
    if (n == 0) {
        row[0] = 1;
        return row;
    }
    int* prev = getRow(n - 1, returnSize);
    generateRow(prev, n, row, n + 1);
    free(prev);
    return row;
}

int main() {
    int n = 4, returnSize;
    int* row = getRow(n, &returnSize);
    printf("행 %d: ", n);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", row[i]);
    }
    printf("\n");
    free(row);
    return 0;
}
        

방법 5: 수학적 비율 사용

각 항목을 이전 항목의 비율로 계산하여 n번째 행을 생성합니다.

#include 
#include 

int* getRow(int n, int* returnSize) {
    *returnSize = n + 1;
    int* row = (int*)malloc((n + 1) * sizeof(int));
    row[0] = 1;
    for (int k = 1; k <= n; k++) {
        row[k] = (int)((long long)row[k - 1] * (n - k + 1) / k);
    }
    return row;
}

int main() {
    int n = 4, returnSize;
    int* row = getRow(n, &returnSize);
    printf("행 %d: ", n);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", row[i]);
    }
    printf("\n");
    free(row);
    return 0;
}
        

설명

방법 1: 조합 공식 사용: 이항계수 C(n,k)를 직접 계산하여 각 요소를 생성합니다. 간단하지만 큰 숫자에서 오버플로우 가능성이 있습니다.

방법 2: 이전 행에서 계산: 파스칼 삼각형의 속성(각 요소는 이전 행의 두 요소의 합)을 이용해 반복적으로 행을 생성합니다.

방법 3: 단일 배열 최적화: 단일 배열을 사용해 메모리를 절약하며 이전 값을 참조해 계산합니다.

방법 4: 재귀적 접근: 재귀적으로 이전 행을 계산하여 현재 행을 생성합니다. 이해하기 쉽지만 메모리 사용량이 많을 수 있습니다.

방법 5: 수학적 비율 사용: 각 항목을 이전 항목의 비율((n-k+1)/k)을 사용해 계산하여 효율적으로 행을 생성합니다.

각 코드 예시는 n=4일 때 출력 예시: 행 4: 1 4 6 4 1을 생성합니다. 메모리 해제를 포함하여 코딩 테스트에서 요구되는 완전한 구현을 제공했습니다.

각 방법은 메모리 사용량, 시간 복잡도, 코드 단순성 측면에서 장단점이 있습니다. 코딩 테스트에서 요구되는 효율성과 상황에 따라 적합한 방법을 선택하세요!