알고리즘
태그 :
- 개념
- 어떠한 문제를 해결하기 위한 일련의 생각의 흐름 Algorithm is an effective method expressed as a finite list of well defined instructions for calculating a function
I. 자료구조와 알고리즘의 개요
가. 알고리즘의 정의
- 어떠한 문제를 해결하기 위한 일련의 생각의 흐름
- Algorithm is an effective method expressed as a finite list of well defined instructions for calculating a function.
나. 알고리즘의 조건
조건 |
설명 |
입출력 |
0개 이상의 외부 입력 / 1개 이상의 출력 |
명확성 |
각 명령어는 모호하지 않고 의미가 명확해야 함 |
유한성 |
알고리즘은 수행 뒤에 반드시 종료 |
유효성 |
모든 명령들은 오류가 없이 실행 가능해야 함 |
효율성 |
충분히 큰 입력에 대하여 알고리즘의 수행 시간은 크게 차이가 발생하기 때문에 효율적으로 수행되어야 함 |
- 프로그램은 유한성이 만족되지 않아도 된다는 측면에서 알고리즘과 프로그램이 구별됨
다. 알고리즘의 선택 기준
기준 |
설명 |
정확성 |
알고리즘에서의 입력데이터와 수행 후 기대되는 출력에 대해 정확히 이해/일반적으로 수학적 귀납법 이용 증명 |
효율성 |
알고리즘의 수행에 소요되는 컴퓨터 자원의 양 (기억장치 의 소요량과 수행시간)을 의미 프로그램의 효율성을 높이기 위한 튜닝 작업은 시스템을 구현한 후에 이루어져야 함 수행시간의 80% 이상을 코드의 20% 이하 부분에서 소비 한다는 현상 |
적합성 |
목표 시스템의 하드웨어와 소프트웨어에 적합을 의미 |
라. 알고리즘의 생성 절차
알고리즘 설계 -> 표현 -> 정확성 검증 -> 효율성 분석
II. 자료구조와 알고리즘의 유형
가. 알고리즘의 유형
|
|
III. 알고리즘 설계기법
가. 알고리즘 설계 목표
- 알고리즘은 궁극적으로 컴퓨터에서 수행하는 것을 목표로 하므로 실용성이 있어야 하고 효율성도 필요
- 입출력, 명확성, 유한성, 효과성을 만족하는 알고리즘이 존재하면 그 문제가 해결 가능함
나. 대표적인 설계 기법
기법 |
설명 |
예제 |
욕심쟁이 방법 (greedy method) |
해를 구하는 일련의 선택 과정마다 그 단계에서 최선이라고 볼 수 있는 선택을 행해나가면 결과적으로 전체적인 최적해를 구할 수 있을거 라는 희망적인 전략을 취하는 방법 최적의 해를 구한다는 보장을 못함 |
크루스칼, 다익스트라 알고리즘 / 허프만 트리 |
분할과 정복 방법 (divide and conquer method) |
문제를 더 이상 나눌 수 없을 때까지 나누고, 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 방법 문제를 쪼개는 요령이나 규칙은 없음 |
병합정렬 / 거듭제곱 |
동적 프로그래밍 방법 (dynamic programming method) |
어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어질 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법 소문제에 대한 여러 최적해로부터 다음 크기의 소문제에 대한 최적해가 결정 |
피보나치 수 / LCS알고리즘 |
백트래킹 (back tracking) |
여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘 목적 : "진짜 해"를 효율적으로 찾는 것 |
N-Queen 알고리즘 |
IV. 알고리즘 표현방법
구분 |
내용 |
흐름도 |
장점 : 명령의 흐름을 쉽게 파악 단점 : 복잡한 알고리즘을 나타내기에는 역부족
|
프로그램 설계언어 |
프로그래밍 언어를 사용하여 알고리즘을 표현하는 방법 장점 : 알고리즘 자체가 실제로 구체화된 구현이므로 추가적인 구체화 작업이 필요 없음 단점 : 알고리즘을 번역하고 필요한 다른 프로그래밍 언어로 변환해야 하는 작업이 필요 |
의사코드 (pseudo-code) |
프로그래밍 언어의 형태를 갖춘 의사코드(pseudo-code)를 사용하여 알고리즘을 표현하는 방법 장점 : 원하는 특정 프로그래밍 언어로 변환 (구체화 작업) 하기가 쉬움 단점 : 특정 프로그래밍 언어가 아니기 때문에 직접 실행할 수는 없음 |
V. 알고리즘 평가 방법
가. 알고리즘의 성능을 가리는 5가지 측정기준
- 정확성 : 알고리즘이 정확하게 동작하는가
- 작업량 : 얼마나 적은 연산을 수행하는가
- 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
- 단순성 : 얼마나 단순한가
- 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가
나. 정확성 평가
- 수학적 : 알고리즘이 예상대로 수행되는지 수학적 증명 수행
- 실용적 : 테스트 데이터에 의한 디버깅을 통해 정확성 평가
다. 효율성 평가
구분 |
설명 |
시간 복잡도 (Time Complexity) |
입력크기의 값에 대하여, 단위연산을 몇 번 수행 하는지를 계산함으로써, 알고리즘의 수행시간 평가 프로그램의 컴파일 시간과 실행 시간의 합 3가지 점근적 표현법 O - 빅오 Ω - 오메가 Θ - 세타 |
공간 복잡도 (Space Complexity) |
알고리즘 수행에 필요한 메모리의 양을 평가 필요한 고정 공간과 가변 공간의 합 |
VI. 알고리즘의 점근 표기법과 복잡도
가. 점근 표기법
- 알고리즘의 수행 시간을 대략적으로 나타내는 방법 (1) Big O : 어떤 최악의 상황에서도 성능을 보장 (2) Big Omega : 아무리 좋은 케이스라도 그 성능 이상을 낼 수 없음 (3) Big Theta : 알고리즘이 처리해야 하는 수행 시간의 상한과 하한을 동시에 표현 |
|
나. 복잡도
구분 |
내용 |
시간 복잡도 |
문제를 해결하는 시간과 입력의 함수 관계 |
공간 복잡도 |
문제를 해결하기 위해 필요한 저장 공간과 함수 관계 |