자료구조 개요
자료구조 개념
- 자료구조란 데이터의 구조적 특징이 잘 살도록 체계적으로 데이터를 저장하고 사용하는 방법
- 데이터마다 특정한 방법 (효율적인 방법)으로 저장되거나 사용
자료구조 분류
- 자료구조는 단순 구조, 선형 구조, 비선형 구조로 분류
단순 구조
- 정수(integer), 실수(float, double), 문자(char), 문자열(string) 등의 자료형
- 데이터들 사이의 관계가 아닌 개별 데이터 1개의 형태를 의미
선형 구조
- 어떤 순서에 따라 데이터들이 한 줄로 늘어선 형태의 자료구조
- 대표적인 선형 구조 배열(Array), 연결 리스트(Linked list), 스택(Stack), 큐(Queue) 등
비선형 구조
- 비순차적인 성질을 지닌 데이터들을 표현한 자료구조
- 대표적인 비선형 구조 트리(Tree), 그래프(Graph)
배열
배열 개념
- 배열은 자료형이 같은 데이터를 순서대로 나열한 뒤 메모리에 연속으로 저장해 만든 자료 그룹
- 첫 번째 데이터를 기준으로 상대적인 위치를 파악해 나머지 데이터들을 파악
배열 구조
- 배열은 변수 한 개의 이름으로 메모리 방을 여러 개 사용하는 구조
- 각 방을 동일한 이름으로 쓰되 번호를 붙여 구분
밑의 그림에서 5개의 메모리는 모두 arr 이라는 이름을 사용하는데 각 위치에 따라 차례대로 arr[0], arr[1], arr[2], arr[3], arr[4] 로 구분한다.
이처럼 배열은 각 요소를 구분할 때 번호를 사용하게 되는데 이것을 인덱스(Index) 라고 한다.
프로그래밍 언어에서는 항상 인덱스는 0 부터 시작하며 특정 배열 요소를 사용할 때, 배열 이름[인덱스]로 지정하고 각각의 변수처럼 사용한다.
예를 들어, 위의 사진에 있는 메모리 중 e를 사용하고 싶다면 배열이름 arr과 인덱스 4를 합쳐서 arr[4]를 사용하면 된다.
모든 자료형은 배열로 구성할 수 있으며, 구성에 따라 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)로 배열을 선언할 수 있으며, 인덱스를 통해 배열 안의 요소들을 불러올 수 있다.
배열에서 데이터 추가 및 삭제하기
- 정해진 배열의 중간에 다른 데이터를 추가하고 싶다면 추가하려는 자리 다음의 데이터를 모두 한 칸씩 뒤로 이동
- 데이터를 삭제하고 싶다면 데이터를 삭제하고 난 빈 자리 뒤의 데이터를 모두 한 칸씩 앞으로 이동 (데이터 추가 과정을 반대로 진행)
데이터 추가
예를 들어, 위의 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']데이터 삭제
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']- 배열에서의 데이터 추가와 데이터 삭제 과정은 데이터를 옮기는 시간이 필요
- 데이터 추가와 삭제를 자주 해야 한다면 배열보다는 연결 리스트를 사용하는 것이 더욱 효율적
연결 리스트
연결 리스트 개념
- 배열은 데이터의 위치를 찾기는 굉장히 쉬우나, 데이터를 추가/삭제 하는 과정에서 시간이 많이 소요되며 메모리 사용이 비효율적
- 이러한 문제를 해결한 데이터 표현 방식 연결 리스트
연결 리스트 구조
- 연결 리스트의 데이터는 다음에 이어질 데이터 주소를 포함해 (원소, 주소) 단위로 구성 = 노드
- 원소 값을 저장하는 데이터 필드와 노드 주소를 저장하는 링크 필드로 나누어져 있음
연결 리스트 분류
- 연결 리스트는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트로 분류
단순 연결 리스트
- 노드의 링크 필드가 하나이며, 링크 필드는 다음 노드와 연결되는 가장 기본적인 연결 리스트 구조
- 연결 관계만 있기 때문에 특정한 노드를 불러내기 어려운 단점이 존재
원형 연결 리스트
- 단순 연결 리스트의 마지막 노드가 리스트의 첫 번째 노드를 가리키게 해서 리스트 구조를 원형으로 만든 구조
- 단순 연결 리스트와 달리 마지막 노드의 링크 필드에는 NULL 값이 저장되지 않으므로 원형 연결 리스트에서 특정한 값을 불러오기 위해서는 한 싸이클을 다 돌아야만 특정 노드를 불러낼 수 있다는 단점이 존재
이중 연결 리스트
- 단순 연결 리스트와 원형 연결 리스트의 단점들을 보완한 구조
- 양쪽으로 모두 순회할 수 있도록 노드를 연결하여 바로 뒤의 노드에 접근하는 것이 용이하다는 장점이 존재
- 이중으로 연결하기 때문에 컴퓨터가 처리해야 할 양이 늘어나고 자료구조의 크기가 더 커진다는 단점이 존재
연결 리스트에서 데이터 추가 및 삭제하기
- 연결 리스트는 새로운 항목을 추가하거나 삭제할 때 링크 필드에 연결된 화살표만 수정
- 배열보다 데이터 추가와 삭제 과정이 훨씬 간편하고 효율적
데이터 추가
먼저 노드 A, 노드 B, 노드 C가 있다고 가정하자. 이 때 노드 B와 노드 C 사이에 노드 N을 추가하려고 한다. 그렇다면 일단 노드 B의 링크 필드(화살표)가 가리키는 노드 C를 끊고, 노드 B가 노드 N을 가리키도록 한다. 그 후, 노드 N의 링크 필드를 노드 C를 가리키면 데이터 추가 과정은 완료된다.
데이터 삭제
노드 B, 노드 C 사이에 추가한 노드 N을 삭제한다고 가정하자. 이 때 노드 N을 가리키던 노드 B의 링크 필드가 노드 C를 가리키도록 하면 사실상 삭제 과정은 끝이 난다. 이렇게 하면 노드 B와 노드 C가 바로 연결되므로 노드 N은 연결 리스트에서 제거 된다. 하지만 노드 N은 연결 리스트에서 제외된 것일 뿐, 메인 메모리에서 삭제가 된 것은 아니기에 완전히 제거하고자 하면 메인 메모리에서도 지워야 한다.
스택
스택의 개념
- 스택은 데이터를 차곡차곡 쌓아 올린 형태로 구성된 자료구조
- 스택 구조에서는 제일 위에 놓인 자료, 즉 가장 최근에 쌓아둔 자료부터 차례대로 사용
스택의 구조
- 스택 자료구조는 톱(TOP) 으로 정해진 맨 위에서만 데이터 추가와 삭제 작업이 가능하므로 중간에서는 데이터를 추가하거나 삭제 불가능
- 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있고 톱을 통해서만 접근이 가능
- 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 LIFO(Last in First Out) 구조
스택에서의 데이터 추가 및 삭제
- 데이터를 추가하는 과정 푸시(Push)
- 데이터를 삭제하는 과정 팝(Pop)
데이터 변수를 추가하기 위해 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, 5큐
큐의 개념
- 스택과 반대 개념으로 작동
- 큐는 데이터가 한 방향에서만 삽입되고 반대 방향으로만 삭제되는 자료구조
큐의 구조
- 큐는 리스트의 한 쪽 끝은 삽입 작업만 이루어지고, 반대 쪽 끝은 삭제 작업만 가능
- 먼저 삽입된 데이터가 먼저 삭제되는 FIFO(First In First Out) 구조
큐에서의 데이터 추가 및 삭제
큐에서 데이터를 추가하고 삭제할 때, 맨 처음 데이터 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, 20비선형 자료구조
- 앞서 배운 배열, 연결 리스트, 스택, 큐 등은 선형 자료구조
- 비선형 자료구조에는 트리, 그래프 등이 존재
트리
- 나무를 뒤집어 놓은 모습의 자료구조
- 데이터들이 1 : 1 관계의 선형 구조가 아닌 1 : N 관계의 비선형 구조 (또는, 계층 관계로 만들어진 계층형 자료구조)
해당 트리 구조를 보자. 트리에 있는 원들은 노드(Node)라고 하고 노드와 노드를 연결하는 선은 간선(Edge)이라고 한다.
트리는 노드와 간선의 집합체이며, 트리는 계층 관계를 가지는데 가장 위에 있는 노드부터 레벨 정보가 시작된다.
트리의 가장 위에 위치한 노드를 루트 노드(Root Node)라고 부르며 가장 아래에 위치한 노드들은 단말 노드(Leaf Node == Terminal Node)라고 부른다. 예를 들어, 노드 A가 노드 B를 가리킬 때 A를 부모 노드(Parent Node), B를 자식 노드(Child Node)라고 부른다. 또 한, 형제 노드(Sibling Node)는 같은 부모 노드를 가지는 모든 노드를 가리킨다.
그래프
- 연결된 데이터들의 N : N 관계를 표현하는 자료구조
그래프는 연결한 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)들의 집합이다. 그래프와 트리의 차이점은 그래프 사이에는 사이클(Cycle)이 존재한다는 점이다. 그래프(G)는 G = (V, E)로 정의 되는데, V는 그래프에 있는 정점의 집합을 나타내고, E는 정점을 연결하는 간선의 집합을 뜻한다.
그래프는 방향성에 따라 무방향 그래프와 방향 그래프로 나누어지는데, 무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선의 방향이 정해져 있지 않은 그래프를 말하고, 방향 그래프(Directed Graph)는 간선에 방향이 정해져 있는 그래프를 말한다.
