자료구조 기본

자료구조에서 배열까지

알고리즘에서 배열은 가장 기본이 되는 자료구조 입니다. 자료구조를 이해하기 위한 첫번째 관문이 되는거죠.

알고리즘 초반에는 용어의 다양한 측면을 이해하고 익숙해지는데 시간을 좀 더 투자할 필요가 있습니다. 자료구조(data structure) 부터 배열까지 가보겠습니다.

먼저 자료란 뭘까요?

자료(資料, data, 데이터, 문화어: 데타)는 문자, 숫자, 소리, 그림, 영상, 단어 등의 형태로 된 의미 단위이다.
위키피디아

문자, 숫자, 소리 등등이 나옵니다. 이것들은 실세계의 자료이고 컴퓨터의 자료는 0과1로 이루어진 메모리에 100% 구현할 수 있습니다. 뭐 자료중에 실수 표현 같은 무한의 영역을 표현하는 것은 기술적 한계가 있을지 모르겠습니다.

무한으로 계속되는 원주율 3.1415926… 의 경우 구글이 2019년도에 31.4조 자리(digits)까지 연산했다는 소식이 있습니다. 뭐 그런 것들 말고는 실세계 데이터의 대부분은 컴퓨터에 구현이 됩니다.

사진은 그림이지만 마찬가지로 0과 1로 저장할 수 있고, 구글 어스같은 지형의 3D 데이터도 벡터와 3차원 배열을 사용하여 컴퓨터에서 표현이 가능합니다.

다음에 구조(structure) 란 뭘까요? 건물의 구조를 이해한다는 것은 건물의 짜임새 예를 들어 기둥과 지붕의 상호관계 등을 이해한다는 말입니다. 데이터 구조라는 것도 마찬가지로 데이터 간에 여러가지 관계가 있습니다.

형태가 같은 데이터가 모이기도 하고(int 현 배열) 형태가 다른 데이터가 모이기도 합니다 (C structure C언어 구조체). 현대의 프로그래밍 기술중에 객체지향 프로그래밍이란 방법론이 있습니다. 여기서는 객체(Object)가 자료형태가 됩니다.(data type) 이렇듯 데이터의 특성이 다르고 데이터간의 관계도 존재하며 알고리즘이 어떤 데이터를 선택해야 할지도 차이가 있습니다.

이 모든 개념을 총망라해서 한 단어로 표현하면 자료구조(Data Structure)가 됩니다. 어려운 단어처럼 느껴졌다면 당연한 겁니다. 여러개의 의미가 들어있고 그 의미는 이제부터 하나씩 여러분의 사고속에서 밝혀 나가야 합니다.

이제 자료구조에서 구조(Structure)적인 부분을 제외하고 순수한 자료를 보겠습니다. 자료는 위키피디아의 인용처럼 문자, 숫자, 그림 등이 있습니다.

실제 사람이 글씨를 쓰면 문자 자료가 됩니다. 문자도 쓸 수 있고 숫자도 쓸 수 있겠죠? 궁극적으로 사람이 사용하는 모든 문자와 숫자는 컴퓨터에서 0과 1로 저장되어 취급됩니다. 그렇게 취급하는 주체는 컴퓨터의 두뇌라 말할 수 있는 CPU입니다.

0과 1은 이진법이니까 사람이 주로 사용하는 10진법까지는 무난히 커버가 됩니다. 2의 배수가 아니라서 좀 불편하긴 하지만 큰 문제는 없습니다. 컴퓨터의 이름이 계산기인 만큼 숫자는 당연히 커버가 됩니다. 그리고 좀 복잡하긴 하지만 실수나 복소수 등도 사용할 수 있습니다. 이제 컴퓨터가 숫자를 거의 완벽히 처리할 수 있다는 것을 알았습니다.

그렇다면 문자나 그림 등은요?

인내심을 가지고 단계적으로 봅시다. 문자 역시 숫자로 표현합니다. 컴퓨터 개발의 초창기에는 인간의 언어는 영어만 사용가능했는데 이는 아스키 코드(ASCII CODE) 체계를 사용했기 때문입니다. 후에 유니코드로 확장하면서 전세계인의 언어를 통합한 코드를 사용할 수 있게 되었습니다.

아스키 코드표는 아래의 링크에서 확인할 수 있습니다.

아스키 코드표 (ASCII CODE) 코딩지식 1 – 스무디코딩

아스키코드 출력 예제 C++

아스키코드를 이해하면 컴퓨터의 작동원리에 대하여 한차원 더 깊게 알 수 있기 때문에 C와 C++ 초기에 반드시 알아야 하는 내용입니다. 아스키코드에는 한글은 없습니다. 한글을 알기 위해서는 유니코드를 배워야 하지만 아스키코드가 기본입니다.

문자는 메모리안에서 숫자로 저장되며 출력형식을 지정하는 것 만으로 코드의 복호화가 가능합니다. 아스키코드도 하나의 암호화입니다. 기초적인 암호문이죠.

딱히 누구한테 감출 필요가 있어서 암호를 만든게 아닙니다. 인간의 언어와 컴퓨터의 언어가 외계어 수준으로 다르기 때문입니다.

그러나 놀랍게도 숫자만으로 이 세상의 모든 것을 표현할 수 있다는 것을 깨달은 과학자들은 인간과 컴퓨터가 소통할 수 있도록 중간적인 소프트웨어를 만들어 냅니다. 그것이 바로 C++ 같은 프로그래밍 언어입니다.

소프트웨어 프로그래머가 하는 일은 인간의 요구사항을 명령으로 만들어서 컴퓨터에게 일을 시키는 일입니다. 언뜻 보면 노가다 같은데 노가다가 맞습니다;;;

이 세상에는 컴퓨터에게 시킬 일들이 끝도없이 많은데 노가다를 뛸 프로그래머는 부족한 실정입니다. 정확히는 숙련된 프로그래머(소프트웨어 장인, 엔지니어)가 부족합니다. 한 사람의 숙련된 프로그래머는 컴퓨터의 힘을 빌려 무한에 가까운 일을 시킬 수 있기 때문이죠.

암튼 자료구조는 조금 시간이 걸리더라도 아주 밑바닥 부터 흝고 지나가야 의미가 있습니다.

다음은 C++로 아스키코드를 출력합니다. int( ) 와 char ( ) 연산자(사용법은 함수나 비슷함) 를 사용하여 인코딩(encoding 코드화, 부호화)과 디코딩(decoding 복호화)을 합니다.

인코딩은 문자에서 숫자로 디코딩은 숫자에서 다시 문자로 돌리는 처리를 의미합니다.

#include <iostream>

using std::cout;
using std::endl;

int main() {

	char ascii1 = 'A' , ascii2 = 'z';
	
	cout << "아스키코드 A : " << int(ascii1) << endl;
	cout << "아스키코드 z : " << int(ascii2) << endl;

	cout << "[아스키코드 출력하기] " << endl;
	for (int i = int(ascii1); i <= int(ascii2) ; i++)
	{
		cout << char(i);
		if (i % 7 == 0) cout << endl;
	}

	return 0;
}

아스키코드 A : 65
아스키코드 z : 122
[아스키코드 출력하기]
ABCDEF
GHIJKLM
NOPQRST
UVWXYZ[
\]^_`ab
cdefghi
jklmnop
qrstuvw
xyz

결과값을 보면 대문자 A가 65로 저장되고 B, C, D 가 각각 66, 67, 68 처럼 연속으로 이어지는 것을 볼 수 있습니다. 그리고 대문자 Z와 소문자 a의 사이에 다른 문자도 들어가 있죠? 구체적인 내용은 아스키코드표에서 확인할 수 있습니다.

마지막으로 한가지 의문을 풀고 가겠습니다. 숫자나 문자는 스크린에 보일 뿐인데 이것은 무엇인가요?

– > 질문내용이 어렵습니다. 아마 모니터 스크린상에 보이는 것에 대한 질문이라 생각합니다. 아스키코드는 어떻게 보이는 것이냐?

우리가 스크린에서 0, 1, 2, 3 과 같이 숫자가 표시된다면 이는 컴퓨터 메모리에 저장된 것 일까요?

– 정답은 틀렸습니다. 스크린에서 보이는 숫자는 아스키코드로 디코딩한 표시입니다. 아스키코드의 30~39는 숫자 0~9까지를 표현합니다.

모니터 화면에 숫자를 표시하기 위해 CPU가 메모리의 어딘가에서 숫자 7을 가져왔다고 해봅시다. 숫자는 여전히 CPU의 레지스터에 전자적으로 들어있을 뿐입니다. 이를 화면에 표시하기 위해서는 기본출력 시스템을 사용해야 합니다. 기본 출력장치(Standard Output)은 보통 모니터입니다.

이런 부분은 운영체제가 담당하는 부분인데요. 간단하게 설명하면 정수 7에 해당하는 아스키 코드표를 찾습니다. 숫자 7의 아스키코드는 37입니다. 윈도우나 리눅스 운영체제에서는 폰트시스템을 사용합니다. 운영체제는 아스키코드 37에 해당하는 폰트를 모니터에 출력합니다. 즉 사람은 모니터에서 7을 보겠죠.

방향성에 차이가 있을 뿐 키보드입력(Standard Input)도 마찬가지 원리입니다.

이 폰트는 2차원 배열의 그래픽으로 정의되어 있습니다.

아래의 폰트는 A (아스키 코드 65)에 대응하는 폰트입니다. 쉽게말해 이미지 배열이죠. 비어있는게 0 검은게 1입니다. 0과 1만으로 간단한 폰트부터 복잡한 폰트까지 만들 수 있습니다.

변수(Variable)와 데이터형(Data type)

변수는 메모리에서 CPU가 접근하는 최소한의 구성단위입니다. 언어에 따라 기본 자료형 혹은 핵심 자료형(core data type) 이라고도 불립니다.

4기가 메모리에서도 변수 하나에 1바이트 단위를 할당하여 사용이 가능합니다. 변수는 데이터형에 따라 메모리를 구분하는데요. 일반 가정용 PC에서 일반적으로 정수형이라하면 32비트(4바이트) 부호있는 정수를 의미합니다. 이는 정수의 범위 -21억~+21억를 갖습니다.

1바이트도 사용할 수 있지만 수의 범위가 256개 밖에 안되기 때문에 편하지 않습니다.

int myNumber = 0;
// 32비트 정수형 변수 myNumber 를 0으로 초기화한다
// 정수 21억까지 표현할 수 있는 하나의 데이터 저장소를 확보하여 비워둔다는 뜻이다.

배열(array)

변수는 C++ 기초에서 처음에 배우는 부분이라 이해하기 어렵지 않습니다. 데이터형이 있다는 것 정도만 알고 있어도 됩니다.

배열(array)는 같은 데이터 타입의 변수들을 모아 놓은 것 입니다. 변수를 따로 관리하면 불편하죠. 예를 들어 한 학급에 30명의 학생이 있는데 변수로 관리하면 번거롭습니다.

30명이 문제가 아니라 3만명이라고 하면 변수 이름만 3만개를 지어야 합니다. 이미 이름(식별자)을 짓는데만 심각한 메모리 낭비가 발생합니다.

그러지말고 하나의 이름으로 관리하면 어떨까라는 발상에서 시작된게 배열입니다.

아래의 코드는 myClass 라는 이름의 정수형 배열을 0으로 초기화 시킵니다.

int myClass[30] = { 0, };

마찬가지로 30명을 300명 30000명으로 만들기 위해 필요한 것은 0을 몇개 추가하면 됩니다. 매우 획기적이죠.

배열 예제

다음은 배열의 예제입니다. 30명이 있는 학급의 시험점수를 0으로 최기화하고 점수를 입력한 후 출력합니다. 이런 방식으로 배열을 만들어 놓는다면 변수를 30개 관리하는 것 보다 훨씬 수월하게 데이터를 관리할 수 있습니다.

#include <iostream>

using std::cout;
using std::endl;

int main() {

	int myClassScore[30] = { 0, };

	myClassScore[0] = 75;
	myClassScore[1] = 80;
	myClassScore[2] = 65;

	int length = sizeof myClassScore / sizeof myClassScore[0];

	for (int i = 0; i < length; i++)
	{
		cout.width(2);
		cout << myClassScore[i] << ", ";
		if ((i+1) % 10 == 0) cout << endl;
	}
	return 0;
}

75, 80, 65,  0,  0,  0,  0,  0,  0,  0,
 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,

위의 코드에서는 배열의 크기를 구하기 위한 sizeof 연산자를 사용했습니다.

C++ 의 STL 라이브러리를 사용하면 좀 더 간단한 코드로 구현할 수도 있지만 자료구조의 원리에 대하여 밑바닥 부터 훑어야 하기 때문에 편리한 도구들은 학습기간 중에는 사용할 필요가 없습니다.

C++에서 배열의 사용법은 포인터의 사용법과 비슷합니다. 배열의 인덱스는 그 배열의 0부터의 거리(offset)이기 때문입니다.

요약

컴퓨터의 자료구조 기본에 대하여 알아봤습니다. 자료구조라는 큰 개념에서 시작해서 작은 것으로 나아가는 방식으로 살펴봤는데 중간에 아스키코드의 원리 같은 부분도 자료구조를 분석하기 위한 기본이 되는 부분입니다.

기왕 자료구조에 입문했다면 수박겉핥기 보다는 더욱 디테일한 부분까지 파고드는 것이 좋습니다. 너무 빨리 변하기 때문에 지식의 미래적인 가치를 알 수 없는 세상에서 컴퓨터의 지식은 정직한 편입니다. 컴퓨터를 모든 사람이 사용하고 전세계에 수많은 프로그래머가 있지만 그 가치를 완벽히 이해하고 실천하는 사람은 많지 않습니다.

한편으로는 그만큼 컴퓨터 과학이 어렵다는 반증이기도 합니다.

자료구조를 시작하면서 나는 과연 어디까지 파고들 수 있을 것인가? 라는 도전의식을 갖는 것은 장려할 만한 일입니다.

한가지 팁은 자료구조는 현실세계와 동떨어진 지루한 세계가 아니라는 것 입니다. 최근에 떠오르고 있는 비트코인도 SHA 256 이라는 블록체인 알고리즘으로 만들어졌습니다. 이 암호화 기술의 기초에 해당하는 것이 해시테이블(Hash Table) 입니다. 컴퓨터 대학에서는 기본으로 가르치는 알고리즘으로 완벽하게 이해하는 사람이 많지 않은 기술입니다.

가장 기본적인 것을 완벽하게 이해하려고 노력하는 것이 컴퓨터 공학입니다.

C언어의 창시자인 데니스 리치의 어록에 힌트가 있습니다.

유닉스는 단순한 운영체제입니다. 그러나 당신은 그 단순함을 이해하기 위해서 천재가 되야 합니다.
데니스 리치

컴퓨터 프로그래밍 언어의 기초를 습득하고 이제 어느정도 자신감이 붙기 시작할 때가 알고리즘 학습을 하기 좋은 때 입니다. 하나의 알고리즘 문제를 푸는데 짧게는 1분에서 길게는 며칠이 걸리기도 합니다.

이 과정은 프로그래밍 초중급에 해당합니다. 가장 지루한 때이기도 합니다. 동기부여를 하며 쉬지않고 달려나갈 때 입니다.

이전 학습

다음 학습

외부참고문서