[알고리즘] 알고리즘의 개념과 기본 자료구조

[알고리즘] 알고리즘의 개념과 기본 자료구조

1. 알고리즘의 정의와 조건

1) 알고리즘의 정의

주어진 문제를 풀기 위한 명령어들의 단계적 나열

 

2) 알고리즘의 조건

입력 : 0개 이상의 외부 입력
출력 : 1개 이상의 출력
명확성 : 각 명령은 모호하지 않고 명확해야 함
유한성 : 한정된 수의 단계를 거쳐 반드시 종료됨
유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 함

 

알고리즘의 조건을 합쳐서 정의하자면 알고리즘이란 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것이다.

 

2. 알고리즘 생성 단계

 

3. 알고리즘의 표현/기술 방법

알고리즘은 크게 일상 언어, 의사 코드(Pseudo code), 순서도의 세 가지 방법으로 표현할 수 있다.

 

의사코드(슈도코드, pseudocode)는 프로그램을 작성할 때 각 모듈이 작동하는 논리를 표현하기 위한 언어이다. 특정 프로그래밍 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드를 말한다.

 

다음은 '최대값 찾기 알고리즘'을 일상 언어, 의사 코드, 순서도로 표현한 것이다.

 

 

4. 알고리즘 기본 자료구조

알고리즘을 배울때 최소한 알아둬야 하는 기본 자료구조는 다음과 같다.

 

위 자료구조를 공부할때는 [배열, 연결리스트], [스택, 큐], [트리, 그래프]를 쌍으로 묶어서 함께 공부하면 좋다.

각 기본 자료구조를 간단히 알아보자.

 

1) 배열(Array)

 

- <index, value> 쌍으로 구성
- 각 원소들이 모두 같은 데이터 타입을 갖는다.
- 각 원소의 물리적 순서(메모리 주소)가 논리적 순서(인덱스 번호)와 동일하다.
- 첫 번째 원소의 메모리 주소로 다른 원소의 주소를 계산할 수 있다.
- [장점] 인덱스를 통한 직접 접근 ( = 어디로 접근하든 접근 시간 동일)
- [단점] 삽입/삭제 시 많은 양의 데이터 이동 필요
- 1차원 배열, 2차원 배열, 3차원 배열, ... , n차원 배열

 

2) 연결 리스트(Linked List)

 

- 데이터와 링크를 갖는 노드로 구성됨
- 논리적 순서와 물리적 순서가 동일하지 않음
- 데이터 삽입/삭제가 수월하다.
- 단일 연결 리스트, 단일 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트

 

3) 스택(Stack)

- 삽입/삭제가 한 쪽에서만 발생
- LIFO(Last In First Out)

 

4) 큐(Queue)

 

- 삽입과 삭제가 다른 쪽에서 발생
- FIFO(First In First Out)

 

5) 트리(Tree)

 

하나 이상의 노드로 구성된 유한 집합 T
- (조건1) T의 원소 중 단 하나의 루트 노드가 존재
- (조건2) 루트 노드를 제외한 나머지 노드는 n개(n≥0)의 서로 분리된 부분집합 T1, T2, ..., Tn(Ti : 서브트리)로 나누어진다.

 

📝 주요 용어

 

- 이진 트리(Binary Tree)

이진 트리는 각 노드의 degree(차수)가 2 이하인 순서 트리로 트리 중 가장 중요한 자료구조이다.

 

- 각 노드의 degree(차수)가 2 이하인 순서 트리
- 레벨 i에서 최대 노드 개수 = 2^i
- 높이가 h인 이진 트리의 최대 노드 개수 = 2^h-1
- Terminal(단말) 노드 수 = degree(차수)가 2인 노드 수 + 1

 

6) 그래프(Graph)

- 강력한 모델링 수단으로써 '관계'를 그래프로 추상화하여 다룰 수 있다.
- Vertex 집합 V와 Edge 집합 E에 대해 그래프 G = (V, E)

 

📝 주요 용어

 

References

한국방송통신대학교 컴퓨터과학과 알고리즘 강의