알고리즘이란?
문제를 해결하기 위한 절차나 방법.
조건
- 입력 0개 이상
- 출력 1개 이상
- 명백해야함
- 실행 가능한 연산이어야 한다(유효성)
- 반드시 종료되어야함(유한성) ★
--> 알고리즘과 프로그래밍은 다르다.
OS는 PC를 키고있는 동안 계속된다.
그러므로 알고리즘 관점(반드시 종료가 있어야함)으로 봤을때
만족시키지 못하므로 알고리즘과 프로그래밍 관점은 다르다.
알고리즘의 기술 방법
(1) 자연어로 표기된 알고리즘
인간이 읽기가 쉽다.
단점: 단어들을 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있다.
(2) 흐름도로 표기된 알고리즘
직관적이고 이해하기 쉬운 알고리즘 기술 방법
단점: 복잡한 알고리즘의 경우, 상당히 복잡해짐.
(3) 유사코드로 표현된 알고리즘
알고리즘의 고수준 기술 방법이고 가장 많이 사용한다.
프로그램을 구현할 때의 여러 가지 문제들을 감출 수 있고 알고리즘의 핵심적인 내용에만 집중할 수 있다.
(4) 특정 언어로 표현된 알고리즘
알고리즘의 가장 정확한 기술 가능
실제 구현시의 많은 구체적인 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있음
예) C언어로 표기된 알고리즘
알고리즘 분류
1. 분할-정복 알고리즘
- 합병 정렬(Merge sort), 퀵 정렬(Quick sort), 선택(Selection) 문제
2. 그리디 알고리즘
- top-down 방식으로 최적화 문제를 해결하는 알고리즘 (위에서부터 내려옴)
- 동전 거스름돈, 최소 신장 트리, 최단 경로, 부분 배낭 문제, 집합 커버, 작업 스케줄링, 허프만 압축
3. 동적 계획
- 최적화 문제를 해결하는 bottom-up 방식의 알고리즘 (아래에서 위로)
- 모든 쌍 최단 경로, 연속된 행렬 곱셈, 편집거리 문제, 배낭 문제, 동전 거스름돈 문제
4. 정렬 알고리즘
- 기본적인 정렬 알고리즘인 버블 정렬(Bubble sort), 선택 정렬(Selection sort), 삽입 정렬(Insertion sort)을 다루고, 이 보다 효율적인 쉘 정렬(Shell sort)과 힙 정렬(Heap sort)을 살펴보며, 특정 환경에서 사용되는 기수 정렬(Radix sort)과 외부정렬(External sort)
5. 근사 알고리즘
- 정확한 값보다는 근사 값를 찾는 알고리즘
프로그램 = 자료구조 + 알고리즘
ex) 최대값 탐색 프로그램 = 배열(자료구조) + 순차탐색(알고리즘)
어떤 알고리즘이 가장 좋은 알고리즘일까?
선택에 기준에 따라 다르다.
예로 2가지 기준으로 살펴보자.
1. Time
(알고리즘이 시작하고 끝날때까지의 시간이 짧을 수록 좋다)
--> 대신 비교하는 서로에 하드웨어가 무관(independent)하다는 가정하에 비교를 해야함.
ex) cpu가 i3와 i7으로 비교하면 같은 알고리즘도 하드웨어 속성에 따라 시간이 다르게 나오므로.....
2. Space
(메모리 공간을 적게 차지할 수록 좋은 알고리즘이다)