'algorithm' 태그의 글 목록

본문 바로가기

알고리즘 [Algorithm] - 계수 정렬 Counting Sort (7) (C, Python) 계수 정렬 이번에는 계수 정렬에 대해 알아보자. 계수 정렬이란 단순하게 '크기를 기준으로 세는 알고리즘'이다. 하지만 계수 정렬은 '범위조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘이다. 지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬을 배웠는데 지금 까지 배운 정렬 중 가장 빠른 정렬방법을 고르라면 시간 복잡도 O(N*log N)을 가지는 퀵 정렬, 병합 정렬, 힙 정렬 중 하나를 고를 것이다. 하지만 이보다 더 빠르게 정렬해야 한다면 어떻게 해야될까? 계수 정렬은 범위가 주어져있다면 시간복잡도 O(N)의 속도로 정렬을 수행한다. 크기를 기준으로 갯수를 세고, 갯수만큼 출력해주면 정렬이 이루어지기 때문에 굉장히 빠르다. 다음의 5 이하 자연수 데이터를 오름차순 정렬하세..

알고리즘 [Algorithm] - 힙 정렬 Heap Sort(6) (C,Python) 힙정렬 이번에는 힙 정렬에 대해 알아보자. 힙정렬이란 힙트리 구조를 이용하는 정렬방법이다. 이를 이해하기 위해선 먼저 힙(Heap)구조를 알아야하고, 힙을 알기 이전에는 이진 트리(Binary Tree)에 대해 알아야 한다. 이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로, 자식 노드를 각각 왼쪽자식 노트와 오른쪽 자식 노드 라고 한다. (출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC) 완전 이진트리는 데이터가 루트(Root) 노드부터 시작해서 자식노드가 왼쪽 자식노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리이다. 즉 완전 이진트리는 이진트리의 노드가 중..

알고리즘 [Algorithm] - 병합 정렬 Merge Sort(5) (C,Python) 병합정렬 이번에는 병합 정렬에 대해 알아보자. 병합정렬도 퀵정렬과 마찬가지로 대표적인 '분할정복' 방법을 채택한 알고리즘이다. 따라서 결과적으로 퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가진다. 다만 퀵 정렬은 최악의 경우 O(N^2)의 시간복잡도를 가지지만, 병합정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N*logN)을 보장한다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 7 6 5 8 3 5 9 1 병합정렬은 하나의 큰 문제를 두개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택한다. 즉 기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬하는 것이다. 퀵 정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징이 있고, 때문에 단..

알고리즘 [Algorithm] - 퀵 정렬 (4) (C, Python) 퀵 정렬 이번에는 퀵 정렬에 대해 알아보자. 퀵 정렬이란 대표적인 '분할 정복'알고리즘으로 평균 속도가 O(N*logN)인 알고리즘이다. 이전에 배웠던 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 데이터의 갯수가 10만개가 넘어가면 사용하기 매우 어려운 알고리즘이다. 따라서 더욱 빠른 정렬 알고리즘이 필요하고 대표적인 알고리즘이 퀵 정렬 알고리즘이다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 퀵 정렬은 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 정렬한다. 다시 말해 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 예시를 통해 보자. 퀵 정렬에는 기준 값이 사용된다. 이를 피벗(Pivot)이라고도 하..

이전 1 2 다음

티스토리툴바