[TOPCIT][01] III. 자료구조와 알고리즘 (에센스 정리 요약)

학습 목표

1. 자료구조의 정의와 분류에 대하여 설명하고, 선형/비선형구조를 활용할 수 있다.

2. 알고리즘의 역할을 이해하고 상황에 따라 적합한 알고리즘을 선택할 수 있다.

 

핵심 키워드

- 배열, 리스트, 스택, 큐, 데크, 트리, 그래프

- 알고리즘의 정의, 알고리즘 성능분석, 정렬/탐색 알고리즘

 

01 자료구조(Data Structure)

자료구조란? 자료를 컴퓨터의 기억장치 내에 저장하는 방법으로 다양한 자료를 효율적으로 표현하고 활용할 수 있도록 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의한 것

 

자료구조의 분류

선형구조 : 자료가 일렬로 연결되어 있는 형태로 구성하는 방법

비선형구조 : 자료의 구성이 계층구조나 망구조의 특별한 형태를 띠는 구조

스택과 큐

스택

- 스택은 선형리스트의 하나로 데이터가 입력된 순서로 기억공간에 저장되어 출력 시 가장 나중에 쌓인 데이터가 가장 먼저 출력을 하게 되는 자료구조

- 스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하여 top 위치에서만 원소를 삽입하고 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 출력되게 됨

스택의 연산 종류

- top() : 스택의 맨 위에 있는 데이터 값 반환

- push() : 스택에 데이터 삽입

- pop() : 스택에서 데이터를 삭제해 반환

- isempty() : 스택에 원소가 없으면 true 값을 반환하고 있으면 false 값을 반환

- isfull() : 스택에 원소가 없으면 false 값을 반환하고 있으면 true 값을 반환

 

큐

- 스택과 유사하게 삽입과 삭제의 위치가 제한되어 있지만 스택과는 달리 데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료 구조

- 큐는 뒤에서만 삽입되고 앞에서는 삭제만 할 수 있는 구조로 삽입된 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제됨

큐의 연산 종류

- enQueue : 큐에 데이터 삽입

- deQueue : 큐에서 데이터 삭제

 

스택과 큐의 연산 비교

항목	삽입연산		삭제연산
자료구조	연산자	삽입위치	연산자	삭제위치
스택	push	top	pop	top
구조	enQueue	rear	deQueue	front

트리와 그래프

트리(Tree)

- 원소들 간에 계층관계를 가지느느 계층형 자료 구조로 상위원소에서 하위 원소로 내려가면서 확장되는 나무 모양의 구조를 가지고 있으며 원소들 간에 1:다 관계를 가짐

- 루트노드 : 트리의 시작노드

- 간선 : 노드를 연결하는 선

- 형제노드 : 같은 부모 노드를 가진 자식 노드들

- 서브트리 : 부모노드와 연결된 간선을 끊었을 때 생성되는 트리

그래프(Graph)

- 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조

- 객체를 나타내는 정점과 객체를 연결하는 간선의 집합

- 최단거리 검색, 인공지능 등과 같이 여러 복잡한 문제들을 그래프로 나타내어 문제 해결하는 경우가 많음

자료구조의 선택 기준

1. 자료의 처리 시간

2. 자료의 크기

3. 자료의 활용 빈도

4. 자료의 갱신 정도

5. 프로그램의 용이성

 

자료구조의 활용

1. 리스트 : 배열의 구현, DBMS 인덱스, 탐색이나 정렬 등

2. 스택 : 인터럽트 처리, 재귀 프로그램의 순서 제어, 서브루틴의 복귀 번지 저장, 후위 표기법으로 표현된 수식의 연산, 텍스트 에디터 Undo 기능 등

3. 큐 : 운영체제의 작업 스케줄링, 대기 행렬의 처리, 비동기 데이터 교환 등

4. 데크 : 스택과 큐의 장점만 활용한 자료구조로 스택과 큐 관련 분야에서 활용

5. 트리 : 탐색이나 정렬과 같은 문제, 문법의 파싱, 허프만 코드, 결정 트리 등

6. 그래프 : 컴퓨터 네트워크, 이항 관계 등

 

02 알고리즘(Algorithm)

알고리즘이란? 주어진 문제를 해결하기 위한 일련의 처리 절차를 단계적으로 기술한 것으로 문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

 

알고리즘의 조건

입력 : 0개 이상 입력으로 제공될 수 있어야 함

출력 : 하나 이상의 결과를 출력해야 함

명확성 : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 각 처리 단계의 명령어들은 명확하게 명세되어야 함

유한성 : 수행 후에 반드시 종료되어야 함

효과성 : 모든 명령어들은 기본적이며 실행 가능해야 함

 

알고리즘 분석 기준

정확성 : 알고리즘이 타당한 입력에 대해 유한 시간 내에 올바른 결과를 산출하는가

작업량 : 알고리즘을 수행하는데 걸리는 수행 횟수 (일반 연산 제외, 중요한 연산만 측정)

기억 장소 사용량 : 알고리즘 수행 시 필요한 컴퓨터 메모리 사용량

최적성 : 알고리즘을 적용할 시스템의 사용 환경(수행량, 메모리 사용량 등)을 고려할 때 최적인가

단순성 : 알고리즘의 표현이 얼마나 이해하기 쉽게 명확하게 작성되었는가

 

알고리즘 표현 방법

자연어 기술(일상적으로 사용하는 말이나 글), 순서도 표현, 수도코드

 

알고리즘 성능 분석

공간 복잡도 = 고정 공간량 + 가변 공간량

- 고정 공간량 : 프로그램, 변수 및 상수들과 같이 프로그램의 크기나 입출력 횟수에 상관없이 고정적으로 필요한 저장 공간

- 가변 공간량 : 프로그램의 수행과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간

시간 복잡도 = 컴파일시간 + 실행시간

- 컴파일시간 : 프로그램 특성과 관련이 적은 고정적인 시간으로 일단 컴파일이 되면 프로그램의 수정이 일어나지 않는 한 일정하게 유지

- 실행시간 : 프로그램의 실행시간으로 컴퓨터의 성능 등에 의존하므로 실제 정확한 실행시간을 측정하기 보다는 명령문의 실행 빈도수를 구하여 계산

 

정렬 알고리즘

내부정렬이란? 소량의 데이터에 대해 주기억 장치에 올려서 정렬하는 방식으로 정렬 속도는 빠르나 주기억 장치의 용량에 의해 정렬할 수 있는 데이터의 양이 제한됨

 

외부정렬이란? 대량의 데이터에 대해 보조 기억 장치에서 정렬하는 방식으로 대량의 데이터를 몇 개의 서브 파일로 나누어 내부 정렬을 한 후 보조기억장치에서 정렬된 각 서브 파일들을 병합하는 방식으로 속도가 느림

 

내부정렬의 종류

- 삽입법 : 삽입정렬, 쉘정렬

- 교환법 : 선택정렬, 퀵정렬, 버블정렬

- 선택법 : 힙정렬

- 병합법 : 머지정렬

- 분배법 : 계수정렬, 기수정렬, 버킷정렬

 

내부 정렬 알고리즘의 수행시간 비교

정렬방법	수행시간 -  최악	수행시간 - 평균	수행시간 - 최선	추가메모리
삽입정렬	O(n^2)	O(n^2)	O(n)	없음
쉘정렬	O(nlog2(n))	O(n^15)	O(n)	없음
선택정렬	O(n^2)	O(n^2)	O(n^2)	없음
퀵정렬	O(n^2)	O(nlogn)	O(nlogn)	없음
버블정렬	O(n^2)	O(n^2)	O(n^2)	없음
힙정렬	O(nlogn)	O(nlogn)	O(nlogn)	없음
머지정렬	O(nlogn)	O(nlogn)	O(nlogn)	있음
기수정렬	O(dn)	O(dn)	O(dn)	있음

 

선택정렬이란? 가장 간단한 정렬 알고리즘 중 하나로 배열 A[1...n]에서 가장 큰 원소를 찾아 배열의 맨 끝자리에 있는 A[n]자리를 바꾸는 정렬방법

 

버블정렬이란? 선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하지만 제일 큰 원소를 오른쪽으로 옮길 때 왼쪽에 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 자리를 바꾸어 진행하는 정렬알고리즘

검색 알고리즘

- 데이터 집합에서 원하는 항목을 효율적으로 찾는 기법

- 데이터의 정렬 여부에 따라 순차검색(Linear Search)과 제어검색(Control Search)으로 구분할 수 있음

- 특정 함수에 따라 키 값을 계산하여 데이터를 검색하는 해싱도 있음

- 자료구조의 형태 및 자료의 배열 상태를 고려하여 최적의 탐색 방법을 선택해야 함

 

검색 알고리즘의 분류

분류방법	데이터정렬	종류	내용 및 특징
선형 검색 (Linear Search)	X	선형 탐색 (Linear Search)	- 처음부터 마지막까지 순서대로 각 레코드를 비교하면서 찾아가는 방법 - 프로그램 작성이 용이 - 파일의 크기가 커질수록 탐색시간이 증가 - 가장 간단하고 직접적인 검색 방법 - 평균비교횟수 : (n+1)/2 - 평균검색시간 : O(n)
제어 검색 (Control Search)	O	이진 탐색 (Binary Search)	- 상한값과 하한값을 설정하고 그 중간값을 구한 후 키와 중간값을 계속 비교하면서 검색하는 방법 - 파일의 탐색 대상을 1/2씩 줄여가면서 탐색하므로 효율적임 - 레코드 수가 많을 수록 효과적임 - 평균검색시간 : O(log2(n))
		피보나치탐색 (Fibinacci Search)	- 피보나치 순열을 이용하여 서브 파일을 형성해 가면서 검색하는 방법 - 이진검색은 나눗셈을 이용하나, 피보나치 검색은 덧셈과 뺄셈만으로 검색이 가능하므로 속도가 빠름 - 평균검색시간 : O(log2(n))
		보간탐색 (Interpolation Search)	- 탐색 대상이 있을 것으로 예상되어지는 위치를 선택하여 찾아가는 방식으로 이후 그 위치에서 선형 탐색을 함 - 사전이나 전화번호부, 색인명 등과 같은 탐색에 이용 - 평균적으로 O(logn)의 성능
		블록탐색 (Block Search)	- 전체 데이터를 일정한 개수의 블록으로 구분하고 찾기를 원하는 데이터가 속한 블록을 결정한 후에 해당 블록 내의 키 값을 순차적으로 검색하는 방법 - 효율적인 블록의 크기는 루트n - 프로그램 작성과 갱신이 쉬움 - 평균적으로 O(logn)의 성능
		이진트리탐색 (Binary Tree Search)	- 이진 트리를 이용하는 검색방법 - 평균적으로 삽입/검색/삭제 모두 O(logn)의 성능
특정 함수를 이용하여 접근하는 방식	X	해싱 (Hashing)	- 해싱함수를 이용하여 데이터가 저장되어 있는 주소를 직접 계산하여 찾아가는 검색방법 - 삽입과 삭제가 빈번한 자료에 적합함

 

그래프 탐색

- 그래프의 가장 기본적인 연산

- 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산

- 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부나 전자회로에서의 단자 연결 여부 등 해결해야 하는 많은 문제들이 단순히 그래프 노드를 탐색하는 것으로만 해결되는 경우가 많음

- 종류로는 깊이 우선 탐색과 너비 우선 탐색이 있음

 

깊이 우선 탐색 (DFS, Depth First Search)

- 시작 정점의 한 방향으로 갈 수 있는 경로가 있는데까지 깊이 탐색해가다 더 이상 갈 곳이 없으면 마지막 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하여 목표 노드를 찾을 때까지 정점을 방문하는 방법

- 마지막 갈림길 간선의 정점으로 되돌아가 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용

- 현재 경로상의 노드들만 기억하기 때문에 저장 공간의 수요가 적고 목표노드가 깊은 단계에 있는 경우 신속하게 목표를 찾을 수 있고 구현이 용이함

 

너비 우선 탐색(BFS, Breadth First Search)

- 하나의 시작 정점을 방문한 후 인접한 노드를 먼저 탐색하는 방법

- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법

- 너비 우선 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검색하야 하고 방문한 노드들을 차례대로 꺼낼 수 있는 자료구조인 큐를 사용함

최소 신장 트리(Minimum Spanning Tree)

- 신장트리란? 무방향 가중치 그래프 내 모든 정점을 포함하고 서로 연결되어 있는 트리의 특수한 형태로 사이클을 포함해서는 안되는 트리

- 구성하는 가중치의 합이 최소인 신장 트리

- 최소 신장 트리를 구현하는 대표적인 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 있음

 

크루스칼(Kruskal) 알고리즘

- 정점에 연결된 간선 가운데 가중치가 최소인 간선을 선택하고 추가된 간선이 사이클을 만드는지 체크하는 방식으로 처리함

- 가중치가 가장 낮은 간선을 선택한 후 정점과 연결이 되어 있지 않더라고 가중치가 작은 간선을 순서대로 선택하는 방법

 

프림(Prime) 알고리즘

- 분석대상 그래프에서 임의의 한 정점을 선택하여 각 반복과정마다 그때까지 구성된 최소 신장 트리 부분에 방문하지 않은 새로운 정점과 간선을 선택하여 확장해나가는 방법