자료구조와 알고리즘 - 이강욱

[TOPCIT 목차]

 

1. 자료구조 (Data Structure)

가) 정의

- 컴퓨터에서 자료를 저장하고 사용하는 방법의 정의

 

나) 분류

1) 자료구조의 분류

- 선형구조 (Linear) : 자료간의 관계가 1:1로 나열

- 비선형구조 (Nonlinear) : 자료간의 관계가 N:N으로 배치

 

2) 저장방식의 비교

구분	순차자료구조	연결자료구조
메모리 저장 방식	순차 저장	임의 위치 저장
논리/물리 순서 일치 여부	일치	불일치
연산 특징	삽입/삭제시 물리적 위치 재조정 필요	삽입/삭제시 링크정보만 변경
프로그램 기법	배열을 이용한 구현	포인터를 이용한 구현

 

다) 스택과 큐

1) 스택 (Stack)

- 데이터 삽입(push), 삭제(pop)은 top 위치에서 실행

 

2) 큐 (Queue)

- 데이터 삽입(enQueue)은 rear, 데이터 삭제(deQueue)는 front 위치에서 실행

 

라) 트리와 그래프

1) 트리 ( Tree)

- 원소들 간에 1:N의 계층관계를 가지는 계층형 자료구조

항목	설명
루트 노드 (root node)	최상위 노드
부모 노드 (parent node)	해당 노드의 상위 노드
조상 노드 (ancestor node)	부모 노드를 포함한 상위 모든 노드(들)
자식 노드 (child node)	해당 노드의 하위 노드(들)
자손 노드 (descendant node)	자식 노드를 포함한 하위 모든 노드(들)
형제노드 (sibling node)	같은 부모 노드를 갖는 노드(들)
간선 (edge)	노드간의 연결선
서브트리 (subtree)	트리에서 생성되는 트리

 

2) 그래프 (Graph)

- 원소들 간의 N:N 관계를 표현하는 자려구조

(1) 그래프의 종류

종류	설명
무방향 그래프	정점(vertex) 사이에 방향성이 없는 간선(edge)으로 연결된 그래프
방향 그래프	정점 사이에 방향성이 있는 간선으로 연결된 그래프
완전 그래프	모든 정점이 서로 연결된 그래프
가중 그래프	정점을 연결하는 간선에 가중치를 할당한 그래프

 

(2) 그래프 구현 방식

- 인접행렬 (Adjacency Matrix) : 순차 자료구조를 이용한 방식으로 간선의 유무를 행열로 저장하는 방식

- 인접리스트 (Adjacency List) : 연결 자료구조를 이용한 방식으로 각 정점의 차수만큼 노드를 연결하는 방식

 

마) 자료구조의 선택 기준

(1) 자료의 처리 시간

(2) 자료의 크기

(3) 자료의 활용 빈도

(4) 자료의 갱신 정도

(5) 프로그램의 용이성

 

바) 자료구조의 활용

분류	자료구조	활용
선형구조	리스트	- 배열의 구현 - DBMS 인덱스 - 탐색, 정렬 등
	스택	- 인터럽트 처리 - 프로세스 호출의 순서 제어 - 후위 표기법 수식의 연산 - 텍스트 에디터 Undo
	큐	- OS 작업 스케줄링 - 대기 행렬의 처리 - 비동기 데이터 교환 (파일 I/O, Pipe, Sockets) - 키보드 버퍼
	데크	- 스택과 큐의 혼합
비선형구조	트리	- 탐색, 정렬 - 문법의 파싱 - 허프만 코드 - 결정트리
	그래프	- 컴퓨터 네트워크 - 전기회로 분석 - 이항 관계 - 연립방정식

 

2. 알고리즘 (Algorithm)

가) 알고리즘 개요

1) 알고리즘의 정의

- 문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술한 명세서

 

2) 알고리즘의 조건

조건	설명
입력 (Input)	0개 이상 입력 제공
출력 (Output)	1개 이상 출력
명확성 (Definiteness)	각 처리단계 명령어들의 명세
유한성 (Finiteness)	수행 후 종료
효과성 (Effectiveness)	모두 실행가능한 명령어

 

나) 알고리즘 분석 기준

분석기준	설명
정확성 (Correctness)	- 입력에 대한 정확한 결과 산출
작업량 (Amount of Work Done)	- 알고리즘을 수행하는데 걸리는 수행 횟수
기억 장소 사용량 (Amount of Space Used)	- 컴퓨터 메모리의 사용량
최적성 (Optimality)	- 사용환경을 고려한 최적성
단순성 (Simplicity)	- 알고리즘 표현의 단순성

 

다) 알고리즘 표현 방법

표현 방법	설명
자연어 기술	일상 언어를 이용한 알고리즘 표현
순서도 표현	순서도나 NS차트를 이용한 알고리즘 표현
의사 코드 (Pseudo Code)	프로그래밍 언어와 유사한 형태로 알고리즘 표현

 

라) 알고리즘 성능 분석

항목	산출방법	설명
공간 복잡도	공간 복잡도 = 고정 공간량  + 가변 공간량	- 고정 공간량 : 입출력과 관계없이 고정된 공간 - 가변 공간량 : 수행과정에서 사용되는 공간
시간 복잡도	시간 복잡도 = 컴파일 시간 + 실행시간	- 컴파일 시간 : 컴파일 수행시간 (변동없음) - 실행 시간 : 프로그램의 실행시간 (컴퓨터 성능과 비례) ** 객관적 지표를 위해 실제 실행시간보다 실행명령어 갯수로 사용

- 복잡도는 빅-오 표기법을 사용 ( O(n), O(log n), 등)

 

마) 정렬 알고리즘

1) 정렬의 분류

- 주기억장치에서 정렬하는 내부정렬, 보조기억장치에서 정렬하는 외부 정렬

항목	내부 정렬	외부 정렬
정렬 장소	- 주기억장치	- 보조기억장치
정렬 속도	- 빠른 정렬 속도	- 느린 정렬 속도
데이터량	- 주기억장치 용량에 따라 제한적	- 대량의 데이터 - 서브파일 분할 정렬

 

2) 내부 정렬 알고리즘의 분류

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

정렬방법	설명	수행시간			추가 메모리
		최악	평균	최선
삽입정렬	- 데이터의 정렬을 가정하고 해당 위치에 삽입	O(n^2)	O(n^2)	O(n)	없음
쉘정렬	- 데이터를 일정 기준으로 부파일로 쪼개고, 각 부파일의 삽입 정렬을 수행. - 부파일의 크기를 눌리며 해당 과정을 반복 수행	O(nlog(2)n)	O(n^1.5)	O(n)	없음
선택정렬	- 최소값을 찾아 이동시키는 과정을 데이터 크기만큼 반복 수행	O(n^2)	O(n^2)	O(n^2)	없음
퀵정렬	- 분할정복방식으로, 임의의 기준점(pivot)으로 데이터 분할하는 작업의 반복수행으로 정렬 - 재귀호출 사용	O(n^2)	O(nlog n)	O(nlog n)	없음
버블정렬	- 인접한 데이터간의 비교를 통한 정렬 방법	O(n^2)	O(n^2)	O(n^2)	없음
힙정렬	- 최대/최소 힙트리를 구성해 정렬하는 방법	O(nlog n)	O(nlog n)	O(nlog n)	없음
머지정렬	- 분할정복방식으로, 데이터의 크기를 반으로 계속 나누고 이를 정렬하고 합치는 방법	O(nlog n)	O(nlog n)	O(nlog n)	있음
기수정렬	- 낮은 기수(자릿수)부터 비교하여 정렬하는 방법	O(dn)	O(dn)	O(dn)	있음

 

바) 검색 알고리즘

1) 검색 알고리즘의 개요

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

 

2) 검색 알고리즘의 분류

분류방법	데이터 정렬	종류	내용 및 특징
선형검색 (Linear Search)	X	선형탐색 (Linear Search)	- 처음부터 마지막까지 비교 검색하는 방법 - 프로그램 작성 용이 - 평균비교횟수 : (n+1)/2 - 평균 검색시간 : O(n)
제어 검색 (Control Search	O	이진 탐색 (Binary Search)	- 상한값(F)과 하한값(L)을 설정하고 그 중간값(M)을 구한 후 키와 중간값을 계속 비교하며 검색하는 방법 - 탐색 대상을 1/2씩 줄여가며 탐색 - 평균 검색시간 : O(log(2)n)
		피보나치탐색 (Fibonacci Search)	- 파보나치 순열을 이용하여 서브파일을 형성해 가면서 검색하는 방법 - 덧셈과 뺄샘만으로 검색 - 평균 검색시간 : O(log(2)n)
		보간탐색 (Interpolation Search)	- 예상되는 위치를 선택하여 그 위치에서 선형 탐색 - 사전, 전화번호부등 색인 탐색에 이용 - 평균 O(log(n))의 성능
		블록탐색 (Block Search)	- 전체 데이터를 블록으로 분할하고, 블록 내에서 순차적 검색하는 방법 - 효율적인 블록크기는 √n - 평균 O(log(n))의 성능
		이진트리탐색 (Binary Tree  Search)	- 이진트리를 이용하는 검색방법 - 평균 O(log(n))의 성능
특정 함수를 이용하여 접근하는 방식	X	해싱 (Hashing)	- 해싱함수를 이용하여 데이터 주소를 찾는 검색 방법 - 삽입과 삭제가 빈번한 자료에 적합함

 

사) 그래프 탐색 알고리즘

알고리즘	설명
깊이 우선 탐색 (Depth First Search)		- 시작 정점의 한방향으로 계속 방문하고, 그 경로의 마지막 정점에 방문 후에 마지막 갈림길 간선이 있는 정점에서 한방향 방문을 반복하여 탐색. - 구현시 스택을 이용. - 상대적으로 적은 저장공간 사용
너비 우선 탐색 (Breadth First Search)		- 시작 정점을 방문 후 인접한 노드를 먼저 탐색하는 방법. - 구현시 큐를 이용.

 

아) 최소 신장 트리(Minimum Spanning Tree)

- 무방향 그래프 내의 모든 정점이 연결되어있고, 사이클이 없고, 구성하는 가중치의 합이 최소인 트리

- 특징) 간선의 수는 n-1, 무 사이클

알고리즘	설명
크루스칼 알고르즘 (Kruskal)	- 간선을 가중치 기준으로 오름차순 정렬하고, 간선들을 순서대로 연결하는 알고리즘 - Union-Find 알고리즘 이용
프림 알고리즘 (Prim)	- 임의의 정점을 기준으로 최소비용 정점을 선택하며 방문하는 알고리즘 - Priority Queue를 이용