[정보 처리] 7. 자료구조 이론

- 이번 포스팅은 알고리즘 개념과 자료구조 이론에 대해 정리합니다.

자료구조의 실제 구현은 포함되어 있지 않습니다.

 

[자료구조 개론]

(자료구조 개념)

- 자료구조란, 데이터를 프로그램에서 효율적으로 활용할 수 있도록 논리적으로 설계된 데이터 구조 및 관계입니다.

자료구조는 여러 종류가 있으며,

개발자라면 데이터의 유형과 상황에 따라 적절한 자료구조를 선택하여 활용할 수 있는 능력이 필요합니다.

 

- 자료 구조의 특징

1. 같은 데이터를 활용하더라도 자료구조에 따라 성능에 큰 영향을 끼칠 수 있습니다.

2. 효과적인 자료 구조란, 데이터 용량, 실행 시간 등을 최소한으로 사용하는 것입니다.

3. 데이터 추가, 삭제, 탐색을 보다 효율적으로 수행할 수 있도록 하는 것이 목표입니다.

 

- 자료 구조의 유형

1. 단순 구조

프로그래밍 언어에서 공통적이고 기본적으로 제공되는 기본 데이터 타입을 의미합니다.

정수, 실수, 문자 등의 데이터를 그대로 사용하는 것을 의미하며,

이를 확장해 사용하는 것이 자료 구조입니다.

 

2. 선형 구조

데이터들의 관계가 1대 1로 되어있는 구조로,

쉽게 설명하자면 기준 데이터의 앞뒤로 데이터가 연결된 구조입니다.

선형 구조는 또한 앞뒤의 연결이 실제 물리적 메모리 상 순차적으로 나열되어 있을 때의 순차(Sequential) 구조와,

앞뒤 연결이 주소를 기록하는 방식(앞 데이터는 이곳에 있고, 뒤 데이터는 저곳에 있음...)으로 처리된 연결(Linked) 구조로 나뉩니다.

 

3. 비선형 구조

데이터들의 관계가 1대 1이 아닌 1:N, N:M 등으로 구성되어 있는 구조입니다.

예시로는 한 데이터에서 가지를 뻗어가고, 가지로 뻗은 데이터에서도 가지를 뻗는 트리 구조가 있습니다.

 

4. 파일 구조

보조기억 장치에 실제로 데이터가 기록될 때 활용되는 자료입니다.

파일 구조의 종류는 순차 파일, 직접 파일, 색인 순차 파일 등이 있습니다.

 

(알고리즘 개념)

- 알고리즘이란,

문제를 해결하기 위해 수행되어야 할 기능들의 해법을 의미합니다.

 

- 프로그램은 데이터 구조와, 그 구조를 사용하는 알고리즘으로 이루어집니다.

올바른 데이터 구조를 선별하는 것만큼 올바른 알고리즘을 선정하여 사용하는 것이 중요합니다.

 

- 알고리즘 성능 판단 기준

알고리즘은 좋고 나쁨이 있습니다.

그 자체로 개선할 여지가 있는 미완성 정도라거나, 상황에 따른 적합성으로 나뉩니다.

아래는 알고리즘이 좋고 나쁜지를 외부적 척도로 판단할 때의 기준입니다.

 

1. 정확성 : 올바른 입력에 올바른 출력값이 반환되는지 여부

2. 명확성 : 알고리즘 이해와 변경이 용이한지를 판단

3. 수행량 : 단위 시간 대비 주요 연산 수행 횟수(수행 시간의 경우 연산 디바이스 성능에 달렸기에 연산 횟수를 기준으로 함)

4. 메모리 사용량 : 문제 해결에 사용된 메모리 사용량

 

- 알고리즘의 표현 방식은 엄격히 정해진 방법은 없습니다.

관계자간 이해하기 쉬운 형태로 작성하기만 하면 되는데,

추후 기록 및 추가 인원에의 정보 전달을 위하여 누구나 명확히 이해할 수 있는 일관성 있는 표현 방식을 결정해 사용해야 합니다.

 

일반적인 큰 분류의 표현 방식으로는,

1. 순서도(Flow Chart) : 약속된 도형과 기호로 기능과 흐름을 표현

2. 의사코드(Pseudo Code) : 실제 프로그래밍 언어로 만들어진 코드가 아닌 보다 추상적이고 자연어에 가까우면서 프로그래밍 언어의 형식을 빌린 가상 코드

 

(알고리즘 설계 기법)

1. 동적 계획법(Dynamic Programming)

어떠한 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하는 방법으로,

큰 문제를 작은 하위 문제로 나누고, 중복되는 하위 문제의 결과를 저장(메모리제이션) 하여 다시 계산하지 않도록 하는 방식입니다.

계산량을 줄여 시간 복잡도를 개선하는 장점이 있습니다.

ex : 피보나치 수열, 배낭 문제(Knapsack Problem), 최장 공통 부분 수열(LCS)

 

2. 탐용적 알고리즘(Greedy Algorithm)

매 단계마다 가장 최적의 해(로컬 최적)를 선택하여 전체 결과를 도출하는 방식입니다.

반드시 종합적인 최적 결과를 보장하지는 않습니다.

간단하고 빠르며 특정 조건에서는 최적 해를 보장합니다.

ex : 거스름돈 문제(동전 최소 개수), 크루스칼/프림 알고리즘(최소 신장 트리), 허프만 인코딩

 

3. 재귀적 알고리즘(Recursive Algorithm)

문제 풀이를 위해 함수를 사용하면 문제 해결 직전까지 함수 본인의 함수를 재귀적으로 불러오는 방법입니다.

본인이 본인을 호출하므로 무한 루프에 빠지지 않도록 적절한 탈출 조건을 마련하는 것이 필요합니다.

함수 하나로 그 이상의 사이즈의 문제를 해결하기에 코드가 간결해지지만,

호출된 함수는 탈출문을 만날 때 까지 메모리에 쌓이기에 오버플로우를 일으킬 가능성이 있습니다.(함수가 차례로 호출되었다가 탈출문을 만나면 역순으로 해소됨)

ex : 하노이의 탑, 이진 트리 순회, DFS(깊이 우선 탐색)

 

4. 근사 알고리즘(Approximation Algorithm)

최적화된 해답을 정확하게 구하는 것이 난해하고, 근사한 값으로도 충분한 경우,

비교적 빠른 시간에 계산이 가능하도록 근사 해답을 구하는 방법입니다.

빠르게 실행되어 실용적 상황에 적용하기 유용하지만, 최적해를 보장하지 않으므로 정확성을 요구하는 분야에서 사용할 수 없습니다.

ex : 외판원 문제(TSP), 집합 커버 문제

 

5. 분할 정복법(Divide and Conquer)

문제를 작은 하위 문제로 나누고, 각 하위 문제를 독립적으로 해결한 후 결과를 결합하여 전체 문제를 해결하는 방식입니다.

정렬, 탐색 알고리즘 쪽에 자주 사용됩니다.

ex : 병합 정렬, 퀵 정렬, 이진 탐색

 

6. 퇴각 검색법(Backtracking)

분기 구조의 탐색에서 가능한 분기를 시도해나가며,

가능한 모든 경우를 시도하되, 조건에 맞지 않는 경우는 중간에 포기하고 되돌아가(퇴각하여) 다른 분기를 시도하는 방식입니다.

완전 탐색이 필요한 경우 유용하며, 경우의 수가 많으면 성능이 떨어질 수 있습니다.(이를 해결하기 위해 Pruning 기법 사용)

ex : N-Queen 문제, 미로 찾기, 순열/조합 생성, 깊이 우선 탐색(DFS)

 

(수식 표기법)

- 수식 표기법이란, 수학 식이나 계산식을 어떤 순서와 방식으로 표기하는가에 대한 방법입니다.

연산자에 따라 전위식, 중위식, 후위식으로 나뉩니다.

- 중위식(In-fix)
연산자가 피연산자들의 사이에 위치합니다.

1+1 = 2

와 같이 일반적으로 사용되는 표현 방식입니다.

 

중위식을 사용한다면,

(1+2)*(3+4)

위와 같이 계산 순서를 나타내기 위해 괄호를 사용해야 합니다.

 

- 전위식(Pre-fix)

연산자가 피연산자들의 앞에 위치합니다.

중위식에서 계산 순서를 나타내기 위해 괄호를 사용하며, 계산 순서를 알기 위해선 괄호를 먼저 해석해야 합니다.

이 부분을 개선하기 위해 폴란드의 논리학자가 고안한 표기법으로, Polish 표기법이라고도 합니다.

 

상세한 설명을 위하여 일반적인 표기법인 중위식을 전위식으로 변환하며 설명하겠습니다.

 

(A-B)*C+D

이것을 변환할 때,

괄호 속의 A-B 를 먼저 변환합니다.

 

두 피연산자의 중간에 있는 연산자를 앞으로 옮겨서,

-AB

 

A-B 의 계산 결과 다음으로 계산되는 C 와의 계산식을 적용할 때엔,

피연산자를 먼저 정렬한 피연산자 뒤에 두고, 연산자는 앞서 정렬한 연산자의 앞에 두어,

*-ABC

 

다음으로 계산되는 D 역시 동일한 방식으로,

피 연산자는 피연산자 뒤에, 연산자는 연산자의 앞에 두어,

+*-ABCD

 

위와 같이 연산자가 앞에 표시되어, 이를 계산할 때에는, 피연산자는 앞에서 뒤로, 연산자는 뒤에서 앞으로 상호 조합하며 계산합니다.

 

- 후위식(Post-fix)

연산자가 피연산자들의 뒤에 위치합니다.

전위식에서 연산자의 위치만 뒤로 바뀐 것으로, 역 Polish 표기법이라고도 합니다.

 

상세한 설명을 위하여 일반적인 표기법인 중위식을 후위식으로 변환하며 설명하겠습니다.

 

(A-B)*C+D

이것을 변환할 때,
괄호 속의 A-B 를 먼저 변환합니다.

 

두 피연산자의 중간에 있는 연산자를 뒤로 옮겨서,
AB-

 

A-B 의 계산 결과 다음으로 계산되는 C 와의 계산식을 적용할 때엔,
피연산자, 연산자 순서로 가장 뒤로 붙이면 됩니다.
AB-C*

다음으로 계산되는 D 역시 동일한 방식으로,
피연산자, 연산자 순서로 가장 뒤로 붙이면,
AB-C*D+

위와 같이 표시됩니다.

전위식과는 달리 피연산자와 연산자의 위치가 구분되지 않는데,

이를 이용하여 연산시에는 앞에서부터 차례로 만나는 피연산자와 연산자를 조합하면 됩니다.

수식 파악 방식이 동일 순서를 보장하므로 전위식보다 쉽습니다.

 

[선형구조 자료구조]

- 선형 자료구조의 종류는 아래와 같습니다.

 

(스택(Stack))

스택 구조

 

- 스택이란, 바닥에 쌓아둔 책을 생각하면 됩니다.

책(데이터)을 쌓을 때는 차례대로 위쪽을 향해 쌓이고, 책이 빠져나갈 때에도 위에서부터 차례로 빠져나옵니다.

 

- 스택의 특징

1. 데이터 입출력이 한쪽에서만 일어남

2. 가장 나중에 삽입된 데이터가 가장 먼저 추출됨(후입선출, LIFO : Last In First Out)

3. Push(넣기), Pop(꺼내기) 의 인터페이스와, Top(Stack 이 얼마나 쌓였는지) 변수로 이루어집니다.

 

(큐(QUEUE))

큐 구조

 

- 큐란,

자판기를 생각하면 됩니다.

자판기 안의 음료수(데이터)는 위에서 아래로 쌓이는데, 음료수가 꺼내지는 순서는 아래에서부터 굴러나옵니다.

 

- 큐의 특징

1. 데이터의 입출력이 서로 다른 방향에서 일어남

2. 가장 먼저 입력된 데이터가 가장 먼저 출력됨(선입선출, FIFO : First In First Out)

 

(데크(DEQUE))

- 큐와 스택을 합친 개념이라 생각하면 됩니다.

양방향 큐라고도 볼 수 있으며,

데이터의 입출력이 양쪽 끝에서 모두 일어날 수 있는 구조입니다.

 

- 입출력의 제한 유형에 따라 방식이 나뉩니다.

1. 스크롤(Scroll) 방식 : 데크에서 입력은 한곳에서만 가능하도록 제한한 것입니다.

2. 쉘프(Shelf) 방식 : 데크에서 출력은 한곳에서만 가능하도록 제한한 것입니다.

 

(선형 리스트(Linear List))

선형 리스트

 

- 같은 유형의 데이터가 연속된 공간에 저장되는 자료구조입니다.

가장 단순하며, 접근 속도가 가장 빠르다는 장점이 있지만,

데이터들은 연속적으로 저장되어 있어야 하기에 중간 데이터를 삽입, 삭제시 나머지 데이터들을 전부 인접한 위치로 이동해야 하는 단점이 있습니다.

 

- 배열 특징

1. 같은 유형의 데이터를 하나로 묶은 개념

2. 데이터별 순서(Index) 가 부여되며, 이를 통해 데이터에 접근 가능

3. 사전에 미리 지정된 메모리 크기를 사용하며, 그 이상을 넘어서 데이터를 입력할 수 없음

4. 물리적으로 메모리에 저장된 데이터 순서와 논리적 순서가 동일하므로, 앞 데이터와 뒷 데이터를 조회하기 좋습니다.

5. 데이터를 배열 중간에 삽입, 삭제시 해당 위치의 오른쪽 데이터들은 모두 위치를 이동해야 합니다.

 

(연결(Linked) 리스트)

- 선형 리스트에서 데이터 삽입 및 삭제가 어려운 단점을 보완한 자료구조입니다.

데이터에는 데이터의 값 외에도 연결된 다른 데이터의 위치 정보가 포함되어 있으며,

이로써 물리적으로 연결되어있지 않더라도 각 데이터간 위치 정보를 기반으로 순서와 연결성을 가집니다.

 

- 연결 리스트에서 데이터는 간접적으로 연결되어 있습니다.

물리적으로 떨어진 각 데이터는 위치 데이터로 하나로 묶이며,

이렇게 각 위치에 존재하는 데이터 단위를 Node 라고 부릅니다.

 

- 연결 리스트의 장점은, 선형 리스트에 비해 데이터 조작 성능이 좋다는 것이고,

단점은, 노드마다 위치 데이터를 추가로 저장해야 하므로 추가 메모리 공간이 필요하며, 주소를 타고 데이터 위치를 찾아야 하므로 접근 속도가 선형 리스트보다 느리다는 것입니다.

 

- 연결 리스트는 연결 방식에 따라 여러 종류가 있습니다.

1. 단일 연결 리스트

단일 연결 리스트

노드별 다음 노드의 위치만을 저장합니다.

한 노드에선 다음 노드로만 이동할 수 있습니다.

리스트의 첫 노드 위치만 저장해 두면 노드를 타고 가며 원하는 인덱스 데이터를 검색할 수 있습니다.

노드의 끝으로 이동한 상태에서 다음 노드를 찾으면 데이터가 없습니다.

 

2. 이중 연결 리스트

이중 연결 리스트

노드별 선행 노드, 후행 노드를 저장하는 방식입니다.

노드의 시작에서 앞 노드를 찾거나, 노드의 끝에서 뒷 노드를 찾으면 데이터가 없습니다.

양방향 탐색이 가능하고, 포인터가 훼손되어도 복구의 가능성이 있습니다.

 

3. 원형 연결 리스트

원형 연결 리스트

단일 연결 노드와 같이 다음 노드의 위치만 가집니다.

차이점으로는, 마지막 노드가 참조하는 위치가 다시 첫 노드를 가리킨다는 것으로,

즉, 마지막 노드에서 다음 노드로 이동하면 첫 노드로 이동합니다.

 

4. 이중 원형 연결 리스트

이중 연결 리스트 구조에서 원형 연결 리스트 구조를 적용한 것과 같습니다.

첫 노드에서 앞으로 이동하면 마지막 노드로 이동하고, 마지막 노드에서 뒤로 이동하면 첫 노드로 이동합니다.

 

[비선형구조 자료 구조]

- 비선형 자료구조의 종류는 아래와 같습니다.

 

(트리(Tree))

- 데이터를 1:N 계층 구조로 표현하는 자료구조입니다.

 

- 용어 정리

1. 간선(Branch, Edge) : 나무에서 가지가 뻗어나가듯, 노드와 노드를 연결하는 가지를 의미합니다.

    간선의 총 개수는 언제나 노드의 총 개수에서 1 을 뺀 값

 

2. 뿌리(Root) 노드 : 부모가 없는 노드, 시작 위치의 노드

3. 단말(Leaf) 노드 : 자식이 없는 최하단 레벨의 노드

4. 내부(Internal) 노드 : 단말 노드가 아닌 노드(뿌리 노드도 포함)

5. 형제(Sibling) 노드 : 같은 부모를 갖는 노드

 

6. 노드의 크기(Size) : 특정 노드에서 자신을 포함한 모든 자식 노드의 개수

7. 노드의 깊이(Depth) : 특정 노드에서 자신의 부모 노드의 개수(뿌리 노드까지 몇번을 타고 가야 하는지)

8. 노드의 높이(Height) : 특정 노드에서  자신과 연결된 가장 깊은 단말까지의 간선 개수

9. 트리의 높이 : 루트 노드로부터 가장 깊은 단말까지의 간선 개수

10. 노드의 레벨(Level) : 같은 깊이를 가지는 노드의 집합

    (뿌리 노드를 1레벨로 두고, 뿌리 노드를 부모로 두는 노드를 2레벨... 이렇게 이어집니다.)

11. 노드의 차수(Degree) : 특정 노드에서 자신을 부모로 두는 자식 노드들의 개수(연결된 간선의 개수)

12. 트리의 차수 : 가장 큰 차수를 지닌 노드의 차수

 

- 이진(Binary) 트리

이진 트리

 

자식 노드가 최대 2개인 노드들로만 구성된 트리입니다.

이진 트리의 세부 종류는 아래와 같습니다.

 

포화(Perfect) 이진트리 :

뿌리 노드부터 모든 단말 노드까지 모든 노드의 자식 노드가 2개로 꽉 채워진 상태

       A
      / \
     B   C
    / \ / \
   D  E F  G

 

완전(Complete) 이진트리 :

마지막 레벨을 제외하고는 모든 레벨이 다 채워져 있음
마지막 레벨은 왼쪽부터 순서대로 채워져야 함

       A
      / \
     B   C
    / \  /
   D  E F

 

전(Full) 이진트리 :

모든 노드가 자식이 0개 또는 2개인 이진 트리
자식이 1개만 있는 노드가 없음

     A
    / \
   B   C

 

- 트리의 순회(Tree Traversal)

트리의 순회는 트리의 모든 노드를 어떤 순서로 방문할지 정하는 방법입니다.

 

순회의 방법은 3가지로,

          A
         / \
        B    C
       / \  / 
      D   E F
     / \  
    G   H

 

위 트리 구조 예시를 사용하여 설명하겠습니다.

 

1. 중위 순회(In-Order)

가장 좌측의 단말노드로 시작하여 해당 노드의 부모 노드, 형제 노드 순으로 순회하는 방식입니다.

좌측 자식 노드 -> 부모 노드 -> 우측 자식 노드 순으로 순회합니다. (부모를 중간에 순회하기에 중위 순회)

 

G->D->H->B->E->A->F->C

 

2. 전위 순회(Pre-Order)

뿌리 노드에서 시작하여 자식 노드를 차례로 순회하는 방식입니다.

부모 노드 -> 좌측 자식 노드 ->우측 자식 노드 의 순서로 순회합니다.(부모를 앞에 순회하기에 전위 순회)

 

A->B->D->G->H->E->C->F

 

3. 후위 순회(Post-Order)

가장 좌측 단말노드로 시작하여 형제 노드, 부모 노드 순으로 순회하는 방식입니다.

좌측 자식 노드 -> 우측 자식 노드 -> 부모 노드 순으로 순회합니다.(부모를 뒤에 순회하기에 후위 순회)

 

G->H->D->E->B->F->C->A

 

(그래프(Graph))

- 노드를 N:M 구조로 연결하여 데이터간 관계를 표현하는 자료구조입니다.

계층이 뚜렷한 트리와 달리 노드간 자유로운 경로 설정이 가능한 네트워크 모델로,

계층 관계가 없기에 루트, 부모-자식 과 같은 개념이 없습니다.

 

- 그래프 용어

1. 정점(Vertex) : 트리의 Node 와 같은 개념

2. 간선(Edge, Branch) : 정점을 연결하는 선

3. 인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 정점

4. 사이클(Cycle) : 시작과 종료의 정점이 동일한 경우

5. 단순 경로(Simple Path) : 동일 정점으로 연결되지 않는 경로

 

6. 정점의 차수(Degree) : 무방향 그래프에서 특정한 정점에 인접한 정점의 수

7. 진입 차수(In-Degree) : 방향 그래프에서 특정 정점으로 오는 간선의 수

8. 진출 차수(Out-Degree) : 방향 그래프에서 특정 정점에서 나가는 간선의 수

9. 경로 길이(Path Length) : 경로를 구성하는데 사용된 간선의 수

 

- 그래프의 종류는 방향의 유무, 모든 노드 연결 여부, 특정 노드 연결 여부, 순환 여부, 가중치 유무로 나뉠 수 있습니다.

 

- 방향의 유무에 따른 분류

1. 방향(Directed) 그래프

간선에 방향성이 존재하며, 한방향으로 진행되는 그래프입니다.

정점 A 에서 정점 B 방향으로 향하는 그래프는 <A,B> 로 표현합니다.(<B,A> 와 다릅니다.)

 

2. 무방향(Undirected) 그래프

간선에 방향성 없이 양방향으로 진행되는 그래프입니다.

정점 A 와 정점 B의 연결 그래프는 (A,B) 로 표현합니다.((B,A) 와 같습니다.)

 

- 모든 노드 연결 여부에 따라서는 모든 정점에 간선이 연결된 완전 그래프와 그렇지 못한 부분 그래프로 나뉘며,

특정 노드 연결 여부는, 특정 노드에 연결되었는지에 대해 연결 그래프와 비연결 그래프로 나뉘고,

순환 여부는, 시작 노드와 종료 노드가 연결된 순환 그래프와 그렇지 못한 비순환 그래프,

네트워크 연결 우선순위와 같이 간선에 가중치가 달렸는지에 따라 가중치 그래프와 비가중치 그래프로 나뉩니다.