알고리즘/정렬13 [알고리즘-10] 계수 정렬(Counting Sort) 안녕하세요 기린입니다 :) 지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 알고리즘에 대해 알아보았는데요 여기서 정렬 속도가 가장 빠른 알고리즘은 퀵 정렬, 병합 정렬, 힙 정렬 등이 시간복잡도 O(N * logN)으로 가장 빠르다고 할 수 있습니다. 하지만 이 보다 더 빠르게 정렬해야 한다면 어떻게 해야할까요? 다음의 5이하 자연수 데이터들을 오름차순 정렬하세요. 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1 이번 예시의 데이터의 갯수는 30개입니다. 다만 모든 데이터가 1부터 5사이에 속한다는 특징이 있습니다. 이처럼 '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있습니다. 시간 복잡도가 무려 O(.. 2022. 4. 11. [알고리즘-9] 힙 정렬 (Heap Sort) 안녕하세요 기린입니다 :) 오늘은 힙 정렬(Heap Sort)에 대해 알아보겠습니다. 먼저 힙 정렬은 병합 정렬과 퀵 정렬만큼 정렬속도가 빠른 알고리즘입니다. 그리고 실제 고급 프로그래밍 기법으로 자주 사용하기 때문에 반드시 알고 넘어가야 할 정렬 알고리즘이지요. 힙 정렬은 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법입니다. 힙 트리 구조를 이해하기위해 먼저 힙과 트리 구조에 대해 알아야 합니다. 가장 먼저 트리 구조 중 이진 트리(Binary Tree)에 대해서 알고있을 필요가 있습니다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드(Node)에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조를 말합니다. 이 때 트리구조에 맞게 부모 노드에서 자식 노드로 가지.. 2022. 4. 5. [알고리즘-6] 병합 정렬 (Merge Sort) 안녕하세요 기린입니다 :) 지난 시간까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬 알고리즘을 공부했습니다. 이번에는 병합 정렬 (Merge Sort)에 대해 알아보겠습니다 ! 병합 정렬도 퀵 정렬 알고리즘과 같이 '분할 정복' 방법을 채택한 알고리즘 인데요 결론은 시간 복잡도가 O(N * logN)이라는 거죠 :] 다만 퀵 정렬 알고리즘은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N ^ 2)의 시간 복잡도를 가지지만 병학 정렬 알고리즘은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)의 시간 복잡도를 보장합니다. 퀵 정렬을 이해하셨다면 이 병합 정렬은 쉽게 이해하실 수 있을겁니다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 8 2.. 2022. 3. 25. [알고리즘-4] 퀵 정렬 안녕하세요 기린입니다 :) 지난 시간까지 다루었던 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘 모두 시간 복잡도 O(N^2)를 가지는 알고리즘 이었는데요. 이러한 알고리즘 들은 데이터의 갯수가 10만 개만 넘어가도 사용하기가 매우 어려운 알고리즘입니다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 필요하겠죠 ? 자 대표적으로 빠른 알고리즘인 퀵 정렬에 대해 알아보겠습니다. 퀵 정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN) 입니다. 예시를 통해 바로 확인해보시죠 :] 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 방법으로 빠르게 정렬하는데요, 더 쉽게 말해 특정한 값을 .. 2022. 3. 15. [알고리즘-3] 삽입정렬 안녕하세요 기린입니다 :) 지난 시간까지 선택 정렬과 버블 정렬에 대해 알아보았습니다. 앞에서 다룬 정렬 알고리즘은 모두 시간 복잡도 모두 O(N^2)을 가진다는 점에서 비효율적이라 할 수 있죠. 이번시간에 다룰 삽입 정렬은 어떨지 한번 보겠습니다. 문제는 지난 시간과 동일합니다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 삽입 정렬은 위 문제를 풀 때 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결합니다. 자 여기서 다른 알고리즘들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 '필요할 때만' 위치를 바꾸게 되는데요 먼저, 소스 코드를 살펴 보겠습니다. #include int main(void) { int i, j, temp; int ar.. 2022. 3. 10. [알고리즘-2] 버블정렬 안녕하세요 기린입니다 :) 오늘은 지난 시간에 이어서 버블 정렬에 대해 알아볼텐데요 자 버블정렬이란 일련의 숫자들을 오름차순으로 정렬하는것 인데요 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 버블정렬 또한 선택정렬과 같이 몹시 직관적인 해결 방법입니다 바로 가까이에 있는 두 숫자끼리 비교해서 더 작은 숫자를 앞으로 보내주는 것을 반복 하는 겁니다 다시 말해 버블정렬이란 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법인데요 정렬 알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘입니다 #include int main(void) { int i, j, temp; int array[10] = {1, 10, 5, 8, 7, .. 2022. 3. 7. 이전 1 2 3 다음
