컴퓨터에서 "자료(Data)" 란 프로그램으로 처리하고자 하는 데이터를 뜻합니다.
대부분의 프로그램은 자료를 처리하여 유용한 정보로 출력하는데, 이때 데이터가 어떤 구조로 표현되느냐에 따라 프로그램의 성능이 결정됩니다. 이것이 "자료구조"가 필요한 이유입니다.
01. 자료구조 개요
1) 자료구조 개념
"자료구조"란 데이터의 구조적 특징이 잘 살도록 체계적으로 데이터를 저장하고 사용하는 방법을 의미합니다. 프로그램이 쉽게 이용하도록 구성된 데이터 간의 논리적인 관계입니다. 프로그램이 다루는 데이터의 대부분은 어떠한 구조적인 관계를 맺고 있습니다. 즉, 데이터마다 특정한 방법으로 저장되거나 사용된다는 것입니다.
2) 자료구조 분류
자료구조는 "단순 구조", "선형 구조", "비선형 구조"로 분류됩니다.
(1) 단순 구조
단순 구조는 기본 자료형에 따라 다시 분류됩니다. "정수(integer)", "실수(float, double)", "문자(char)", "문자열(string)" 등의 자료형이 있으며, 데이터들 사이의 관계가 아닌 개별 데이터 1개의 형태를 의미합니다.
(2) 선형 구조
선형 구조는 어떤 순서에 따라 데이터들이 한 줄로 늘어선 자료구조입니다. 구조가 복잡하지 않기에 컴퓨터 프로그래밍 작업에도 많이 사용됩니다. 대표적인 선형 구조로는 "배열(Array)", "연결 리스트(Linked list)", "스택(Stack)", "큐(Queue)" 등이 있습니다.
(3) 비선형 구조
비선형 구조는 비순차적인 성질을 지닌 데이터들을 표현한 자료구조입니다. 대표적인 비선형 구조로는 "트리(Tree)" 와 "그래프(Graph)" 가 있습니다.
02. 배열
1) 배열 개념
배열은 자료형이 같은 데이터를 순서대로 나열한 뒤 메모리에 연속으로 저장해 만든 자료 그룹입니다. 첫 번째 데이터를 기준으로 상대적인 위치를 파악해 나머지 데이터들을 파악합니다.
2) 배열 구조
배열은 변수 한 개의 이름으로 메모리 방을 여러 개 사용하는 구조입니다. 각 방을 동일한 이름으로 쓰되 번호를 붙여 구분합니다. 밑의 사진의 5개의 메모리는 모두 "arr" 이라는 이름을 사용하는데 각 위치에 따라 차례대로 "arr[0]", "arr[1]", "arr[2]", "arr[3]", "arr[4]" 로 구분합니다.
이렇게 배열은 각 요소를 구분할 때 번호를 사용하는데 이것을 "인덱스(Index)" 라고 합니다. 프로그래밍 언어에서는 항상 인덱스는 0부터 시작합니다. 특정 배열 요소를 사용할 때, "배열 이름[배열 요소의 인덱스]" 로 지정하고 각각의 변수처럼 사용하면 됩니다.
예를 들어, 위의 사진에 있는 메모리 중 "e"를 사용하고 싶다면 "배열이름 arr"과 "인덱스 4"를 합쳐서 "arr[4]"를 사용하면 e를 사용할 수 있게 되는 것입니다. 모든 자료형은 배열로 구성할 수 있으며, 구성에 따라 1차원, 2차원, 3차원 등 다차원 배열도 만들 수 있습니다.
colors = ['Red', 'Orange', 'Yellow', 'Green', 'Skyblue', 'Blue', 'Violet']
# colors[0] = Red
# colors[1] = Orange
# colors[2] = Yellow
# colors[3] = Green
# colors[4] = Skyblue
# colors[5] = Blue
# colors[6] = Violet이와 같이 프로그래밍 언어(Python)로 배열을 선언할 수 있으며, 인덱스를 통해 배열 안의 요소들을 불러올 수 있습니다.
3) 배열에서 데이터 추가 및 삭제하기
위에서 보면 알 수 있는 것처럼, 배열은 항목을 접근하는 것은 쉽습니다. 배열명[인덱스] 이렇게 접근할 수 있었습니다. 그런데 데이터를 추가하는 것이나 삭제하는 것은 생각보다 복잡합니다. 정해진 배열의 중간에 다른 데이터를 추가하고 싶다면 추가하려는 자리 다음의 데이터를 모두 한 칸씩 뒤로 옮겨야 합니다.
(1) 데이터 추가
예를 들어, 위의 colors 배열에 데이터 'Black'을 'colors[2] 인 Yellow' 뒤에 추가하고 싶다면 Green, Skyblue, Blue, Vlolet을 한 칸씩 뒤로 옮긴 후 colors[3] 자리에 Black을 삽입해야 합니다.
# 배열에서 데이터 추가 과정을 의사코드로 나타냈습니다. (정식 파이썬 문법을 따르지 않았습니다.)
# 현재 배열 상태
colors = ['Red', 'Orange', 'Yellow', 'Green', 'Skyblue', 'Blue', 'Violet']
# Green, Skyblue, Blue, Violet 한 칸씩 뒤로 밀기
colors = ['Red', 'Orange', 'Yellow', ( ), 'Green', 'Skyblue', 'Blue', 'Violet']
# Black 추가하기
colors = ['Red', 'Orange', 'Yellow', 'Black', 'Green', 'Skyblue', 'Blue', 'Violet'](2) 데이터 삭제
바로 위에서 Black을 colors 배열에 추가하는 방벙을 알아보았습니다. 이번에는 colors 배열에 들어간 Black을 삭제하는 방법을 알아보겠습니다.
사실 데이터 추가 과정을 거꾸로 한 것이 바로 데이터 삭제 과정입니다. colors 배열에 들어있는 'Black'을 먼저 삭제합니다. 그 후, Green, Skyblue, Blue, Violet 요소들을 한 칸씩 이동시키면 삭제 과정은 모두 종료됩니다.
# 배열에서 데이터 삭제 과정을 의사코드로 나타냈습니다. (정식 파이썬 문법을 따르지 않았습니다.)
# 현재 배열 상태
colors = ['Red', 'Orange', 'Yellow', 'Black', 'Green', 'Skyblue', 'Blue', 'Violet']
# Black 삭제하기
colors = ['Red', 'Orange', 'Yellow', ( ), 'Green', 'Skyblue', 'Blue', 'Violet']
# Green, Skyblue, Blue, Violet 한 칸씩 앞으로 당겨오기
colors = ['Red', 'Orange', 'Yellow', 'Green', 'Skyblue', 'Blue', 'Violet']배열에서의 데이터 추가와 데이터 삭제 과정은 데이터를 옮기는 시간이 필요합니다. 따라서 데이터 추가와 삭제를 자주 해야 한다면 배열보다는 연결 리스트를 사용하는 것이 더욱 효율적입니다.
03. 연결 리스트
1) 연결 리스트 개념
배열은 논리적 순서와 물리적 순서가 같기에 데이터 위치를 찾기는 굉장히 쉽지만, 데이터를 추가하거나 삭제하는 과정에서 작업 시작이 많이 소요되고 메모리 사용 또한 비효율적입니다. 이러한 문제를 해결한 데이터 표현 방식이 바로 "연결 리스트"입니다.
2) 연결 리스트 구조
연결 리스트의 데이터는 다음에 이어질 데이터 주소를 포함해 <원소, 주소> 단위로 구성되어 있으며, 이를 합쳐서 "노드"라고 합니다. 원소 값을 저장하는 "데이터 필드"와 노드 주소를 저장하는 "링크 필드"로 나누어져 있습니다.
3) 연결 리스트 분류
연결 리스트는 "단순 연결 리스트", "원형 연결 리스트", "이중 연결 리스트" 로 분류됩니다.
(1) 단순 연결 리스트
단순 연결 리스트는 노드의 링크 필드가 하나이며, 링크 필드는 다음 노드와 연결되는 가장 기본적인 연결 리스트 구조입니다. 단순 연결 리스트는 연결 관계만 있기 때문에 특정한 노드를 불러내기 어려운 단점이 있습니다.
(2) 원형 연결 리스트
원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 리스트의 첫 번째 노드를 가리키게 해서 리스트 구조를 원형을 만든 구조입니다. 원형 연결 리스트는 단순 연결 리스트와 달리 마지막 노드의 링크 필드에는 'NULL' 값이 저장되지 않습니다. 원형 연결 리스트에서 특정한 값을 불러오기 위해서는 한 싸이클을 다 돌아야만 특정 노드를 불러낼 수 있다는 단점이 있습니다.
(3) 이중 연결 리스트
이중 연결 리스트는 단순 연결 리스트와 원형 연결 리스트의 단점들을 보완한 구조입니다. 양쪽으로 모두 순회할 수 있도록 노드를 연결하여 바로 뒤의 노드에 접근하는 것이 용이하다는 장점이 있습니다. 다만, 이중으로 연결하기 때문에 컴퓨터가 처리해야 할 양이 늘어나고 자료구조의 크기가 더 커진다는 단점이 있습니다.
4) 연결 리스트에서 데이터 추가 및 삭제하기
연결 리스트는 새로운 항목을 추가하거나 삭제할 때 링크 필드에 연결된 화살표만 수정하면 됩니다. 그렇기에 배열보다 데이터 추가와 삭제 과정이 훨씬 간편합니다.
(1) 데이터 추가
연결 리스트에 데이터를 추가하는 방법은 간단합니다.
먼저, 노드 A, 노드 B, 노드 C가 있다고 가정합시다. 이때 노드 B와 노드 C 사이에 노드 N을 추가하고자 합니다. 그렇다면 일단 노드 B의 링크 필드가 가리키는 노드 C를 노드 N으로 가리키도록 합니다. 그 후, 노드 N의 링크 필드는 노드 C를 가리키면 데이터 추가 과정은 완료됩니다.
아래의 그림은 데이터 추가 과정을 간단히 그림으로 나타낸 것입니다.
(2) 데이터 삭제
연결 리스트에 데이터를 삭제하는 과정은 더더욱 간단합니다.
노드 B와 노드 C 사이에 추가한 노드 N을 삭제한다고 가정합시다. 이때 노드 N을 가리키던 노드 B의 링크 필드가 노드 C를 가리키도록 하면 사실상 삭제 과정은 끝이 납니다. 이렇게 하면 노드 B와 노드 C가 바로 연결되므로 노드 N은 연결 리스트에서 제거됩니다. 이때 노드 N은 연결 리스트에서 제외된 것일 뿐이지 메인 메모리에서 삭제가 된 것은 아닙니다. 완전히 제거하고자 하면 메인 메모리에서도 지워주셔야 합니다.
04. 스택
1) 스택의 개념
스택은 데이터를 차곡차곡 쌓아 올린 형태로 구성된 자료구조입니다. 이 구조에서는 제일 위에 놓인 자료, 즉 가장 최근에 쌓아둔 자료부터 차례로 쓰이게 됩니다.
2) 스택의 구조
스택 자료구조는 톱으로 정해진 맨 위에서만 데이터 추가와 삭제 작업이 가능합니다. 구조의 중간에서는 데이터를 추가하거나 삭제하지 못합니다. 스택에서 "톱(TOP)"은 삽입과 삭제가 일어나는 위치로 스택의 가장 위에 있는 데이터입니다. "같은 크기"의 데이터를 "정해진 방향"으로만 쌓을 수 있고 "톱"을 통해서만 접근이 가능합니다. 톱을 통해 들어온 데이터는 일정한 방향(아래 -> 위)으로 차곡차곡 쌓이게 되는데 삭제할 때도 마찬가지입니다.
즉, 스택은 가장 마지막에 삽입된 데이터가 가장 먼제 삭제된다는 "LIFO(Last In First Out)" 구조로 운영됩니다.
3) 스택에서의 데이터 추가 및 삭제
스택에서 데이터를 추가하는 과정은 "푸시(Push)"라고 하고, 데이터를 삭제하는 과정을 "팝(Pop)"이라고 합니다. 위에서 말했듯이 푸시와 팝이 일어나는 장소는 스택의 톱이며 LIFO 구조로 인해 아래에서 위로 푸시가 일어나며 위에서 아래로 팝이 일어납니다.
파이썬 코드로 스택의 푸시와 팝 과정을 구현해보겠습니다.
데이터 변수를 추가하기 위해 'append( )' 함수를 사용하고 데이터 변수를 삭제하기 위해서 'pop( )' 함수를 사용합니다.
# 스택에서 데이터 추가
Stack = [1, 2, 3, 4, 5]
Stack.append(6)
print(Stack)
# 결과: 1, 2, 3, 4, 5, 6
Stack.append(20)
print(Stack)
# 결과: 1, 2, 3, 4, 5, 6, 20
# 스택에서 데이터 삭제
Stack = [1, 2, 3, 4, 5, 6, 20]
Stack.pop()
print(Stack)
# 결과: 1, 2, 3, 4, 5, 6
Stack.pop()
print(Stack)
# 결과: 1, 2, 3, 4, 505. 큐
1) 큐의 개념
스택과 반대 개념인 "큐"에 대해서 알아보도록 하겠습니다. 큐는 데이터가 한 방향에서만 삽입되고 반대 방향으로만 삭제되는 자료구조입니다.
2) 큐의 구조
큐는 데이터 삽입, 삭제가 일어나는 위치와 방법이 정해져 있습니다. 이 점은 스택과도 동일합니다. 그러나 큐는 리스트의 한 쪽 끝은 삽입 작업만 이루어지고, 반대 쪽 끝은 삭제 작업만 이루어진다는 점에서 차이가 있습니다. 즉, 먼저 삽입된 데이터가 먼저 삭제되는 "FIFO(First In First Out)" 구조로 운영됩니다.
3) 큐에서의 데이터 추가 및 삭제
큐에서 데이터를 추가하고 삭제할 때, 맨 처음 데이터 A를 삽입하면 A는 프런트와 리어의 역할을 동시에 수행합니다. 이후, 데이터 B와 데이터 C가 순차적으로 삽입되면 가장 마지막에 삽입된 데이터 C가 리어 역할을 수행합니다. 여기서 삭제 작업을 진행하면 데이터 A는 추출되고, 데이터 B가 프런트 역할을 수행하게 됩니다.
Queue = [1, 2, 3, 4, 5]
Queue.append(10)
Queue.append(20)
print(Queue)
# 결과 1, 2, 3, 4, 5, 10, 20
Queue.pop(0)
Queue.pop(0)
print(Queue)
# 결과 3, 4, 5, 10, 2006. 비선형 자료구조
앞서 배운 배열, 연결 리스트, 스택, 큐 등은 "선형 자료구조"입니다. 지금부터 배울 "비선형 자료구조" 에는 "트리", "그래프" 등이 있습니다.
1) 트리
트리는 나무를 뒤집어 놓은 모습의 자료구조입니다. 데이터들이 1 : 1 관계의 선형 구조가 아닌 1 : N 관계의 비선형 구조로 놓여 있습니다. 계층 관계로 만들어진 계층형 자료구조이기도 합니다.
이 트리 구조를 보겠습니다. 트리에 있는 원들은 "노드(Node)"라고 하고 노드와 노드를 연결한 선은 "간선(Edge)" 이라고 합니다. 트리는 노드와 간선의 집합체인 것입니다. 또한 트리는 계층 관계를 가지는데, 가장 위에 있는 노드부터 레벨 정보가 시작됩니다. 트리의 가장 위에 위치한 노드를 "루트 노드(Root Node)"라고 부르며 가장 아래에 위치한 노드들은 "단말 노드(Leaf Node == Terminal Node)" 라고 부릅니다. 예를 들어, 노드 A가 노드 B를 가리킬 때 A를 "부모 노드(Parent Node)", B를 "자식 노드(Child Node)" 라고 부릅니다. 또한 "형제 노드(sibling node)"는 같은 부모 노드를 가지는 모든 노드를 가리킵니다
2) 그래프
그래프는 연결된 데이터들의 N : N 관계를 표현하는 자료구조입니다.
그래프는 연결한 객체를 나타내는 "정점(Vertex)"과 객체를 연결하는 "간선(Edge)"들의 집합입니다. 그래프와 트리의 차이점은 그래프 사이에는 "사이클(Cycle)"이 존재한다는 것입니다. 그래프(G)는 G = (V, E) 로 정의되는데, V는 그래프에 있는 정점의 집합을 나타내고, E는 정점을 연결하는 간선의 집합을 뜻합니다.
그래프는 방향성에 따라 "무방향 그래프"와 "방향 그래프"로 나뉘는데, 무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선의 방향이 정해져 있지 않은 그래프를 말하고, 방향 그래프(Directed Graph)는 간선에 방향이 정해져 있는 그래프를 말합니다.
