그림으로 정리한 알고리즘과 자료구조(2018)

제목 : 그림으로 정리한 알고리즘과 자료구조 

저자 : 조민호 

출판사 : 정보문화사 

 

목차

1. 컴퓨터를 바라보는 관점
2. 알고리즘이란 무엇인가?
3. 알고리즘의 개발
4. 자료구조
5. 정렬 알고리즘
6. 검색 알고리즘
7. 컴퓨터 역사에 남을 유명한 알고리즘
8. 알고리즘 활용을 위한 추가 지식 

---

2장 요약 

컴퓨터는 판정, 선택, 응답, 기억의 네 가지 주요 회로로 구성된 기계이다. 주어진 문제 해결을 위해 네 가지 기능을 반복 수행한다. 

프로그래밍 : 문제 해결을 위하여 수행할 작업을 단위 작업으로 나누고 이것을 어떻게 수행해야 문제를 해결할 수 있는지 연구

코딩 : 프로그래밍된 것을 특정 언어로 번역하는 과정이며 코딩된 것은 컴퓨터에서 수행할 수 있다. 

알고리즘 : 프로그래밍에서 문제 해결을 위해 단위 작업을 어떤 순서로 어떻게 반복하면 효과적으로 해결할 수 있는지 연구하는 분야 

알고리즘은 주어진 문제를 단위 작업으로 나누고, 이것의 진행 순서나 절차를 흐름도를 이용해서 표현한다. 

 

3.1 프로그램과 알고리즘의 관계

좋은 프로그래머가 되기 위해서는 주어진 과제를 단위 작업-더 쪼개면 의미가 없어지는 단위로 쪼개는 작업 으로 나눈 후에, 

이들을 잘 조합할 수 있는 능력을 가져야 한다.

 

3.4 알고리즘의 구조화

알고리즘을 고안하려면 대부분의 경우 구조화 단계를 거친다.

구조화란 전체를 부분으로 나누어 구조화한 후에 알고리즘을 구성하는 요령을 말한다. 

 

4장 자료구조 요약

- 자료구조는 컴퓨터에서 다뤄야 하는 데이터가 많은 경우, 이것을 다루는 방법이다. 

- 사용자의 편리성을 위하여 다양한 자료구조가 개발되지만, 실제적인 구현은 리스트와 연결 리스트를 사용한다.

 

4.1 컴퓨터의 데이터 취급 방법

사용자 정의 자료형의 종류는 대표적인 형이 동일한 것을 여러 개 모아서 처리하는 배열과 다른 데이터 형을 여러 개 모아서 처리하는 구조체, 그리고 구조체에 처리하는 함수를 포함하는 클래스로 나누어 볼 수 있다. 

 

모든 프로그램은 만들기 전에 프로그램에서 사용할 자료형을 정의한 다음 만든다. 그러므로, 단위 작업의 분류와 수행 정차를 확정(알고리즘)한 다음 실제 프로그램 코딩을 하기 전에, 사용할 자료형을 정의하는 것은 필수적인 과정이다. 

 

4.4 자료구조의 구현 

자료구조의 종류는 많지만, 실제 자료구조를 구현하는 기술은 리스트와 연결 리스트 두 가지가 있다. 즉 리스트와 연결 리스트를 이용하여 다양한 자료구조가 만들어진다. 

리스트 : 데이터들이 연속적인 공간을 할당 받아 만들어지는 구조

연결리스트 :데이터들이 각각 공간을 할당 받고, 데이터 사이의 연결고리가 만들어지는 구조 

리스트형 자료구조는 두가지가 있다. 크기가 변하지 않는 배열과 크기가 변하는 리스트. 리스트로 선언된 것은 메모리에 연속적인 공간을 할당받아 사용하게 된다. 이에 반해 연결 리스트는 기본적으로 제공하지 않고 프로그래머가 자체적으로 구현하여 사용한다. 데이터를 포인터로 연결하여 사용한다. 

- 해쉬 테이블의 구현 

해쉬 테이블은 데이터를 저장할 때, 저장할 위치를 해쉬 함수를 이용해서 생성하고, 생성된 위치에 데이터를 저장하는 방식에서 사용하는 주소 테이블이다. 순서 리스트와 연결 리스트 자료구조를 조합하여 사용하며, 데이터에 직접적인 접근이 가능하여 저장/읽기 속도가 빠르다. 

해쉬 테이블

 

-스택 자료구조 알아보기 

스택 형태의 데이터 구조를 LIFO형이라고 하며, 스택에 데이터를 넣는 것을 푸시, 데이터를 꺼내는 것을 팝이라고 한다.

스택의 구현은 배열을 이용해도 되고 연결 리스트를 이용해도 된다. 스택은 대표적으로 프로그램을 수행할 때와, 수식을 연산하는 수행과정에서 사용한다. 

다중 스택 : 하나의 공간에 2개의 스택을 구현하여 각자 사용하는 것을 다중 스택이라고 한다. 

스택

 

-큐 자료구조 

큐 형태의 데이터 구조를 FIFO형이라고 한다. 큐의 구현은 배열을 이용하거나(순환 큐), 또는 연결 리스트를 이용한다(링크드 큐). 

큐

 

-데크 자료구조 

데크는 리스트의 양쪽 끝에서  삽입과 삭제가 모두 이루어지는 자료구조이며, 스택과 큐를 혼합한 구조로 하나의 배열을 선언한 후, 2개의 포인터로 양쪽 끝을 가리키고 이것을 이용하여 양쪽에서 삽입, 삭제 연산을 수행한다.

 

4.12 힙-트리 자료구조의 응용 

컴퓨터 분야에서 힙은 두 가지 의미로 사용된다. 하나는 이진 트리의 일종으로 여러 개의 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조이다. 다른 하나는 컴퓨터에서 프로세스가 만들어졌을 때, 메모리를 할당하게 되는데, 이때 메모리를 할당하는 방법이 스택과 힙 두가지이다. 

 

4.13 그래프 자료구조 

2개 이상의 항목이 어떤 관계를 맺고 있는지를 노드와 에지 (정점과 선)를 이용하여 표현하는 것을 그래프라고 한다. 

그래프 용어  - 깊이 우선 탐색 DFS - 너비 우선 탐색 BFS  - 신장트리 - 최소 비용 신장 트리 

그래프 사용 방법  - Prim 방법, Kruskal 방법

사용하는 곳 대표적인 - PERT/CPM, 최단 경로 

 

4.14 프로그램 언어에서의 자료구조 지원 

C언어에서는 자바 컬렉션을 STL 라이브러리 라고 한다. 

 

 

8.1 알고리즘의 성능 및 표기방법

- 알고리즘의 우수함 식별 기준 : 정확성, 작업량, 메모리 사용량, 단순성, 최적성