์ถ์ฒ : https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4
ํน์ ํ ๊ธฐ์ค์ ๋ฐ๋ผ ์์๋๋ก ๋์ด
ํ๋ ๊ฒ์ ๋งํฉ๋๋ค.๊ฐ์ฅ ์์ ๋ฐ์ดํฐ
๋ฅผ ์ ํํด ๋งจ ์์ ์๋ ๋ฐ์ดํฐ
์ ๋ฐ๊พธ๋ ๊ฒ์ ๋ฐ๋ณตํ๋ค.
python
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # ๊ฐ์ฅ ์์ ์์์ ์ธ๋ฑ์ค for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # ์ค์ํ print(array)
Java
import java.util.*; public class Main { public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; for (int i = 0; i < n; i++) { int min_index = i; // ๊ฐ์ฅ ์์ ์์์ ์ธ๋ฑ์ค for (int j = i + 1; j < n; j++) { if (arr[min_index] > arr[j]) { min_index = j; } } // ์ค์ํ int temp = arr[i]; arr[i] = arr[min_index]; arr[min_index] = temp; } for(int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } } }
๐คฏ ์๊ฐ ๋ณต์ก๋ ๋ถ์
โ
์ ํ ์ ๋ ฌ์ N๋ฒ ๋งํผ ๊ฐ์ฅ ์์ ์
๋ฅผ ์ฐพ์์ ๋งจ ์์ผ๋ก ๋ณด๋ด์ผ ํ๋ค. ๊ตฌํ ๋ฐฉ์์ ๋ฐ๋ผ์ ์ฌ์ํ ์ค์ฐจ๋ ์์ ์ ์์ง๋ง, ์ ์ฒด ์ฐ์ฐ ํ์๋ ์๋๊ณผ ๊ฐ๋ค.
N + (N - 1) + (N - 2) + ... + 2
์ด๋ (N^2 + N - 2) / 2 ๋ก ํํํ ์ ์๋๋ฐ, ๋น
์ค ํ๊ธฐ๋ฒ์ ๋ฐ๋ผ์ O(N^2)
์ด๋ผ๊ณ ์์ฑํ๋ค.
์ฒ๋ฆฌ๋์ง ์์ ๋ฐ์ดํฐ
๋ฅผ ํ๋์ฉ ๊ณจ๋ผ ์ ์ ํ ์์น์ ์ฝ์
. ์ ํ ์ ๋ ฌ์ ๋นํด ๊ตฌํ ๋์ด๋๊ฐ ๋์ ํธ์ด์ง๋ง, ์ผ๋ฐ์ ์ผ๋ก ๋ ํจ์จ์ ์ผ๋ก ๋์ํ๋ค.
python
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] # ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค๊ณ ๊ฐ์ for i in range(1, len(array)): # 2๋ฒ์งธ ์์๋ถํฐ ์์ for j in range(i, 0, -1): # ์ธ๋ฑ์ค i๋ถํฐ 1๊น์ง 1์ฉ ๊ฐ์ํ๋ฉฐ ๋ฐ๋ณตํ๋ ๋ฌธ๋ฒ if array[j] < array[j - 1]: # ํ ์นธ์ฉ ์ผ์ชฝ์ผ๋ก ์ด๋ array[j], array[j - 1] = array[j - 1], array[j] else: # ์๊ธฐ๋ณด๋ค ์์ ๋ฐ์ดํฐ๋ฅผ ๋ง๋๋ฉด ๊ทธ ์์น์์ ๋ฉ์ถค (์ค์) break print(array)
Java
import java.util.*; public class Main { public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; for (int i = 1; i < n; i++) { // ์ธ๋ฑ์ค i๋ถํฐ 1๊น์ง ๊ฐ์ํ๋ฉฐ ๋ฐ๋ณตํ๋ ๋ฌธ๋ฒ for (int j = i; j > 0; j--) { // ํ ์นธ์ฉ ์ผ์ชฝ์ผ๋ก ์ด๋ if (arr[j] < arr[j - 1]) { // ์ค์ํ(Swap) int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } // ์๊ธฐ๋ณด๋ค ์์ ๋ฐ์ดํฐ๋ฅผ ๋ง๋๋ฉด ๊ทธ ์์น์์ ๋ฉ์ถค else break; } } for(int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } } }
๐คฏ ์๊ฐ ๋ณต์ก๋ ๋ถ์
โ
์ฝ์
์ ๋ ฌ์ ์๊ฐ ๋ณต์ก๋๋ O(N^2)
์ด๋ฉฐ, ์ ํ ์ ๋ ฌ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ฐ๋ณต๋ฌธ์ด ๋ ๋ฒ ์ค์ฒฉ๋์ด ์ฌ์ฉ๋๋ค.
โ
์ฝ์
์ ๋ ฌ์ ํ์ฌ ๋ฆฌ์คํธ์ ๋ฐ์ดํฐ๊ฐ ๊ฑฐ์ ์ ๋ ฌ๋์ด ์๋ ์ํ๋ผ๋ฉด ๋งค์ฐ ๋น ๋ฅด๊ฒ ๋์ํฉ๋๋ค.
โ
์ต์ ์ ๊ฒฝ์ฐ O(N)
์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋๋ค.
์ด๋ฏธ ์ ๋ ฌ๋์ด ์๋ ์ํ์์ ๋ค์ ์ฝ์ ์ ๋ ฌ์ ์ํํ๋ฉด โ
๊ธฐ์ค ๋ฐ์ดํฐ
๋ฅผ ์ค์ ํ๊ณ ๊ทธ ๊ธฐ์ค๋ณด๋ค ํฐ ๋ฐ์ดํฐ์ ์์ ๋ฐ์ดํฐ์ ์์น๋ฅผ ๋ฐ๊พธ๋ ๋ฐฉ๋ฒ์ด๋ค.๊ธฐ์ค ๋ฐ์ดํฐ(Pivot)
๋ก ์ค์ ํฉ๋๋ค.๐ค ํต ์ ๋ ฌ์ด ๋น ๋ฅธ ์ด์
์ด์์ ์ธ ๊ฒฝ์ฐ ๋ถํ ์ด ์ ๋ฐ์ฉ ์ผ์ด๋๋ค๋ฉด ์ ์ฒด ์ฐ์ฐ ํ์๋ก O(NlogN)
๋ฅผ ๊ธฐ๋ํ ์ ์๋ค.
python(์ผ๋ฐ)
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array, start, end): if start >= end: # ์์๊ฐ 1๊ฐ์ธ ๊ฒฝ์ฐ ์ข ๋ฃ return pivot = start # ํผ๋ฒ์ ์ฒซ ๋ฒ์งธ ์์ left = start + 1 right = end while(left <= right): # ํผ๋ฒ๋ณด๋ค ํฐ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์ ๋๊น์ง ๋ฐ๋ณต while(left <= end and array[left] <= array[pivot]): left += 1 # ํผ๋ฒ๋ณด๋ค ์์ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์ ๋๊น์ง ๋ฐ๋ณต while(right > start and array[right] >= array[pivot]): right -= 1 if(left > right): # ์๊ฐ๋ ธ๋ค๋ฉด ์์ ๋ฐ์ดํฐ์ ํผ๋ฒ์ ๊ต์ฒด array[right], array[pivot] = array[pivot], array[right] else: # ์๊ฐ๋ฆฌ์ง ์์๋ค๋ฉด ์์ ๋ฐ์ดํฐ์ ํฐ ๋ฐ์ดํฐ๋ฅผ ๊ต์ฒด array[left], array[right] = array[right], array[left] # ๋ถํ ์ดํ ์ผ์ชฝ ๋ถ๋ถ๊ณผ ์ค๋ฅธ์ชฝ ๋ถ๋ถ์์ ๊ฐ๊ฐ ์ ๋ ฌ ์ํ quick_sort(array, start, right - 1) quick_sort(array, right + 1, end) quick_sort(array, 0, len(array) - 1) print(array)
python(์์ฝ๋ฉ)
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array): # ๋ฆฌ์คํธ๊ฐ ํ๋ ์ดํ์ ์์๋ง์ ๋ด๊ณ ์๋ค๋ฉด ์ข ๋ฃ if len(array) <= 1: return array pivot = array[0] # ํผ๋ฒ์ ์ฒซ ๋ฒ์งธ ์์ tail = array[1:] # ํผ๋ฒ์ ์ ์ธํ ๋ฆฌ์คํธ left_side = [x for x in tail if x <= pivot] # ๋ถํ ๋ ์ผ์ชฝ ๋ถ๋ถ right_side = [x for x in tail if x > pivot] # ๋ถํ ๋ ์ค๋ฅธ์ชฝ ๋ถ๋ถ # ๋ถํ ์ดํ ์ผ์ชฝ ๋ถ๋ถ๊ณผ ์ค๋ฅธ์ชฝ ๋ถ๋ถ์์ ๊ฐ๊ฐ ์ ๋ ฌ์ ์ํํ๊ณ , ์ ์ฒด ๋ฆฌ์คํธ๋ฅผ ๋ฐํ return quick_sort(left_side) + [pivot] + quick_sort(right_side) print(quick_sort(array))
Java
import java.util.*; public class Main { public static void quickSort(int[] arr, int start, int end) { if (start >= end) return; // ์์๊ฐ 1๊ฐ์ธ ๊ฒฝ์ฐ ์ข ๋ฃ int pivot = start; // ํผ๋ฒ์ ์ฒซ ๋ฒ์งธ ์์ int left = start + 1; int right = end; while (left <= right) { // ํผ๋ฒ๋ณด๋ค ํฐ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์ ๋๊น์ง ๋ฐ๋ณต while (left <= end && arr[left] <= arr[pivot]) left++; // ํผ๋ฒ๋ณด๋ค ์์ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์ ๋๊น์ง ๋ฐ๋ณต while (right > start && arr[right] >= arr[pivot]) right--; // ์๊ฐ๋ ธ๋ค๋ฉด ์์ ๋ฐ์ดํฐ์ ํผ๋ฒ์ ๊ต์ฒด if (left > right) { int temp = arr[pivot]; arr[pivot] = arr[right]; arr[right] = temp; } // ์๊ฐ๋ฆฌ์ง ์์๋ค๋ฉด ์์ ๋ฐ์ดํฐ์ ํฐ ๋ฐ์ดํฐ๋ฅผ ๊ต์ฒด else { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } } // ๋ถํ ์ดํ ์ผ์ชฝ ๋ถ๋ถ๊ณผ ์ค๋ฅธ์ชฝ ๋ถ๋ถ์์ ๊ฐ๊ฐ ์ ๋ ฌ ์ํ quickSort(arr, start, right - 1); quickSort(arr, right + 1, end); } public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; quickSort(arr, 0, n - 1); for(int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } } }
๐คฏ ์๊ฐ ๋ณต์ก๋ ๋ถ์
โ
ํต ์ ๋ ฌ์ ํ๊ท ์ ๊ฒฝ์ฐ O(NlogN)
์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋๋ค.
์ฒซ ๋ฒ์งธ ์์๋ฅผ ํผ๋ฒ์ผ๋ก ์ผ์ ๋, ์ด๋ฏธ ์ ๋ ฌ๋ ๋ฐฐ์ด์ ๋ํด์ ํต ์ ๋ ฌ์ ์ํํ๋ฉด โ
๐๐ป ์ต์
์ ๊ฒฝ์ฐ(ํผ๋ฒ์ ์๋ชป ์ค์ ํ์์ ๋)์ด๊ธฐ ๋๋ฌธ์ O(N^2)
์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
์ ์ ํํ
๋ก ํํํ ์ ์์ ๋ ์ฌ์ฉ ๊ฐ๋ฅํฉ๋๋ค.๊ณต๊ฐ๋ณต์ก๋
๊ฐ ๋๋ค.N
, ๋ฐ์ดํฐ(์์) ์ค ์ต๋๊ฐ์ด K
์ผ ๋ ์ต์
์ ๊ฒฝ์ฐ์๋ ์ํ ์๊ฐ O(N + K)
๋ฅผ ๋ณด์ฅ
python
# ๋ชจ๋ ์์์ ๊ฐ์ด 0๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๋ค๊ณ ๊ฐ์ array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # ๋ชจ๋ ๋ฒ์๋ฅผ ํฌํจํ๋ ๋ฆฌ์คํธ ์ ์ธ (๋ชจ๋ ๊ฐ์ 0์ผ๋ก ์ด๊ธฐํ) count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # ๊ฐ ๋ฐ์ดํฐ์ ํด๋นํ๋ ์ธ๋ฑ์ค์ ๊ฐ ์ฆ๊ฐ for i in range(len(count)): # ๋ฆฌ์คํธ์ ๊ธฐ๋ก๋ ์ ๋ ฌ ์ ๋ณด ํ์ธ print(str(i)*count[i], end = '') # ์ด๊ฒ ๋ ํจ์จ์
Java
import java.util.*; public class Main { public static final int MAX_VALUE = 9; public static void main(String[] args) { int n = 15; // ๋ชจ๋ ์์์ ๊ฐ์ด 0๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๋ค๊ณ ๊ฐ์ int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2}; // ๋ชจ๋ ๋ฒ์๋ฅผ ํฌํจํ๋ ๋ฐฐ์ด ์ ์ธ(๋ชจ๋ ๊ฐ์ 0์ผ๋ก ์ด๊ธฐํ) int[] cnt = new int[MAX_VALUE + 1]; for (int i = 0; i < n; i++) { cnt[arr[i]] += 1; // ๊ฐ ๋ฐ์ดํฐ์ ํด๋นํ๋ ์ธ๋ฑ์ค์ ๊ฐ ์ฆ๊ฐ } for (int i = 0; i <= MAX_VALUE; i++) { // ๋ฐฐ์ด์ ๊ธฐ๋ก๋ ์ ๋ ฌ ์ ๋ณด ํ์ธ for (int j = 0; j < cnt[i]; j++) { System.out.print(i + " "); // ๋์ด์ฐ๊ธฐ๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฑ์ฅํ ํ์๋งํผ ์ธ๋ฑ์ค ์ถ๋ ฅ } } } }
๐คฏ ๋ณต์ก๋ ๋ถ์
โ
๊ณ์ ์ ๋ ฌ์ ์๊ฐ ๋ณต์ก๋
์ ๊ณต๊ฐ ๋ณต์ก๋
๋ ๋ชจ๋ O(N + K)
โ
๊ณ์ ์ ๋ ฌ์ ๋์ ๋ฐ๋ผ์ ์ฌ๊ฐํ ๋นํจ์จ์ฑ์ ์ด๋ํ ์ ์์ต๋๋ค.
๐๐ป ๋ฐ์ดํฐ๊ฐ 0๊ณผ 999,999๋ก ๋จ 2๊ฐ๋ง ์กด์ฌํ๋ ๊ฒฝ์ฐ ์ฌ๊ฐํ ๊ณต๊ฐ ๋ญ๋น
โ
๊ณ์ ์ ๋ ฌ์ ๋์ผํ ๊ฐ์ ๊ฐ์ง๋ ๋ฐ์ดํฐ๊ฐ ์ฌ๋ฌ ๊ฐ ๋ฑ์ฅํ ๋ ํจ๊ณผ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋ค.
๐๐ป ์ฑ์ ์ ๊ฒฝ์ฐ 100์ ์ ๋ง์ ํ์์ด ์ฌ๋ฌ ๋ช
์ผ ์ ์๊ธฐ ๋๋ฌธ์ ๊ณ์ ์ ๋ ฌ์ด ํจ๊ณผ์
๋งค๋ฒ ๋ฐฐ์ด A์์ ๊ฐ์ฅ ์์ ์์๋ฅผ ๊ณจ๋ผ์, ๋ฐฐ์ด B์์ ๊ฐ์ฅ ํฐ ์์์ ๊ต์ฒดํ๋ค.
โ๐ป ๊ฐ์ฅ ๋จผ์ ๋ฐฐ์ด A์ B๊ฐ ์ฃผ์ด์ง๋ฉด A์ ๋ํ์ฌ ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ๊ณ , B์ ๋ํ์ฌ ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ
โ๐ป ์ดํ์ ๋ ๋ฐฐ์ด์ ์์๋ฅผ ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค๋ถํฐ ์ฐจ๋ก๋ก ํ์ธํ๋ฉด์ A์ ์์๊ฐ B์ ์์๋ณด๋ค ์์ ๋์๋ง ๊ต์ฒด๋ฅผ ์ํ
์ด ๋ฌธ์ ์์๋ ๋ ๋ฐฐ์ด์ ์์๊ฐ ์ต๋ 100,000๊ฐ๊น์ง ์
๋ ฅ๋ ์ ์์ผ๋ฏ๋ก, ์ต์
์ ๊ฒฝ์ฐ O(NlogN)
์ ๋ณด์ฅํ๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด์ผ ํ๋ค.**
python
n, k = map(int, input().split()) # N๊ณผ K๋ฅผ ์ ๋ ฅ ๋ฐ๊ธฐ a = list(map(int, input().split())) # ๋ฐฐ์ด A์ ๋ชจ๋ ์์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ b = list(map(int, input().split())) # ๋ฐฐ์ด B์ ๋ชจ๋ ์์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ a.sort() # ๋ฐฐ์ด A๋ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ์ํ b.sort(reverse=True) # ๋ฐฐ์ด B๋ ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ ์ํ # ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค๋ถํฐ ํ์ธํ๋ฉฐ, ๋ ๋ฐฐ์ด์ ์์๋ฅผ ์ต๋ K๋ฒ ๋น๊ต for i in range(k): # A์ ์์๊ฐ B์ ์์๋ณด๋ค ์์ ๊ฒฝ์ฐ if a[i] < b[i]: # ๋ ์์๋ฅผ ๊ต์ฒด a[i], b[i] = b[i], a[i] else: # A์ ์์๊ฐ B์ ์์๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ๋, ๋ฐ๋ณต๋ฌธ์ ํ์ถ break print(sum(a)) # ๋ฐฐ์ด A์ ๋ชจ๋ ์์์ ํฉ์ ์ถ๋ ฅ
Java
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // N๊ณผ K๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ int n = sc.nextInt(); int k = sc.nextInt(); // ๋ฐฐ์ด A์ ๋ชจ๋ ์์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ Integer[] a = new Integer[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } // ๋ฐฐ์ด B์ ๋ชจ๋ ์์๋ฅผ ์ ๋ ฅ๋ฐ๊ธฐ Integer[] b = new Integer[n]; for (int i = 0; i < n; i++) { b[i] = sc.nextInt(); } // ๋ฐฐ์ด A๋ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ์ํ Arrays.sort(a); // ๋ฐฐ์ด B๋ ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ ์ํ Arrays.sort(b, Collections.reverseOrder()); // ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค๋ถํฐ ํ์ธํ๋ฉฐ, ๋ ๋ฐฐ์ด์ ์์๋ฅผ ์ต๋ K๋ฒ ๋น๊ต for (int i = 0; i < k; i++) { // A์ ์์๊ฐ B์ ์์๋ณด๋ค ์์ ๊ฒฝ์ฐ if (a[i] < b[i]) { // ๋ ์์๋ฅผ ๊ต์ฒด int temp = a[i]; a[i] = b[i]; b[i] = temp; } // A์ ์์๊ฐ B์ ์์๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ๋, ๋ฐ๋ณต๋ฌธ์ ํ์ถ else break; } // ๋ฐฐ์ด A์ ๋ชจ๋ ์์์ ํฉ์ ์ถ๋ ฅ long result = 0; for (int i = 0; i < n; i++) { result += a[i]; } System.out.println(result); } }