자료구조(알고리즘) 서문

컴퓨터이야기/알고리즘 2005/12/26 20:08
1. 문제 해결 방법은 여러가지일 수 있습니다.
선택(selection), 거품(bubble), 삽입(insertion), 퀵(quick), 기수(radix), 병합(merge) 등등 수많은 종류의 알고리즘들이 이미 개발되어 있죠.
하지만 중요한건 절대적 최상의 알고리즘은 없다는 것입니다.
주어진 문제의 상황과 제한점 안에서 최상의 알고리즘이 선택될 수 있는 것이죠.

일반적으로 정렬의 가장 좋은 알고리즘은 퀵정렬이라고 합니다. 하지만 데이터의 유동이 심한 경우 퀵정렬보다는 힙(heap) 정렬이나 삽입(insertion)정렬이 유효할 수 있습니다. 또한 퀵정렬은 불안정하므로 다중 인덱스를 사용하는 경우 병합(merge)정렬이나 삽입(insertion)정렬을 사용해야 합니다.

2. 알고리즘의 속도와 메모리 소요의 관계에 대한 이해가 필요합니다.
퀵정렬은 빠른 정렬방법이지만 재귀호출이나 스택에 필요한 정보를 저장하는 방식으로 자료 저장에 소요되는 메모리 외에 부가적인 메모리가 필요하게 됩니다. 속도를 위해서 메모리를 희생하는 것인데, 10만건, 100만건 대용량 자료를 처리해보시면 알겠지만 메모리 풀나서 서버 죽는걸 자주 보실수 있을겁니다.-_-;;

3. 속도보다는 단순함을 지향해야 합니다.
이게 정신건강에 좋습니다.

4. 최선의 경우와 최악의 경우를 고려합니다.
최악이나 최선이나 무난한 알고리즘을 선택하는 것이 일반적으로 좋답니다.

5. 유형분석
입력되는 자료 개수 N에 대해 수행시간을 함수관계로 나타내면 성능을 구할 수 있습니다. 그리고 그 유형은 다음과 같습니다. logN형이 제일 좋으나 일반적으로는 NㆍlogN 유형에 상수가 곱해지고 더해지는 경우가 많습니다.
▶ 1
입력자료 수에 관계없이 일정시간동안 실행됨. (good)

▶ logN
입력자료 수 N이 증가함에 따라 실행시간이 조금씩 늘어남.
커다른 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때.(good)

▶ N
입력자료 수에 따라 선형적인 실행시간 증가.(good)

▶ NㆍlogN
N이 2배로 늘어나면 실행시간은 2배보다 약간 더 늘어남
큰문제를 작게 쪼갠 뒤, 다시 합치는 경우에 나타남.(good)

▶ N²
N이 2배가 되면 실행시간이 4배(bad)

▶ N³
N이 2배가 되면 실행시간이 8배(bad)

▶ 2ⁿ
이건 아주 안좋은 대략 난감한 상황(bad)
Posted by 백구씨쥔장
트랙백 0개, 댓글 0개가 달렸습니다