본문 바로가기

Thinking/Algorithm9

선택 (Select) 알고리즘 선택 (Select) 알고리즘 정렬되지 않은 리스트나 배열에서 가장 작은 k번째 수를 찾는 알고리즘이다. 간단한 방법은 최소 숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는 것이 있는데, 이러한 알고리즘은 O(nlogn)의 수행 시간이 걸린다. 이보다 효율적인 해결을 위하여 분할 정복 개념을 활용할 수 있다. 일부 과정이 퀵 정렬과 비슷하여 Quick-Select 알고리즘이라고도 한다. "평균"선형 시간 안에 k번째 작은 수를 찾을 수 있다. 부분문제의 크기가 일정하지 않은 크기가 감소하는 형태의 분할 정복 알고리즘이다. 만일 피봇이 입력을 너무 한 쪽으로 치우치게 분할하면, 알고리즘의 수행시간이 길어진다. 두 그룹 중 하나의 크기가 입력 크기의 3/4과 같거나 그보다 크면 bad 분할이고, 그 반.. 2023. 10. 2.

Sort 계수 정렬 (Counting Sort) 알고리즘 [Sort] 계수 정렬 (Counting Sort) 알고리즘 계수 정렬은 데이터의 키에 따라 객체를 수집 정렬 하는 정렬 알고리즘이다.비교 연산을 하지 않는 정렬 알고리즘이다.키의 다양성이 데이터의 수보다 상당히 크지 않은 상황에서 유용하다.O(n)의 시간 복잡도를 가진다.데이터 중 가장 작은 값과 가장 큰 값을 기준으로 하는 공간 크기가 필요하다. (1~10의 경우 10개의 공간이 필요하지만 1과 10000이 들어 있는 데이터에서는 10000의 배열 크기가 필요하다.)특정한 값이 몇번 등장했는지에 따라 정렬을 수행한다.계수를 다 카운팅 한 후에 앞에서 부터 차례대로 배열에 넣는다. 정렬 과정10000개의 공간에 1 ~ 10까지의 정수가 무작위로 들어가 있다고 가정한다.최솟값 최댓값을 알고 있을 때, 각.. 2023. 10. 1.

Sort 기수 정렬 (Radix Sort) 알고리즘 [Sort] 기수 정렬 (Radix Sort) 알고리즘 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.공간을 나눠 알맞은 데이터를 놓는 방법이 버킷 정렬 (Bucket Sort)과 비슷하다.* 버킷 소트(bucket sort)는 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다. 특징데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식이다.비교연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘이다. 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능하다.전체 데이터의 기수를 위한 버킷이라는 추가적인 메모리 공간이 필요하다. 10 진수인 데이터들을 정렬하기 위해서는 0~9 를 저장할 10.. 2023. 10. 1.

Sort 힙 정렬(Heap Sort) 알고리즘 [Sort] 힙 정렬(Heap Sort) 알고리즘 힙(Heap)이란?힙이란 완전 이진 트리의 형태로 만들어진 자료구조이다.돌 더미, 장작 더미 처럼 위로 갈수록 노드의 수가 줄어드는 모습을 하고 있다. 완전 이진 트리(Complete Binary Tree)란?완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 가지고 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있는 자료구조이다. 최하단 레벨의 노드는 좌측 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 힙 정렬(Heap Sort)이란 ?힙 정렬(Heap sort)이란 최대 힙(부모 노드 > 자식 노드) 트리나 최소 힙(부모 노드 트리를 구성해 정렬을 하는 방법이다.힙(.. 2023. 9. 19.

Sort 퀵 정렬(Quick Sort) 알고리즘 [Sort] 퀵 정렬(Quick Sort) 알고리즘 퀵 정렬(Quick Sort) 알고리즘이란?찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 정렬 알고리즘이다다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하며, 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.N개의 데이터를 정렬할 때, 최악의 경우에는 O(N^2)번의 비교를 수행하고, 평균적으로 O(N log N)번의 비교를 수행한다.매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다.퀵 정렬은 정렬을 위해 평균적으로 O(log N)만큼의 memory를 필요로한다. 최악의 경우 O(n)의 공간복잡도를 보인다.퀵 정렬.. 2023. 9. 14.

Sort 병합 정렬(Merge Sort) 알고리즘 [Sort] 병합 정렬(Merge Sort) 알고리즘 병합정렬이란?병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 방식을 이용한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 병합하는 과정에서 재귀적으로 반복하며 풀어내는 것이 일반적이다.'존 폰 노이만(John von Neumann)'이 1945년에 개발데이터 분포도에 영향을 많이 받지 않아 시간복잡도가 O(NlogN)인 안정적인 정렬 방식에 속한다.두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요하다. 따라서 공간 복잡도는 O(N) 이다.다른 정렬 방법은 연결리스트에서 각 데이터.. 2023. 9. 13.

Sort 삽입 정렬(Insertion Sort) 알고리즘 [Sort] 삽입 정렬(Insertion Sort) 알고리즘 삽입 정렬은 두 번째 원소부터 시작하여 앞의 원소들을 비교하고, 삽입할 위치를 정한다. 삽입할 위치가 정해졌으면 대상 위치 부터 자신의 바로 앞 위치까지 있는 원소들을 한 칸씩 뒤로 옮겨 들어갈 자리를 만든 후 삽입해 정렬하는 알고리즘이다. 가나다 순으로 되어있는 책들 사이에 끼워 넣거나 순서대로 정렬할 필요가 있는 카드를 생각하면 이해가 쉽다. 아래는 삽입 정렬을 그림으로 표현한 것이다.1회차 - 2번째 원소 3을 Key로 두고 앞에 있는 5와 비교하고 자리를 바꾼다.2회차 - 3번째 원소 1을 Key로 설정하고 앞에있는 5와 3을 비교하고 뒤로 한 칸씩 밀어낸다. - 비어있는 첫 번째 원소 자리에 1을 삽입한다.3회차 - 4번.. 2023. 9. 3.

Sort 버블 정렬(Bubble Sort) 알고리즘 [Sort] 버블 정렬(Bubble Sort) 알고리즘버블 정렬(Bubble Sort)이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 배열 A[N]이 있을 경우 배열의 원소 A[n]과 ~ A[n+1]을 순차적으로 비교하며 가장 큰 수를 맨 뒤로 이동하는 방법이다.가장 큰 자료가 맨 뒤로 이동하므로 맨 끝 원소는 검사 및 정렬에서 제외된다. 반복횟수마다 검사하는 원소가 줄어드는 이유이다. 5개의 원소 안에 {5, 3, 1, 4, 2} 의 원소가 들어가 있을 경우 버블 정렬은 아래 그림과 같다.1회차 - 5와 3을 비교 후 자리를 바꾼다. - 5와 1을 비교 후 자리를 바꾼다. - 5와 4를 비교 후 자리를 바꾼다. - 5와 2를 비교 후 자리를 바꾼다. - 마지막 자리수는 이.. 2023. 9. 3.

Sort 선택 정렬(Selection Sort) 알고리즘 [Sort] 선택 정렬(Selection Sort) 알고리즘 선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나다.배열[A ··· n] 에서 가장 큰 원소를 마지막 원소와 자리를 바꾸거나, 가장 작은 원소를 제일 앞 원소와 자리를 바꾸는 것이다.자리 바꾸기가 완료되면 그 원소가 있는 자리는 신경쓰지 않아도 된다. 배열 { 3, 5, 1, 4, 2} 가 있을 때, 뒤에서 부터 오름차순 정렬하는 모습은 다음과 같다.*보통 프로그래밍 언어에서 인덱스는 0번 부터 시작한다.{ 3, 5, 1, 4, 2} 중 가장 큰 수 '5'를 찾는다. ('5'는 인덱스 1번에 있다.){ 3, 2, 1, 4, 5} '5'를 가장 뒤에 있는 '2'와 자리를 바꾼다. (1번 인덱스와 4번 인덱스 자리 바꿈){ 3, 2, 1, 4, 5.. 2023. 9. 2.

이전 1 다음

티스토리툴바