[1.1] 자료구조와 알고리즘
자료구조
사람들이 사물을 정리하는 것과 마찬가지로 프로그램에서도 자료들을 정리하는 여러 가지 구조들이 있는데, 이를 자료 구조라 부른다.
| 물건을 쌓아 놓는 것 | 스택 |
| 영화관 매표소의 줄 | 큐 |
| 할일 리스트 | 리스트 |
| 영어사전 | 사전, 탐색구조 |
| 지도 | 그래프 |
| 조직도 | 트리 |
알고리즘
컴퓨터 프로그램은 자료구조로 표현되고 저장되어있는 자료(data)와 주어진 문제를 처리하는 절차가 필요하다.
이러한 절차는 알고리즘이라고 불린다.
예를 들어 트리의 어떤 노드를 탐색하는 문제가 있을 때, 트리는 자료구조이고, 이 트리 상에서 어떤 노드를 탐색하는 절차를 기술한 것이 알고리즘이다.
알고리즘은 장치가 이해할 수 있는 언어로 기술된 명령어들의 집합으로,
알고리즘을 기술하는 데는 다음과 같은 방법이 있다.
- 자연어
- 흐름도(flowchart)
- 유사 코드(pseudo-code)
- 프로그래밍 언어
알고리즘이 되기 위한 조건은 다음과 같다.
- 입력: 0개 이상의 입력이 존재해야 한다.
- 출력: 1개 이상의 출력이 존재해야 한다.
- 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
- 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다.
- 유효성: 각 명령어들은 실행 가능한 연산이어야 한다.
[1.2] 추상 데이터 타입
데이터: 처리의 대상이 되는 모든 것
데이터 타입: 데이터의 집합과 이러한 데이터에 적용할 수 있는 연산의 집합
추상 데이터 타입: 새로운 데이터 타입을 추상적으로 정의한 것
자료 구조: 추상 데이터 타입을 프로그래밍 언어로 구현한 것
추상 데이터 타입
데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입
즉 데이터 타입을 추상적으로 정의함을 의미
데이터나 연산이 무엇(what)인지는 정의되지만, 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.
프로그램에서 추상 데이터 타입이 구현될 때 구현 세부사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개하게 된다. 즉 인터페이스만 정확하게 지켜진다면 추상 데이터 타입이 여러 가지 방법으로 구현될 수 있음을 뜻한다. 이를 통해 전체 프로그램을 변경 가능성이 있는 구현의 세부사항으로부터 보호하는 것이다.
[1.3] 알고리즘의 성능 분석
점점 더 처리해야 할 자료의 양이 많아지므로 효율성의 차이가 더 커지게 되고 사용자들은 빠른 프로그램을 선호하므로 경쟁력을 갖기 위해서는 최선의 효율성을 가져야 한다.
알고리즘의 복잡도 분석 방법
- 공간 복잡도 : 알고리즘이 사용하는 기억 공간 분석
- 시간 복잡도 : 알고리즘의 실행 시간 분석
- 시간 복잡도 : 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는 지를 숫자로 표시한다.
- 시간 복잡도 함수: 입력 갯수 n에 따라 변하는 T(n)으로 표기
빅오 표기법
자료의 개수가 많은 경우 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다. 따라서 불필요한 정보를 제거해 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오(big-oh notation) 표기법이라고 한다.
[ 정의 ]
두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>=n(0)에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n(0)가 존재하면 f(n)=O(g(n))이다.
많이 쓰이는 빅오 표기법 (실행 시간이 빠른 순)
- O(1) : 상수형
- O(log n) : 로그형
- O(n) : 선형
- O(n log n) : 선형 로그형
- O(n^2) : 2 차형
- O(n^3) : 3 차형
- O(2^n) : 지수형
- O(n!) : 팩토리얼형