자료구조

이 글은 Crash Course의 Computer Science를 보고 정리한 글입니다.

알고리즘이 실행되는 데 데이터가 어떻게 컴퓨터 메모리에 저장되는지에 대해서 얘기해 보자. 데이터는 일고 불러오기 쉽게 구조가 탄탄하고 잘 정리되어 있어야 한다. 이것을 위해서 컴퓨터 과학자들은 자료 구조라는 것을 사용한다.

 

배열(Arrays), 리스트(Lists), 벡터(Vectors)

이것들은 메모리에 연속적으로 저장되어 있는 값이다. 그래서 'j=5'와 같이 한 개의 변수에 한 개의 값을 저장하는 대신, 여러 개의 숫자를 지정한 다음 배열에 저장할 수 있다. 'j=[1,26,73,94,65,36,17]'

배열에 있는 특정한 값을 찾으려면 인덱스(index ; 목록)를 지정해 줘야 한다. 거의 모든 프로그래밍 언어에서 배열의 목록은 0부터 시작한다. 그리고 배열의 인덱스를 대괄호[]로 표현하여 읽는다. 예를 들어서, j배열 첫 번째와 세 번째 자리에 값을 더해 변수 a에 저장하고 싶다면 'a = j[0] + j[2]' 와 같이 코드를 쓰면 된다.

배열이 메모리에 저장되는 방법은 매우 간단하다. 간단하게, 컴파일러가 우리 배열을 메모리 주소 1000에 저장했다고 가정하자. 배열이 7개의 숫자를 가지고 있다면, 메모리 상에서는 나란히 1000, 1001, 1002, ..., 1006 주소에 나란히 저장된다. 우리가 j[0]을 찾는다면 컴퓨터는 메모리 주소 1000에서 0만큼 더하여 값을 찾는다. 마찬가지로 우리가 j[5]를 찾고 싶다면 프로그램은 메모리 주소 1000으로 가서 5만큼 더한 위치에서 값을 얻는다.

배열에서 5번째 숫자랑 인덱스가 5인 숫자를 헷갈리기 쉽다. 둘은 전혀 다른 값이다. 배열의 수는 0부터 시작하므로 인덱스가 5인 숫자는 6번째 숫자라는 것을 기억해야 한다.

 

배열은 매우 다양하게 사용되는 데이터 구조로 늘 사용되므로 유용하게 다루는 많은 함수가 있다. 예를 들어, 거의 모든 프로그래밍 언어는 배열을 입력만 하면 정렬이 되어서 나오는 정렬 기능이 내장되어 있다. 그래서 정렬 알고리즘을 맨 처음부터 구현할 필요가 없다.

 

매우 유사한 것으로 문자열(Strings)은 단지 문자나 숫자, 특수문자 등으로 이루어진 문자 배열이다. 보통 메모리에 문자열을 저장할 때는 j="John"처럼 큰따옴표 안에 넣는다. 문자열 또한 배열이 맞다. 메모리상에서 문자열은 (zero)로 끝난다. 문자 0이 아니라 이진법 값 0이다. 이걸 Null 문자라고 하는데, 이게 문자열의 끝을 나타낸다. 이게 중요한 이유는, 만약 이 문자열을 print(j)와 같은 함수로 출력한다고 하면, 시작 메모리 주소부터 순서대로 출력을 하겠지만 언제 출력을 멈춰야 할지 알아야 한다. 그렇지 않으면 메모리 안의 모든 문자를 출력할 것이다. (zero)는 문자열 함수가 언제 끝나는지 알려준다. 

 

컴퓨터는 문자를 다룰 일이 너무 많기 때문에 문자열만을 다루는 함수가 굉장히 많다. 예를 들어, 많은 프로그래밍 언어는 두 문자열을 입력받아 하나의 문자열로 이어주는 'strcat'이라고 하는 함수를 가지고 있다.

first = "I'm "
second = "John"
text = strcat(first, second)
print(text)
>>>I'm John

 

배열을 사용해서 1차원적 자료를 다룰 수 있지만, 스프레드시트의 표나 화면의 픽셀처럼 2차원적으로 확장된 자료도 다룰 수 있다. 이럴 때는 매트릭스(Matrix ; 행렬)라는 게 필요하다. 매트릭스는 배열의 배열이라고 생각하면 된다. 2x3 매트릭스는 그냥 크기가 3인 배열이 2개 있는 것을 말한다.

j = [[1, 2, 3], [4, 5, 6]]

[[1, 2, 3],
 [4, 5, 6]]

메모리상에서는 아래와 같이 배열이 순서대로 저장되어 있다.

특정 갑에 접근하려면 인덱스 두 개를 알려줘야 한다. 예시로 'j[2][1]'을 찾는다면 2번 배열에서 인덱스 1의 값을 구하는 것과 같다. 따라서 1007 위치의 값인 12를 얻을 수 있다.

 

우리는 이런 식으로 차원을 늘려가면서 무한한 차원의 배열을 만들 수 있다.

 

또, 연관성 있는 자료를 연결해서 구조체(Struct)로 묶을 수 있다.

STRUCT account
    VARIABLE accountNumber
    VARIABLE balance
END STRUCT

j.accountNumber = 127834221
j.balance = 189.14

이렇게 단일 숫자가 아닌 여러 데이터를 한 번에 저장 가능한 복합 데이터로 된 변수를 만들어 낼 수 있다.

이런 구조체 또한 배열로 만들어 자동으로 묶을 수도 있다.

또한, Struct 데이터 구조를 사용해서 보다 복잡한 데이터 구조를 만드는 데 사용할 수 있다.

 

노드(Node)라는 이름의 구조체를 살펴보자. 이는 포인터와 변수를 같이 저장한다. 포인터란, 메모리의 주소를 가리키는 특별한 변수를 말한다.

## Node Struct ##
STRUCT node
    VARIABLE i
    POINTER next
END STRUCT

이 구조체를 이용하면 노드를 여러 개 저장할 수 있는 유연한 구조체인 연결 리스트(Linked List)를 만들 수 있다.

노트 구조체가 메모리 주소 1000, 1002, 1008 이렇게 세 군데에 중간중간마다 다른 데이터가 저장되어 있고, 서로 떨어져서 저장되어있다고 가정해보자. 주소가 1000인 node구조체의 포인터 next에 1008이 저장되어 있으면, 이것은 다음 노드가 연결 리스트 안에서 메모리 위치 1008에 있다는 것을 의미한다. 이 연결된 배열을 따라가 보면 다음 위치에서 변수 i의 값을 구할 수 있고, 다음 노드의 주소를 알 수 있다. 문자열과 마찬가지로 끝을 표현할 때는 주소 값에 (zero) Null 값을 넣어주면 된다.

 

크기를 미리 지정해줘야 하는 배열과는 달리, 연결 리스트는 크기를 상황에 따라서 늘이거나 줄일 수 있다. 예를 들어, 메모리에 새 노드를 할당하고 다음 포인터를 변경하는 것만으로 연결 리스트에 삽입할 수 있다. 연결 리스트는 쉽게 순서를 바꾸거나, 간략화, 쪼개기, 뒤집기 등이 가능하다. 이 유연성 덕분에 정렬 알고리즘 등에도 유용하게 쓰이고, 더욱더 복잡한 자료 구조들이 연결 리스트 위에 구축되어있다. 가장 유명하고 보편적인 것은 규(Queue)와 스택(Stack)이다.

 

큐는 식당 줄서기처럼 도착한 순서대로 들어간다. 가장 먼저 온 사람이 가장 먼저 서비스를 받는다. 이런 현상을 FIFO(First-In First-Out; 먼저 들어온 것이 먼저 나간다.)이라고 한다. 연결 리스트의 첫 번째 노드를 가리키는 포인터 p가 있다고 가정하자. 첫 번째 데이터가 처리되면 다음 포인터를 읽고 포인터 p의 값을 큐의 다음 데이터로 업데이트할 수 있다. 첫 번째 데이터는 처리가 완료되었으므로 큐에서 제거된다. 일 처리를 다 했으니까 이제 볼일이 없다.

만약에 큐에 새로운 노드를 추가하려면 연결 리스트의 끝까지 가로질러 가서 마지막 노드의 포인터를 다음 노드의 포인터를 향해서 연결해 주면 된다.

 

여기서 포인터 p가 마지막 데이터를 가리키게 한다면 LIFO(Last-In First-Out; 나중에 들어온 것이 먼저 나간다) 형식인 스택처럼 사용할 수 있다. 큐에 더하고 빼는 대신, 스택에서 데이터는 Push로 추가되고 Pop으로 제거된다.

 

이제 노드 구조체에서 포인터를 한 개 대신 두 개를 갖게 한다면, 다양한 알고리즘에 쓰이는 '트리 구조'를 만들 수 있다.

## Trees ##
STRUCT tree
    VARIABLE i
    POINTER nextLeft
    POINTER nextRight
END STRUCT

다시 말하지만 프로그래머가 포인터의 값을 직접 볼 일은 거의 없기 때문에 다음과 같이 개념화할 수 있다.

여기서 가장 위에 있는 노드를 루트(root)라고 한다. 그리고 한 노드에서 뻗어져 나오는 노드들을 그 노드의 자식 노드(children node)라고 한다. 그리고 자식 노드 위에 있는 노드는 부모 노드(parent node)라고 한다. 마지막으로 자식 노드가 없는 노드, 맨 끝의 노드를 리프 노드(leaf node)라고 한다.

 

위의 예시에서 보면 한 노드가 두 개까지의 자식을 가진다. 이런 구조체를 이진트리(binary tree)라고 한다. 하지만 상황에 맞게 자료 구조를 수정함으로써 트리의 자식 노드 수를 3이나 4 또는 임의의 수로 늘릴 수 있다. 심지어 연결 리스트를 써서 그들이 가리키는 모든 노드를 저장하는 트리 노드도 만들 수 있다.

트리구조에서 중요한 것은 바로 뿌리(root)에서 잎(leaf)까지 하나의 길이 존재한다는 것이다.

 

또, 무한 루프와 같이 제멋대로 연결되는 자료들은, 대신 그래프 데이터(graph data) 구조를 사용한다.

이건 트리처럼 많은 포인터를 가지고 있는 노드로 저장할 수 있지만, 루트나 리프, 부모와 자식에 대한 개념은 없다. 무엇이든지 아무거나 포인터로 가리킬 수 있다.

 

이상이 모든 기본적인 자료 구조에 대한 개요이다.

이 기본적인 뼈대 위에, 프로그래머들은 힙(Heap)이나 Red-Black 트리와 같은 약간 다른 모든 종류의 똑똑한 변형을 만들었다.

 

각각 다른 자료구조는 특정 계산에 유용한 속성을 가지고 있다. 알맞은 데이터 구조의 선택은 컴퓨터가 효율적으로 데이터를 처리할 수 있게 해 준다. 그러므로 이런 이론은 배워두는 게 중요하다. 다행히 많은 프로그래밍 언어는 라이브러리에 이미 만들어진 자료구조들로 가득 차 있다. 이건 우리가 프로그램을 매 처음부터 만드느라 시간을 낭비하지 않아도 된다는 뜻이고 대신 자료구조의 힘을 사용해서 더 유용하고 흥미로운 일을 할 수 있게 해 준다.