์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- java
- ๋ฐ์ดํฐํ์
- ๋ฐฑ์ค11053 #ํ์ด์ฌ #python
- ๋ฌธ์์ด
- stream
- ์ฐ์ฐ์
- ๋
- ์ฟ ํกERD
- ์๋ฐ
- ์คํ์์ด
- ๋ฐฑ์ค1874
- ์ฟ ํกDB
- ๋ฐฑ์ค9012
- ๋ฐฐ์ด
- ์
- ์คํธ๋ฆผ
- ์คํ
- ๋ฐฑ์ค9093
- StringBuffer
- ์ฐ
- ํ๋ฐฉ์ฟผ๋ฆฌ
- StringBuilder
- Today
- Total
Tech Log ๐ ๏ธ
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ด๋? ๋ณธ๋ฌธ
"์ด๊ฒ์ด ์ทจ์ ์ ์ํ ์ฝ๋ฉ ํ ์คํธ๋ค with ํ์ด์ฌ" ๋ด์ฉ์ ๊ธฐ๋ฐ์ผ๋ก ์ ์ํ์์ต๋๋ค.
(https://www.youtube.com/watch?v=KGyK-pNvWos&t=2349s)
์ ๋ ฌ์ด๋?
- ๋ฐ์ดํฐ๋ฅผ ํน์ ํ ๊ธฐ์ค์ ๋ฐ๋ผ ์์๋๋ก ๋์ดํ๋ ๊ฒ์ด๋ค.
- ๋ฌธ์ ์ ๋ฐ๋ผ ์ ์ ํ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ด ์ฌ์ฉ๋๋ค.
์์ ๊ฐ์ด ์ ๋ ฌ๋์ง ์์ ์์ด์ ์ ๋ ฌํ๋ ค๋ฉด ์ด๋ป๊ฒ ํด์ผ๋ ๊น ?
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์๋ ํฌ๊ฒ 4๊ฐ์ง๊ฐ ์๋ค.
1. ์ ํ ์ ๋ ฌ
- ์ฒ๋ฆฌ๋์ง ์์ ๋ฐ์ดํฐ ์ค์์ ๊ฐ์ฅ ์์ ๋ฐ์ดํฐ๋ฅผ ์ ํํด ๋งจ ์์ ์๋ ๋ฐ์ดํฐ์ ๋ฐ๊พธ๋ ๊ฒ์ ๋ฐ๋ณตํ๋ค.
7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
์ฒซ๋ฒ์งธ ๋จ๊ณ์์๋ 0์ด ์ ์ผ ์์ผ๋ฏ๋ก 0๊ณผ 7์ ๊ตํํ๋ค.
0 | 5 | 9 | 7 | 3 | 1 | 6 | 2 | 4 | 8 |
๋๋ฒ์งธ ๋จ๊ณ์์๋ 1์ด ์ ์ผ ์์ผ๋ฏ๋ก 5์ ๊ตํํ๋ค.
0 | 1 | 9 | 7 | 3 | 5 | 6 | 2 | 4 | 8 |
์ด๋ ๊ฒ ๋จ๊ณ๋ฅผ ์งํํด๋๊ฐ๋ค ๋ณด๋ฉด ๊ฒฐ๊ตญ 0๋ถํฐ 9๊น์ง ์ ๋ ฌ์ด ๋๋ค.
์๊ฐ๋ณต์ก๋ : O(N^2)
์์ค์ฝ๋
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for(int i=0;i<arr.length;i++){
int min_idx = i;
for(int j=i+1;j<arr.length;j++){
if(arr[min_idx] > arr[j]){
min_idx = j;
}
}
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
for (int num : arr) {
System.out.print(num+" ");
}
}
}
2. ์ฝ์ ์ ๋ ฌ
- ์ฒ๋ฆฌ๋์ง ์์ ๋ฐ์ดํฐ๋ฅผ ํ๋์ฉ ๊ณจ๋ผ ์ ์ ํ ์์น์ ์ฝ์ ํ๋ค.
- ์ ํ ์ ๋ ฌ๋ณด๋ค ๋ ํจ์จ์ ์ผ๋ก ๋์ํ๋ค.
7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
์ฒซ๋ฒ์งธ ๋จ๊ณ์์๋ 5์ ์์น๋ฅผ ๊ฒฐ์ ํ๋ค. 7์ ์ค๋ฅธ์ชฝ or ์ผ์ชฝ์ผ๋ก ๊ฐ๊ฒ ๋๋๋ฐ 7๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ 7์ ์ผ์ชฝ์ผ๋ก ์ด๋ํ๋ค.
5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
๋๋ฒ์งธ ๋จ๊ณ์์๋ 9์ ์์น๋ฅผ ์ ํ๋ค. ํ์ง๋ง ์์ ์๋ ๋ ๊ฐ์ ์ซ์๋ณด๋ค 9๊ฐ ๋ ํฌ๋ฏ๋ก ์์น๋ฅผ ๋ณ๊ฒฝํ์ง ์๋๋ค.
(์ ํํ๋ ๋ฐ๋ก ์์ 7๋ณด๋ค ์ปค์ ๋ฐ๋ก ์ ๋ ฌ์ ๋ฉ์ถ๋ค,)
์ด๋ฐ์์ผ๋ก ์ ๋ ฌ์ ์งํํ๋ฉด 0๋ถํฐ 9๊น์ง ์ ๋ ฌ์ด ๋๋ค.
์๊ฐ ๋ณต์ก๋: O(N^2)
์์ค์ฝ๋
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for(int i=1;i<arr.length;i++){
for(int j=i;j>0;j--){
if(arr[j-1] > arr[j]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
else break;
}
}
for (int num : arr) {
System.out.print(num+" ");
}
}
}
3. ํต ์ ๋ ฌ
- ๊ธฐ์ค ๋ฐ์ดํฐ๋ฅผ ์ค์ ํ๊ณ ๊ทธ ๊ธฐ์ค๋ณด๋ค ํฐ ๋ฐ์ดํฐ์ ์์ ๋ฐ์ดํฐ์ ์์น๋ฅผ ๋ณ๊ฒฝ
- ํ๋ก๊ทธ๋๋ฐ ์ธ์ด์ ์ ๋ ฌ ๋ผ์ด๋ธ๋ฌ๋ฆฌ์ ๊ทผ๊ฐ
- ๋ณดํต ์ฒซ ๋ฒ์งธ ๋ฐ์ดํฐ๋ฅผ ๊ธฐ์ค(pivot)์ผ๋ก ํ๋ค.
5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
์ฒซ๋ฒ์งธ ๋จ๊ณ์์๋ 5๋ฅผ ๊ธฐ์ค์ผ๋ก ํ๋ค.
๊ทธ๋ ๋ค๋ฉด ์ผ์ชฝ์์๋ถํฐ 7์ 5๋ณด๋ค ํฌ๊ธฐ์ ์ ํ๋๊ณ , ์ค๋ฅธ์ชฝ์์๋ถํฐ์ 4๋ 5๋ณด๋ค ์๊ธฐ์ ์ ํ๋๋ค.
์ด์ ๋์ ์์น๋ฅผ ๋ฐ๊พผ๋ค.
5 | 4 | 9 | 0 | 3 | 1 | 6 | 2 | 7 | 8 |
์ด์ ์ชฝ์์๋ถํฐ 9๋ 5๋ณด๋ค ํฌ๊ธฐ์ ์ ํ๋๊ณ , ์ค๋ฅธ์ชฝ์์๋ถํฐ์ 2๋ 5๋ณด๋ค ์๊ธฐ์ ์ ํ๋๋ค.
๋ค์ ๋์ ์์น๋ฅผ ๋ฐ๊พผ๋ค.
์ด๋ ๊ฒ ์งํํ๋ค๋ณด๋ฉด ๋ฐ์ดํฐ์ ์์น๊ฐ ์๊ฐ๋ฆฌ๋ ์๊ฐ์ด ์ฌ๊ฒ์ด๋ค.
๊ทธ๋ ์์ ๋ฐ์ดํฐ์ ํผ๋ฒ๊ฐ์ ์์น๋ฅผ ๋ณ๊ฒฝํ๋ค
1 | 4 | 2 | 0 | 3 | 5 | 6 | 9 | 7 | 8 |
์ด๋ ๊ฒ ๋๋ฉด ์ผ์ชฝ ๋ฐ์ดํฐ๋ 5๋ณด๋ค ์๊ณ , ์ค๋ฅธ์ชฝ ๋ฐ์ดํฐ๋ 5๋ณด๋ค ํฌ๋ค.
์ด์ฒ๋ผ ํผ๋ฒ์ ๊ธฐ์ค์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ๋๋๋ ๊ฒ์ ๋ถํ ์ด๋ผ๊ณ ํ๋ค.
์์์ ์งํํ๋ ๊ฒ์ฒ๋ผ ๋ถํ ๋ ๋ฐ์ดํฐ์์ ๋ค์ ํต์ ๋ ฌ์ ์ ์ฉํ๋ฉด ๋๋ค.
์๊ฐ๋ณต์ก๋ : ์ผ๋ฐ์ ์ผ๋ก O(NlogN) , ์ต์ ์ ๊ฒฝ์ฐ O(N^2)
์์ค์ฝ๋
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr,0,arr.length-1);
for (int num : arr) {
System.out.print(num+" ");
}
}
public static void quickSort(int[] arr,int start,int end){
if(start >= end) return;
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);
}
}
4. ๊ณ์ ์ ๋ ฌ
- ํน์ ํ ์กฐ๊ฑด์ด ๋ถํฉํ ๋๋ง ๋งค์ฐ ๋น ๋ฅด๊ฒ ๋์ํ๋ค.
- ๋ฐ์ดํฐ์ ํฌ๊ธฐ ๋ฒ์๊ฐ ์ ํ๋์ด ์ ์ ํํ๋ก ํํํ ์ ์์๋๋ง ๊ฐ๋ฅํ๋ค.
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
๋จผ์ ํฌ๊ธฐ๊ฐ 0 ์ธ ๋ฐฐ์ด์ ๋ง๋ค์ด์ค๋ค.
7 | 7 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 |
๋ง์ฝ ์ด๋ฐ ๋ฐฐ์ด์ด ์๋ค๋ฉด ๊ฐ๊ฐ์ ๋ฐ์ดํฐ๊ฐ ๋์ค๋ ์ซ์๋ฅผ ์นด์ดํ ํ๊ณ ๋ฐฐ์ด์ ์ง์ด ๋ฃ๋ ๋ค๋ฉด ํจ๊ณผ์ ์ผ ๊ฒ์ด๋ค.
๋จผ์ ๋ง๋ 0 ๋ฐฐ์ด์ ์ ์ฉ์์ผ๋ณด์
0 | 2 | 2 | 2 | 1 | 1 | 0 | 2 | 0 | 0 |
์ซ์๋ค์ด ๋ฑ์ฅํ ํ์๋งํผ ๋ฐฐ์ด์ ํ๋ฌ์ค๋ฅผ ํด์ฃผ์ด ๋ฃ์ด์ฃผ์๋ค.
์ด์ ์ด๊ฒ์ ๊ทธ๋๋ก ์ถ๋ ฅํด์ฃผ๋ฉด ๋๋ค.
์ด ์๊ณ ๋ฆฌ์ฆ์ ์ต์ ์ ๊ฒฝ์ฐ์๋ O(N+K)๋ฅผ ๋ณด์ฅํ์ง๋ง ๊ฒฝ์ฐ์ ๋ฐ๋ผ์ ์ต์ ์ ํจ์จ์ ๋ผ ์๋ ์๋ค.
ex) 0๊ณผ 9๋ฐ์ ๋ฐ์ดํฐ๊ฐ ์๋ ๊ฒฝ์ฐ์๋ ๋ฐ์ดํฐ๊ฐ ๋ ๊ฐ๋ฐ์ ์๋ ๋ฐ ํฌ๊ธฐ๊ฐ 10์ธ ๋ฐฐ์ด์ ๋ง๋ค์ด์ ์ ๋ ฌํด์ผํ๋ค.
๋ฐ๋ผ์, ๋์ผํ ๊ฐ์ด ์ฌ๋ฌ๊ฐ์ผ ๊ฒฝ์ฐ ํจ๊ณผ์ ์ผ๋ก ์๋ํ ์ ์๋ค.
์์ค์ฝ๋
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int[] sort = new int[arr.length+1];
for(int i=0;i<arr.length;i++){
sort[arr[i]] ++;
}
for(int i=0;i<sort.length;i++){
for(int j=0;j<sort[i];j++){
System.out.print(i+" ");
}
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] LEVEL2 ๊ฑฐ๋ฆฌ๋๊ธฐ ํ์ธํ๊ธฐ (Java) (0) | 2023.05.24 |
---|---|
ํฌ ํฌ์ธํฐ ์๊ณ ๋ฆฌ์ฆ์ด๋ ? (ํ๋ก๊ทธ๋๋จธ์ค - ์ฐ์๋ ๋ถ๋ถ ์์ด์ ํฉ) (3) | 2023.05.10 |
[๋ฐฑ์ค] 14889๋ฒ ์คํํธ์ ๋งํฌ ์๋ฐ(๋ฐฑํธ๋ํน , ๋นํธ๋ง์คํน) (0) | 2023.03.28 |
[๋ฐฑ์ค] 1991๋ฒ ํธ๋ฆฌ์ํ JAVA (0) | 2023.03.26 |
[๋ฐฑ์ค] 11723 ์งํฉ JAVA (2) | 2023.03.23 |