[C언어] 2차원, 3차원 배열을 통한 순차 자료구조의 사용 예시(테트리스 블록, 휴대폰 판매량, 선형 list)

순차 자료구조란?

 데이터는 다양한 방식으로 저장될 수 있는데, 메모리에 저장된 물리적 위치가 연속적으로 저장된 경우를 순차 자료구조라고 합니다.

 C에서는 배열을 통해서 순차 자료구조를 표현합니다. 그래서 메모리에 저장된 시작 위치를 알면 특정 자료의 위치를 쉽게 알 수 있다는 장점이 있습니다.

 반면에 자료들이 연속적으로 저장되어있어, 특정 자료를 특정 위치에 삽입하거나, 삭제할 경우 특정위치 뒤에있는 자료들을 모두 한칸씩 뒤로 이동해서 자리를 비워주거나, 특정위치에 삭제할 자료 뒤에있는 자료들을 모두 한칸씩 앞 당겨야 한다는 번거로운 단점이 있습니다. 

 

• 순차 자료구조의 사용 예시

순차 표현의 사용 예시로 첫번째는 테트리스의 블록 표현 방법이 예시가 있습니다. 

테트리스 블록 한개를 예로들어서, 이 블록의 표현 방법은 배열을 사용하여, 표현할 수 있습니다.

int block[4][4]={
		0,0,0,0,
                0,0,1,1,
                0,1,1,0,
                0,0,0,0};

 

(엥 저게 무슨말이지?) 2차원 배열을 사용한 저것이 어떻게 테트리스 블록이냐?! 궁금해 하실 수도 있습니다. 

#include <stdio.h>

int main(void) {
	int block[4][4] = {0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0 };
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (block[i][j] == 0)
				printf("  ");
			else if (block[i][j] == 1)
				printf("■");
		}
		printf("\n");
	}
	return 0;
}

 

배열에서 숫자 0은 공백으로, 숫자 1은 ■ 기호를 사용할 경우, 단순하지만 연산 처리과정이 엄~청빠른 컴퓨터는 단번에 우리가 쉽게 알아볼 수 있는 블록으로 출력해줍니다.. +_+

 

(저 블록에서 방향도 바꿔야 하지 않나?)..

 

우리는 3차원 배열을 사용해서 블록의 회전기능까지 갖고있는 배열을 만들 수 있습니다.

 

 바로!!!! 'rotation' 유무에 따라 기본 도형인지, 회전한 도형인지를 구분짓는, 두가지의 방법이 추가적으로 저장되어야 할 때 순차 자료구조의 특성을 갖는 3차원 배열을 사용하면 쉽게 저장이 가능합니다.

#include <stdio.h>

int main(void) {
	int block[][4][4] = {
		0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0 //이전의 블록, 기본 형태의 블록
		,0,0,0,0
		,0,1,0,0  //회전한 블록
		,0,1,1,0
		,0,0,1,0 
	};
	for (int z = 0; z < 2; z++) { 
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (block[z][i][j] == 0)
					printf("  ");
				else if (block[z][i][j] == 1)
					printf("■");
			}
			printf("\n");
		}printf("\n\n");
	}
	return 0;
}

내가 만약 기본적인 형태를 갖는 블록을 출력하고 싶다? block[0][i][j]를 출력하면 되고,

회전된 블록을 출력하고 싶을 경우에는 block[1][i][j]를 출력하면 되는 것입니다.

 

이처럼  배열의 첫 번째 원소부터 마지막 원소까지 연이어 메모리에 저장된 것을 순차 자료구조라고 합니다.

 위의 경우에서, 내가 특정한 index의 위치를 바꾸고 싶은 경우에는 쉽게 바꿀 수 있지만,

특정 index의 정보를 삭제하고 싶을 경우, 삭제할 뒤에있는 정보들의 index를 일일이 바꿔주지 않으면 저 도형은 우리가 알아볼 수 없는 도형이 되버립니다.

=> 원소 삽입 삭제가 비효율적이구나..?!를 알아 차릴 수 있습니다.

 

 

• 순차 자료구조의 사용 두번째 예시

예를들어 2020년  5월~8월, 2021년 5월~8월까지 휴대폰의 판매량을 순차적인 리스트로 표현한다면, 2차원 배열을 사용하면 쉽게 자료들을 나열할 수 있습니다.

연도       /  판매량	5월	6월	7월	8월
2020년	3515만대	3342만대	2951만대	4278만대
2021년	3215만대	3751만대	2845만대	4385만대

int salesRate[2][4]={
			{3515,3342,2951,4278},	//2020년 휴대폰 판매량
                        {3215,3751,2845,4385}   //2021년 휴대폰 판매량
                     };

 2차원 배열로 판매량 list를 구현했지만, 실제로 메모리상에서는 배열의 index를 기준으로 하는 행 우선 순서에 따라 1차원 배열이 저장되는 물리적 순서로 저장이 됩니다.

#include <stdio.h>

int main(void) {
	int n = 0;	int* p = NULL;
	int salesRate[2][4] = {{3515,3342,2951,4278},{3215,3751,2845,4385}};

	p = &salesRate[0][0];
	for (int i = 0; i < sizeof(salesRate) / sizeof(salesRate[0][0]); i++) {
		printf("2차원 배열의 주소 : %u ,sale[%d][%d]=%d\n", p, i / 4, i % 4,*p);
		p++;
	}
	return 0;
}

옆에 결과를 볼 수 있으면 알 수 있지만,

행 우선 순서에 따라 시작 배열의 주소 끝 두 자리수가 84에서, index가 1씩 늘어날 때마다 88, 92 ...+(int)자료형의 크기인 4씩 연속적으로 저장됩니니다.

 

 

 

2차원 배열에서 열을 기준으로 저장하는 방식인 열 우선 순서 방법도 있지만, 기본적인 프로그래밍에서는 컴파일러에 따라 결정되는데, C 컴파일러는 행 우선 순서 방법을 사용합니다. 

 

• 순차 자료구조의 사용 세번째 예시

배열을 활용한 순차 list는 수학을 배울때 많이 쓰였던 다항식에서도 사용될 수 있습니다.  

1차원 배열을 사용하여 2x^3+7x^2+0x^1+8x^0 이 다항식을 표현 할 때 최고차항의 계수를 차례대로 index 0부터 저장할 수 있습니다.

int MAX_INDEX=3;
float coef[MAX_INDEX]={2,7,0,8}

(계수는 표현을 했는데 차수(제곱,세제곱 등등)는 어떻게 표현하지? 2차원 배열을 써야하나?)라는 의문점이 문득 들 수 있습니다.

 

최고차항이 낮은 다항식의 경우, 위의 예제에서 차수는 계수를 저장한 index에서 가장 낮은 index=0이 최고차항인 x^세제곱이고, index1=x^제곱....을 표현한다! 라고 계수저장과 반대로 이해하시면 됩니다. 

 그렇다면 10x^1000차수 +10x^2+100 의 다항식같은 경우에는 비어있는 index값, 계수값을 전부 0으로 채워야 할까요?

결론은 No!!!! (손아픕니다..)

 

이런 경우는 희소 다항식이라고 표현하고, 2차원 배열을 이용합니다. 2차원 배열이다! [][] ==내가 원하는 두가지의 정보를 연속적으로 저장할 수 있다!!!!

 2차원 배열을 사용해 한개의 행에 최고차항이 큰 순서부터 계수와 차수를 저장하면 희소 다항식을 쉽게 표현할 수 있습니다. 

int poly[][]={ //<계수, 지수>
	{10,1000} //첫번째 값은 계수, 두번째 값은 차수!
        ,{10,2},
        {10,0}
        };

  # degree = 차수

 #Coefficient 줄여서 coef=계수

#polynomial 줄여서 poly = 다항식

 

한방 정리

순차 자료구조	장점	단점
	배열을 활용해 정보를 연이어 저장 할 수 있다.	특정 원소를 삽입, 삭제 할 경우 추가적인 overhead가 발생한다.
	물리적 주소(1차원 배열)의 순서로 간단하게 구성되어 있다.
	읽기, 쓰기, 순차 접근이 좋다.	삽입, 삭제가 비효율적이다.

긴 글 읽어 주셔서 감사합니다.

모두 화이팅!!