|
http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Lectures&no=733 [복사]
알고리즘이란?
주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합이다.
알고리즘은 우선 주어진 문제가 있고 이 문제를 해결하기 위한 순서적인 동작들이 있다.
알고리즘을 한글로 표현하면 방법이라고 하는 것이 가장 맞을 것이다.
알고리즘을 방법이라고 생각할 때 알고리즘은 행위적 측면을 부여받는다.
그렇다면 알고리즘과 자료 구조의 관계는 어떠한가?
그것은 마치 계란의 노른자와 흰자와도 같다. 계란은 껍질 속에 한정된 양만의 노른자와 흰자가 있을 수 있다.그래서 만일 노른자가 커진다면 흰자는 줄어야 하고 ,노른자가 작아진다면 흰자가 커져야 하는 것이다. 마찬가지로 자료 구조가 잘 조직화되어 복잡한 구조라면 알고리즘은 간단하게 할수 있고, 자료 구조가 단순한 구조이면 알고리즘은 복잡해지는 것이다.
스택(stack)이나 큐(queue)와 같은 구조는 자료 구조이지만 행위적 특면을 부여받은 것이다.
예를 들어 스택은 연속된 자료의 공간일뿐 아니라, 그 자료를 취급하는 행위까지 정의 하고 있다. 스택은 팝(pop)동작과 푸시(push)동작을 자체적으로 포함해서 하나의 자료구조를 형성하고 있으며, 이러한 자료 구조를 입*출력이 제한된 자료 구조라고 하며 더 어려운 말로 추상적인 자료형 이라고 한다.이렇게 자료구조에 행위적 측면을 포함하고 있으면 알고리즘은 단순해 지는 것이다.그러나 자료구조가 단순하다면 알고리즘이 이 행위적 측면까지 다 포함해야 하기 때문에 알고리즘이 복잡해 지는 것이다.
어떤 알고리즘을 선택할 것이가?
하나의 문제에 대해 해결 방법은 여러가지일 수 있다. 예를 들어 정렬을 위한 알고리즈은 선택, 거품, 삽입, 퀵, 기수, 병합 등등 수많은 종류의 알고리즘들이 개발되어 있다.
여기서 어떤 알고리즘을 선택해야 할 것인가?
먼저 알아 두어야 할 것은 절대적으로 최상의 알고리즘은 없다는 것이다. 즉 어떤 상황에서도 가장 잘 맞는 알고리즘은 존재하지 않고, 항상 주어진 문제의 상황과 제한점이 주어질 때에만 최상의 알고리즘을 선택할 수 있다는 것이다.
일반적으로 정렬의 가장 좋은 알고리즘은 퀵 정렬이라고 한다. 대부분의 경우에 있어 퀵 정렬이 가장 좋은 알고리즘이라고 판단할 수 있지만 항상은 아니다. 자료의 유동이 심한 경우에는 퀵 정렬 보다는 힙 정렬이나 삽입 정렬이 유효 할 수 있다.
-출처 C로 배우는 알고리즘- |
Hit : 8887 Date : 2007/05/30 11:34
|
1619, 
1/81 
