![]()
🟩 계수 정렬을 일반화한 것으로 간주 가능 특히 값의 범위가 골고루 퍼져있을 때 유용 EX) 0.0~1.0 사이의 소수점 수를 가진 큰 집합을 정렬 👉 숫자들이 골고루 분산되어 있다면 인덱스 지정이 어렵기 때문에 계수정렬은 적용이 어렵고, 버킷정렬이 유용 🟩 방법 1. 주어진 데이터들의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만든다. 2. 각 데이터를 해당하는 버킷에 넣고 3. 각 버킷을 삽입 정렬과 같은 안정적인 정렬을 수행한 후 4. 버킷 순서대로 각 데이터를 나열하는 정렬 방식 🟩 특징 안정 정렬 (중복된 값의 경우 입력 순서를 무작위로 뒤섞은 상태에서 정렬하는 것) 제자리 정렬 알고리즘 X 🟩 시간복잡도 O(n) 하지만 한 버킷에 입력 키값들이 몰린 경우에는 버킷에 속하는 키들을 정렬하는데..
![]()
🟩 자리수를 비교하며 정렬을 진행하는 알고리즘 🟩 종류 1. LSD (Least Significant Digit) 기수 정렬 가장 작은 자릿수부터 정렬 진행 (예 : 일의 자릿수부터) Right-to-Left 가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이 MSD에 비해 간결하다. 마지막 자릿수까지 검사를 마친 경우, 오름차순으로 정렬이 완료됨 2. MSD (Most Significant Digit) 기수 정렬 가장 큰 자릿수부터 정렬 진행 Left-to-Right LSD와 비교했을 때, 정렬 상태 확인 등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다. 🟩 특징 및 장단점 정렬 순서상 앞과 뒤의 판단을 위한 비교 연산을 하지 않음 정렬 대상의 모..
🌟 비교 기반의 정렬 알고리즘 기본 성능 O(n^2) : 선택/버블/삽입/셸 정렬 향상된 평균 성능 O(nlogn) : 퀵/합병/힙 정렬 👉 비교 기반 정렬 알고리즘의 하한 🟩 이미 얻어진 데이터 분포 정보를 활용하는 정렬 알고리즘 계수/기수/버킷 정렬 👉 선형 시간 O(n) 가능 🟩 데이터 값을 직접 비교하지 않고, 단순하게 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬하는 알고리즘 기존의 정렬 알고리즘들은 위치를 바꾸며 정렬했지만, 계수 정렬은 크기를 기준으로 개수만 세면 되기 때문에 위치를 변경할 필요 없음 🟩 특징 및 장단점 값 비교가 일어나지 않아 속도가 빠르다. 하지만, 개수를 저장하는 배열을 사용해야 하기 때문에 추가 공간 필요 👉 정렬해야할 수의 범위가 작을 때에만 유리하다. EX..
![]()
🟩 '힙' 자료구조의 장점을 활용한 정렬 최대힙 트리나 최소힙 트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서는 최대힙 (루트가 가장 큼)을 구성하고 오름차순 정렬을 위해서는 최소힙 (루트가 가장 작음)을 구성한다. 🟩 과정 1. n개의 노드에 대한 완전 이진 트리 구성 2. 최대힙 구성 3. 가장 큰 수(루트에 위치)를 가장 끝의 노드와 교환 4. 2와 3을 반복 🟩 시간복잡도 힙과 동일하게 O(nlogn) 최대힙으로 만드는 과정 O(logn), n개의 원소를 다 정렬할 때까지 반복 하므로 🟩 특징 제자리 정렬 (추가적인 공간이 필요하지 않음) 👉 메모리 측면에서 몹시 효율적 cf. 합병정렬 항상 시간복잡도 O(nlogn)을 보장 하지만 단순히 속도만 가지고 비교하면 퀵 정렬이 평균적으로 빠르기..
![]()
🟩 자연의 나무처럼 가지가 분기하여 뻗어 나가는 구조 트리를 구성하는 원을 '노드(마디)' 트리 맨 위에 있는 노드는 '루트(뿌리)' 위에 있는지 아래에 있는지에 따라 부모 노드와 자식 노드로 구분, 같은 부모를 가지면 형제 노드 부모와 자식 노드 형태로 묶인 트리의 일부분을 서브 트리 트리의 맨 아래에 있고, 별도의 자식 노드가 없으면 리프(잎) 노드 노드의 레벨 : 루트로부터 그 노드까지 이어진 선(경로)의 길 노드의 길이 : 어떤 노드에서 다른 노드로 이동할 때, 거치는 노드의 개수 노드의 경로 : 어떤 노드에서 다른 노드로 이동할 때, 거치는 노드의 순서 노드의 크기 : 자기 자신과 자식 노드를 포함한 노드의 개수 노드의 차수 : 노드별 자식 노드의 개수 트리의 높이 : 트리 노드로부터 리프 노드..
![]()
🟩 연결되어 있는 원소 간의 관계를 표현한 자료구조 몇 개의 정점(Vertext)이 간선(Edge)으로 연결된 것 그래프 G = (V,E) 🟩 그래프 탐색 특정 정점에서 출발해 간선을 통해 이동해가며 대상 정점을 찾는 것 탐색 순서에 따라 깊이 우선 탐색, 너비 우선 탐색 🟩 그래프 용어 인접 : 두 정점이 연결되어 있을 때 cf. 정점들은 부속되어 있다 한다. 차수 : 정점에 부속되어 있는 간선의 수 경로 : 정점 a에서 b까지 간선으로 연결된 정점을 순서대로 나열한 리스트 단순 경로 : 모두 다른 정점으로 구성된 경로 👉 진입 차수, 진출 차 경로 길이 : 경로를 구성하는 간선의 수 사이클 : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로 🟩 구현 방법 인접 행렬, 인접 리스트 🌟 무..
![]()
🟩 방법 1. 하나의 리스트를 두 개의 균등한 크기로 분할 (부분 리스트의 사이즈가 1이 될 때까지) 2. 분할된 리스트들을 정렬한 후 3. 정렬된 부분 리스트들을 하나로 합치면서 전체가 정렬된 리스트가 되게 하는 방법 🟩 분할정복 알고리즘 하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘 🟩 시간 복잡도 O(nlogn) 데이터를 절반씩 분할하면서 줄여나가기 때문에 logn만큼의 분할이 이뤄지게 되고 각 분할에서 n번의 값 비교를 통해 위치를 찾아가기 때문에 O(nlogn) cf. 퀵 정렬은 피봇을 어떻게 선택하느냐에 따라 최악의 시간 복잡도가 O(n^2)가 되지만, 합병정렬은 항상 리스트를 절반으로 나누기 때문에 O(nlogn..
![]()
🟩피벗 : 보통 주어진 배열의 첫 번째 데이터로 지정 기준이 되는 수(pivot)를 수열 안에서 임의로 하나 선택하여 피봇 이외의 수를 피봇보다 작은 수, 큰 수로 나눈다. 작은 수 < 피봇 1) { // ①피벗을 기준으로 두 부분배열로 분할 // pivot은 제자리를 잡은 피벗의 위치(인덱스)를 표시 pivot = Partition(A[0..n-1], n); // ②왼쪽 부분배열에 대한 퀵 정렬의 순환 호출 QuickSort(A[0..pivot-1], pivot); // ③오른쪽 부분배열에 대한 퀵 정렬의 순환 호출 QuickSort(A[pivot+1..n-1], n-pivot-1); } } int Partition (A[ ], n){ Left = 1; Right = n-1; while (Left < ..
![]()
🟩 삽입 정렬의 장점은 살리고, 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘 삽입 정렬의 보완 삽입 정렬은 초기 리스트가 "거의 보완"되어 있을 경우 효율적 정렬되지 않은상태의 배열에 대해 단순하게 삽입정렬을 적용하는 것이 아니라 '4-정렬', '2-정렬'처럼 조금이라도 정렬이 된 상태에 가까운 배열로 만든 다음 마지막 삽입정렬을 하는 것 정렬해야 하는 횟수는 늘지만, 전체적으로 요소 이동 횟수가 줄어들어 효율적인 정렬을 할 수 있다. 🟩 순서 1. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입 정렬 수행 2. 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄인다 3. 위의 과정을 그룹의 개수가 1이 될 때까지 반복한다. 🟩 나누는 간격 k 간격 k의 초깃값 : (데이터의 갯수) / ..
![]()
🟩 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입 왼쪽에는 정렬이 끝난 수가 오게되고, 오른쪽에는 아직 확인하지 않은 숫자가 남게 되는데, 오른쪽 미탐색 영역에서 숫자를 하나 꺼내어 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식 이미 정렬이 되어있다면 필요없이 종료한다. InsertionSort(A[ ], n) { for (i=1; i 0 && A..
![]()
🟩 왼쪽에서 오른쪽 방향으로 인접한 두 개의 숫자를 비교해 교환하여 정렬 오름차순으로 정렬될 때까지 다시 돌아와 반복한다. 반대 방향으로도 가능 BubbleSort(A[ ], n) { for (i=0; i A[j+1]) // ‘왼쪽 데이터 >오른쪽 데이터’이면 A[j]와 A[j+1]의 자리바꿈; return (A); } 🟩 시간 복잡도 for문 i (외부 반복문) : 0 ~ (n-2) 👉 (n-1)회 for문 j (내부 반복문) : 동일 👉 (n-1)회 총 비교 횟수 = O(n^2) 🟩 성능 선택 정렬에 비해 데이터 교환이 많이 발생. 선택 정렬보다 비효..
![]()
🟩 입력 배열에서 가장 작은 값부터 순서대로 '선택'해서 나열하는 방식 수열 중에서 최솟값을 찾아 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복한다. 최솟값을 찾을 때는 선형 탐색을 사용 SelectionSort(A[ ], n) { for (i=0; i A[j]) min = j; A[i]와 A[min]의 자리바꿈; // ②최소값과 A[i]의 위치 교환 } return (A); } 🟩 시간복잡도 총 비교횟수 = (n-1) + (n-2) + ... + 1 = n(n-1)/2 👉 O(n^2) 루프i 0 1 2 ... n-2 루프j의 비교횟수 n..
