코테 - 행렬의 전치 찾기 5가지 방법

행렬의 전치는 행과 열을 바꾼 행렬입니다. m x n 행렬의 전치는 n x m 행렬이 됩니다. 아래는 C 언어를 사용해 행렬의 전치를 찾는 5가지 방법으로, 코딩 테스트 준비에 유용합니다.

방법 1: 새로운 행렬 생성

새로운 행렬을 동적 할당하여 전치 행렬을 생성하고 값을 복사합니다.

#include <stdio.h>
#include <stdlib.h> 

void transpose(int** matrix, int m, int n, int** result) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            result[j][i] = matrix[i][j];
        }
    }
}

void printMatrix(int** matrix, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int m = 3, n = 3;
    int* matrix[3] = { (int[]){1, 2, 3}, (int[]){4, 5, 6}, (int[]){7, 8, 9} };
    int** result = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) result[i] = (int*)malloc(m * sizeof(int));
    
    printf("원본 행렬:\n");
    printMatrix(matrix, m, n);
    transpose(matrix, m, n, result);
    printf("\n전치 행렬:\n");
    printMatrix(result, n, m);
    
    for (int i = 0; i < n; i++) free(result[i]);
    free(result);
    return 0;
}
        

방법 2: 제자리 전치 (정방 행렬)

정방 행렬(m = n)에서 추가 메모리 없이 원본 행렬의 요소를 교환합니다.

#include <stdio.h>

void transpose(int matrix[][3], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

void printMatrix(int matrix[][3], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n = 3;
    int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    
    printf("원본 행렬:\n");
    printMatrix(matrix, n);
    transpose(matrix, n);
    printf("\n전치 행렬:\n");
    printMatrix(matrix, n);
    return 0;
}
        

방법 3: 1차원 배열로 변환 후 전치

행렬을 1차원 배열로 변환한 후 인덱스 매핑으로 전치 행렬을 생성합니다.

#include <stdio.h>
#include <stdlib.h>  

void transpose(int* matrix, int m, int n, int* result) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            result[j * m + i] = matrix[i * n + j];
        }
    }
}

void printMatrix(int* matrix, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d ", matrix[i * cols + j]);
        }
        printf("\n");
    }
}

int main() {
    int m = 3, n = 3;
    int matrix[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int* result = (int*)malloc(m * n * sizeof(int));
    
    printf("원본 행렬:\n");
    printMatrix(matrix, m, n);
    transpose(matrix, m, n, result);
    printf("\n전치 행렬:\n");
    printMatrix(result, n, m);
    
    free(result);
    return 0;
}
        

방법 4: 동적 할당과 포인터 스왑

동적 할당된 행렬에서 포인터를 스왑하여 전치 행렬을 생성합니다 (정방 행렬용).

#include <stdio.h>
#include <stdlib.h> 

void transpose(int*** matrix, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = (*matrix)[i][j];
            (*matrix)[i][j] = (*matrix)[j][i];
            (*matrix)[j][i] = temp;
        }
    }
}

void printMatrix(int** matrix, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n = 3;
    int** matrix = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) matrix[i] = (int*)malloc(n * sizeof(int));
    int values[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) matrix[i][j] = values[i][j];
    
    printf("원본 행렬:\n");
    printMatrix(matrix, n);
    transpose(&matrix, n);
    printf("\n전치 행렬:\n");
    printMatrix(matrix, n);
    
    for (int i = 0; i < n; i++) free(matrix[i]);
    free(matrix);
    return 0;
}
        

방법 5: 재귀적 전치 (정방 행렬)

재귀적으로 요소를 교환하여 정방 행렬의 전치를 수행합니다.

#include <stdio.h>

void transposeRecursive(int matrix[][3], int i, int j, int n) {
    if (i >= n || j >= n) return;
    if (i < j) {
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }
    transposeRecursive(matrix, i, j + 1, n);
    if (j == n - 1) transposeRecursive(matrix, i + 1, i + 1, n);
}

void printMatrix(int matrix[][3], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n = 3;
    int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    
    printf("원본 행렬:\n");
    printMatrix(matrix, n);
    transposeRecursive(matrix, 0, 0, n);
    printf("\n전치 행렬:\n");
    printMatrix(matrix, n);
    return 0;
}
        

각 방법은 메모리 사용과 코드 복잡성 측면에서 장단점이 있습니다. 새로운 행렬 생성(방법 1)은 범용적이며, 제자리 전치(방법 2, 5)는 정방 행렬에 효율적입니다. 1차원 배열(방법 3)은 메모리 접근을 단순화하며, 포인터 스왑(방법 4)은 동적 할당에 익숙해지는 데 유용합니다.

설명 및 출력 예시

입력 행렬 (3x3):

1 2 3

4 5 6

7 8 9

출력 전치 행렬:

1 4 7

2 5 8

3 6 9

• 방법 1: 새로운 행렬 생성: 추가 메모리를 사용하여 전치 행렬을 생성. m x n 행렬에 범용적. 시간 복잡도 O(mn), 공간 복잡도 O(mn).
• 방법 2: 제자리 전치 (정방 행렬): 추가 메모리 없이 요소를 교환. 정방 행렬(n x n)에만 적용 가능. 시간 복잡도 O(n^2), 공간 복잡도 O(1).
• 방법 3: 1차원 배열로 변환 후 전치: 행렬을 1차원 배열로 처리하여 인덱스 매핑으로 전치. 메모리 접근이 단순. 시간 복잡도 O(mn), 공간 복잡도 O(mn).
• 방법 4: 동적 할당과 포인터 스왑: 동적 할당된 행렬에서 요소를 교환. 정방 행렬에 최적화. 시간 복잡도 O(n^2), 공간 복잡도 O(1) (입력 행렬 제외).
• 방법 5: 재귀적 전치 (정방 행렬): 재귀를 사용하여 요소를 교환. 교육적이며, 정방 행렬에만 적용. 시간 복잡도 O(n^2), 공간 복잡도 O(n^2) (재귀 스택 포함).

특징

• 모든 코드는 3x3 행렬을 예제로 사용하며, m x n 행렬에 일반화 가능(방법 2, 4, 5는 정방 행렬 전용).
• 코딩 테스트에서는 방법 1 또는 2가 가장 일반적이며, 방법 3은 메모리 접근을 단순화할 때 유용.
• 동적 메모리 할당과 해제를 포함하여 메모리 누수를 방지.
• 블로그용으로 깔끔한 HTML/CSS 스타일을 적용하여 코드 가독성을 높였습니다.