삽입정렬 삽입정렬 이론 확실하게 짚고 넘어가야할 중요한 알고리즘이다. 삽입정렬의 시간복잡도는 최선일 경우 O(N) , 최악일 경우 O(N*N)이 된다. 앞서 살펴봤던 이중 반복문으로 모든 곳을 탐색하여 최선과 최악일 경우의 시간 복잡도가 모두 O(N*N)이였던 선택정렬과 버블정렬에 비하면 낫긴 하지만 삽입정렬 역시 비효율적인 정렬 알고리즘에 속한다. 대략적인 코드를 작성해보면 int i, j; for(i=1; i=0; j--) { if(a[j] > tmp) a[j+1] = a[j]; else break; } a[j+1] = tmp; } 이렇게 나타낼 수 있다. i가 1부터 돌고 j는 i-1에서 j=0까지 감소하는 for문을 돈다. 왼쪽의 수가 크면 오른쪽 수에 왼쪽 수를 넣고 그렇지 않은 경우(break..
선택정렬 선택정렬 이론 : 이렇게 정렬하는 알고리즘이다. for문 i 안에서 for문 j가 탐색을 하며 가장 작은 수를 찾아 현재 위치랑 교환(swap)하는 것을 반복한다. 이중 반복문이고, 끝까지 탐색을 해야 하기 때문에 O(N*N)인 시간복잡도를 가지고 있다. 비효율적인 정렬이라고 할 수 있다. O(NlogN)의 시간복잡도를 가진 sort함수를 나두고 이걸 사용할 필요가 있나 싶지만 알아두기로 하자 코드는 이런 느낌으로 작성된다. for(i= ..) { idx = i; for(j=i+1; j m; v.push_back(m); } for(i=0; i
그리디 알고리즘에 대해 그리디 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법으로 소개됩니다. 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', 가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됩니다. 지금 살펴볼 거스름돈 문제는 그리디 알고리즘을 대표하는 문제입니다. 그리디 알고리즘 문제 풀이 1번 - 거스름돈 문제 : 당신은 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정..
