n × n 크기의 2차원 배열이 주어졌을 때, 정수형 행렬의 요소들을 대각선 아래 방향으로 순서대로 출력하는 것이 이번 글의 목표입니다.
여기서 '대각선 아래 방향으로 출력한다'는 것은 아래 그림처럼 행렬의 왼쪽 위에서 시작하여 오른쪽 위를 향해 한 칸씩 이동하면서, 각 위치마다 대각선을 따라 아래쪽(왼쪽 아래)으로 내려가며 요소를 출력하는 방식을 의미합니다.
즉, 먼저 1을 출력하고, 다음으로 첫 번째 행의 2로 이동해 출력한 뒤, 대각선을 따라 아래로 내려가 4를 출력합니다. 이런 식으로 마지막 요소까지 반복하면 전체 행렬이 지그재그 형태의 대각선 순서로 출력됩니다.
입력 및 출력 예시
입력: Matrix [3][3] = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 }}
출력: 1 2 4 3 5 7 6 8 9알고리즘
핵심 아이디어는 두 단계로 나누는 것입니다. 먼저 첫 번째 행의 각 열을 시작점으로 삼아 대각선 아래로 이동하며 출력하고, 이후 마지막 열의 각 행을 시작점으로 삼아 같은 방식으로 출력합니다. 대각선 이동 시에는 행 인덱스(row)는 1씩 증가하고, 열 인덱스(col)는 1씩 감소합니다.
int diagonally_down(int mat[n][n]) START STEP 1: DECLARE i, j, row, col AS INT STEP 2: LOOP FOR i = 0 AND i < n AND i++ SET row = 0 SET col = i LOOP WHILE col >= 0 PRINT mat[row][col] INCREMENT row BY 1 AND DECREMENT col BY 1 END WHILE END FOR STEP 3: LOOP FOR j = 1 AND j < n AND j++ SET row = j SET col = n-1 LOOP WHILE row < n PRINT mat[row][col] INCREMENT row BY 1 AND DECREMENT col BY 1 END WHILE END FOR STOP
C 언어 구현 예제
#include <stdio.h>
#define n 3
int diagonally_down(int mat[n][n]){
int i, j, row, col;
// 첫 번째 행 기준으로 위쪽 삼각형 영역 출력
for (i = 0; i < n; i++){
row = 0;
col = i;
while(col >= 0) // 첫 번째 행에서부터 대각선 아래로 이동
{
printf("%d ", mat[row++][col--]);
}
}
// 마지막 열 기준으로 아래쪽 영역 출력
for (j = 1; j < n; j++){
row = j;
col = n-1;
while(row<n) // 마지막 열에서부터 대각선 아래로 이동
{
printf("%d ", mat[row++][col--]);
}
}
}
int main(int argc, char const *argv[]){
int mat[][n] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonally_down(mat);
return 0;
}실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
1 2 4 3 5 7 6 8 9
코드 동작 원리 정리
- 첫 번째 for 루프: 첫 번째 행의 0번째 열부터 마지막 열까지를 시작점으로 하여, 각 시작점에서 왼쪽 아래 대각선 방향(
row++,col--)으로 이동하며 요소를 출력합니다. 이 과정에서 행렬의 위쪽 삼각형 영역이 처리됩니다. - 두 번째 for 루프: 마지막 열의 1번째 행부터 마지막 행까지를 시작점으로 하여 같은 방식으로 대각선을 따라 출력함으로써 나머지 아래쪽 영역을 처리합니다.
이 알고리즘은 총 n²개의 모든 요소를 정확히 한 번씩만 방문하므로, 시간 복잡도는 O(n²)입니다. 추가적인 메모리 없이 입력된 행렬 그대로 사용하기 때문에 공간 복잡도는 O(1)입니다.