하기 내용은 이재규 교수님의 "C++로 배우는 자료구조와 알고리즘"을 보고 공부한 내용입니다.
문제 시 삭제하도록 하겠습니다.
알고리즘(Algorithm)의 정의
- 주어진 문제를 해결하기 위한 방법
- 어떻게 할 것인가 해결적 측면.
자료구조 (Data Structure)
- 알고리즘의 객체.
- 배열, 스택, 큐, 트리 ...
알고리즘 선택
- 하나의 문제에 대해 여러 알고리즘 존재.
· 예를 들어, 서울에서 부산을 가능 방법은 여러 가지가 있다. (버스, 기차, 자가용 등..)
- 절대적인 최상의 알고리즘은 없다.
· 주어진 환경에 따라 알고리즘의 효율성은 달라진다.
· 예를 들어, 출퇴근 시간에는 자동차보다 지하철이 더 빠르게 갈 수 있다. 그러나 차가 없는 저녁 시간에는 자동차가 더 빠를 수 있다.
- 속도와 자원의 상관관계
· 속도가 빠른 알고리즘은 자원을 많이 차지한다.
· 메모리가 별로 없는 임베디드 시스템에서는 자원을 적게 차지하는 알고리즘을 선택하는 것이 좋고,
PC와 같은 충분한 메모리와 고성능 CPU를 가지고 있다면 자원을 많이 차지하더라도 속도에 효율성이 있는 알고리즘을 선택하는 것이 좋다.
- 단순한 알고리즘이 좋다.
· 지나치게 속도만을 생각하는 것은 좋지 않다.
· 알고리즘 부분의 사용빈도에 따라 선택하는 것이 좋다.
알고리즘의 유형
- 1 (상수)
· 입력자료수와 관계없이 일정한 실행시간 (데이터가 100개이든 1000개이든 실행 시간은 동일)
· 해쉬 검색 알고리즘 등
- log N
· Divide & Conquer 방법 사용 시 (문제를 분할하고 그 분할된 문제를 해결하는 방법)
· 이진검색, 이진트리검색 등
- N
· Scan 방법 사용 시 (자료가 100개 들어오면 100초 걸린다면 1000개 일때는 1000초 걸린다.)
· 선형검색 등 (데이터베이스에서 검색하는 것이 이런 유형)
- N log N
· Divide & Conquer & Merge 방법 사용 시 (문제를 분할하고 정복하고 다시 합치는데 사용하는 방법)
· 병합정렬 등
- N²
· 이중루프
· 삽입정렬, 선택정렬 등
- N³
· 삼중루프
하기 그래프는 각 유형 별 결과 그래프이다.
자료 수가 적을 때는 차이가 나지 않지만 자료 수가 늘어남에 따라 실행 결과의 격차는 커진다.
그러므로 적절한 알고리즘을 찾는 것은 매우 중요하다.
<이재규 교수님 강의 자료 첨부>