์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
- ํฐ์คํ ๋ฆฌ์ฑ๋ฆฐ์ง
- ๋ฐ์ํ
- ์ฝ๋ฉ
- ์ปดํจํฐ๊ณผํ
- html
- JavaScript
- ๋ง์ผ๋ด๊ฐ์ธ์์๋ค์์ฐ๋ค๋ฉด
- Python
- ์ค๋ธ์
- ๊ฐ๋ฐ
- ์นํ์ด์ง๋ง๋ค๊ธฐ
- css
- ์ค๋ผํด
- ๊น๋ฏธ๊ฒฝ์๋งํ์์
- ComputerScience
- ๋ผํ๋ผ์ค์๋ง๋
- K๋ฐฐํฐ๋ฆฌ
- K๋ฐฐํฐ๋ฆฌ๋ ๋ณผ๋ฃจ์
- ํ์ด์ฌ
- ๋ฆฌ์กํธ
- ์๋ฐ์คํฌ๋ฆฝํธ
- ์นํผ๋ธ๋ฆฌ์ฑ
- database
- Java
- ๋ ์
- ์๋ฐ
- ํ๋ก๊ทธ๋๋ฐ
- ์ํ
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ์ฑ
- Today
- Total
JiYoung Dev ๐ฅ
[์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ] ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ, ํ์ ์๊ณ ๋ฆฌ์ฆ (2023.04.04) ๋ณธ๋ฌธ
[์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ] ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ, ํ์ ์๊ณ ๋ฆฌ์ฆ (2023.04.04)
Shinjio 2023. 4. 23. 18:25๐ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ
์์๋ค์ ์ผ์ ํ ์์๋๋ก ์ด๊ฑฐํ๋ ์๊ณ ๋ฆฌ์ฆ
๐ ์ฝ์ ์ ๋ ฌ
ํน์ ํ ๋ฐ์ดํฐ๋ฅผ ์ ์ ํ ์์น์ ์ฝ์ ํ๋ ์ ๋ ฌ
๋ฐ์ดํฐ๊ฐ ๊ฑฐ์ ์ ๋ ฌ ๋์ด ์์ ๋ ํจ์จ์
๐ ๋ณํฉ์ ๋ ฌ
์ฃผ์ด์ง ์๋ฃ๋ฅผ ์๊ฒ ์ชผ๊ฐ ๋ค ํฉ์น๋ ๊ณผ์ ์์ ์ ๋ ฌ
๐ ํต์ ๋ ฌ
๊ธฐ์ค ํค(pivot)๋ฅผ ๊ธฐ์ค์ผ๋ก ์๊ฑฐ๋ ๊ฐ์๊ฐ์ ์ง๋ ๋ฐ์ดํฐ๋ ์์ผ๋ก, ํฐ ๊ฐ์ ์ง๋ ๋ฐ์ดํฐ๋ ๋ค๋ก ๊ฐ๋๋ก ํ์ฌ ๋ฐ์ดํฐ๋ฅผ ๋ถ๋ฆฌํด๊ฐ๋ฉฐ ์ ๋ ฌ
์ผ์ชฝ์์ ์์ํ ํค๋ ๊ธฐ์คํค๋ณด๋ค ํฌ๋ฉด, ์ค๋ฅธ์ชฝ์์ ์์ํ ํค๋ ๊ธฐ์คํค๋ณด๋ค ์์ผ๋ฉด ๋ฉ์ถค
๋ ๊ฐ์ ์๋ฆฌ๋ฅผ ๋ฐ๊ฟ
๋ ๊ฐ์ ์ปค์๊ฐ ๋ง๋๋ฉด ์ผ์ชฝ์ผ๋ก๋ ๊ธฐ์คํค๋ณด๋ค ์์ ๊ฐ๋ง, ์ค๋ฅธ์ชฝ์๋ ๊ธฐ์คํค๋ณด๋ค ํฐ ๊ฐ๋ง ๋จ์
๐ ๋ฒ๋ธ์ ๋ ฌ
๋ ์ธ์ ํ ์์๋ฅผ ๋น๊ตํ์ฌ ์ ๋ ฌํ๋ ๋ฐฉ๋ฒ
ํ ํด๋ง ๋๋๋ ๊ฐ์ฅ ํฐ ์ซ์๊ฐ ์ ์ผ ๋ค์ ์์
์์์ ์ธ๋ฑ์ค 0, 1๋ถํฐ > 1, 2 > 2, 3 > ... > n-1, n๊น์ง ํ์ธ ---- 1ํ์ฐจ
0,1 > 1,2 > 2,3 > ... >n-2, n-1 ----- 2ํ์ฐจ
...
์ต๋ n-1ํ์ฐจ๊น์ง ์งํ
์ฅ์
- ์ธ์ ํ ๊ฐ๋ง ๊ณ์ํด์ ๋น๊ตํ๋ ๋ฐฉ์์ผ๋ก ๊ตฌํ์ด ์ฝ๋ค. >> ์นํ์ด ๋ง์ด ์ด๋ฃจ์ด์ง๋ค.
- ์ฝ๋๊ฐ ์ง๊ด์ ์ด๋ค.
- ์ค๊ฐ์ ๋ฉ์ถ ์ ์์
๋จ์
- ํ๋์ ์์๊ฐ ๊ฐ์ฅ ์ผ์ชฝ์์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ๋ ค๋ฉด ๋ฐฐ์ด์ ๋ชจ๋ ์์์ ๊ตํ ๋์ด์ผ ํจ
- ํน์ ์์๊ฐ ์ต์ข ์ ๋ ฌ ๊ฒฐ๊ณผ์ ๋ง๋ ์์น์ ์๋๋ผ๋ ๊ตํ๋๋ ์ผ์ด ์ผ์ด๋ ์ ์์
์ฆ, ๊ตฌํ์ด ๋จ์ํ์ง๋ง ๋๋ฆฌ๋ค.
package ์๊ณ ๋ฆฌ์ฆ;
import java.util.Arrays;
public class Ex01๋ฒ๋ธ์ ๋ ฌ_๋ด๋ฆผ์ฐจ์ {
public static void main(String[] args) {
//๋ค์ ๋ฐฐ์ด์ ๋ฒ๋ธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ์ฌ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ ํ ๊ฒฐ๊ณผ์ ๊ตํ ํ์ ์ถ๋ ฅ
int[] arr = {6,8,2,1,4,3};
int cnt = 0;
boolean sw = true;
for(int k = 0 ; k < arr.length - 1 ; k++) {
sw = true;
for(int i = 0 ; i < arr.length - k - 1 ; i++) {
if(arr[i] < arr[i+1]) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
sw = false;
}
}
if(sw) {
break;
}
System.out.println(k+1 + "ํ์ฐจ : " + Arrays.toString(arr));
}
}
}
๐ ์ ํ ์ ๋ ฌ
๊ฐ์ฅ ํฐ ์์ ๋๋ ์์ ์์๋ฅผ ์ฐพ์ ์ฃผ์ด์ง ์์น๋ฅผ ๊ต์ฒดํด ๋๊ฐ๋ ์์
๊ฐ์ฅ ์์ ์๊ฐ ์๋ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ์ตํ๋ ๋ณ์ ํ์
0๋ฒ ์ธ๋ฑ์ค์ 1~n-1๋ฒ ์ธ๋ฑ์ค๊น์ง ํ๋ํ๋ ๋น๊ตํด๊ฐ๋ฉฐ ๊ฐ์ฅ ์์ ์ซ์์ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ์ตํด๋์๋ค๊ฐ, ์์น ๊ตํ
1๋ฒ ์ธ๋ฑ์ค์ 2~n-1๋ฒ ์ธ๋ฑ์ค๊น์ง ํ๋ํ๋ ๋น๊ตํด๊ฐ๋ฉด ๊ฐ์ฅ ์์ ์ซ์์ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ์ตํด๋์๋ค๊ฐ, ์์น ๊ตํ
์ต๋ n-1ํ์ฐจ๊น์ง ์งํ
ํ์ฐจ์ ๋ง์ง๋ง์๋ง ์นํ. ๋ฐ๊พธ๋๊ฒ ์ ๋ค. -> ์ด๋ฅผ ์ํด ์ธ๋ฑ์ค ๋ฒํธ๋ฅผ ๊ธฐ์ตํ๋ค.
์ค๊ฐ์ ๋ฉ์ถ ์ ์์. ๋๊น์ง ๋ด์ผํ๋ค.
์ฅ์
- ์ ๋ ฌ์ ์ํ ๋น๊ต ํ์๋ ๋ง์ผ๋ ๊ตํ ํ์๊ฐ ์ ๊ธฐ์ ๊ตํ์ด ๋ง์ด ์ด๋ฃจ์ด์ ธ์ผ ํ๋ ์ํ์์ ํจ์จ์
๋จ์
- ์ด๋ฏธ ์ ๋ ฌ๋ ์ํ์์ ์์์ ์๋ฃ๊ฐ ์ถ๊ฐ๋๋ฉด ์ฌ์ ๋ ฌํ ๋ ์ฒ๋ฆฌ ์๋๊ฐ ๋๋ฆผ
package ์๊ณ ๋ฆฌ์ฆ;
import java.util.Arrays;
public class Ex03์ ํ์ ๋ ฌ์๊ณ ๋ฆฌ์ฆ_๋ด๋ฆผ์ฐจ์ {
public static void main(String[] args) {
int[] arr = {6,8,2,1,4,3};
int index;
for(int i = 0 ; i < arr.length - 1 ; i++) {
index = i; //index๋ ๊ฐ์ฅ ํฐ ์์ ์ธ๋ฑ์ค ๋ฒํธ๋ฅผ ์ ์ฅํ๋ ๋ณ์
for(int j = index + 1 ; j < arr.length ; j++) {
if(arr[j] > arr[index]) {
index = j;
}
}
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
System.out.println(i+1 + "ํ์ฐจ : " + Arrays.toString(arr));
}
}
}
๐ ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ
ํน์ ์์๋ฅผ ๊ฒ์ํ๋ ์๊ณ ๋ฆฌ์ฆ
๐ ์์ฐจ๊ฒ์
๊ฐ์ฅ ๋จ์ํ ๊ฒ์ ๋ฐฉ๋ฒ์ผ๋ก ์์์ ์ ๋ ฌ์ด ํ์์๋ค.
ํ์ง๋ง ๋ฆฌ์คํธ ๊ธธ์ด๊ฐ ๊ธธ๋ฉด ๋นํจ์จ์
์ฒ์๋ถํฐ ๋๊น์ง ์์ฐจ์ ์ผ๋ก ๋น๊ต
package ์๊ณ ๋ฆฌ์ฆ;
public class Ex05์์ฐจ๊ฒ์์๊ณ ๋ฆฌ์ฆ {
public static void main(String[] args) {
int num = 78;
int[] arr = {13,35,15,11,26,72,78,13,61,90};
for(int i = 0 ; i < arr.length - 1 ; i++) {
if(num == arr[i]) {
System.out.println(i);
break;
}
}
}
}
๐ ์ด์ง๊ฒ์
๋ฆฌ์คํธ์ ์ค๊ฐ ๊ฐ์ ์ ํด ํฌ๊ณ ์์์ ๋น๊ตํด ๊ฒ์ํ๋ ์๊ณ ๋ฆฌ์ฆ
์ ๋ ฌ๋ ๋ฆฌ์คํธ์์๋ง ์ฌ์ฉํ ์ ์์
์ฒซ๋ฒ์งธ ์ธ๋ฑ์ค์ ๋ง์ง๋ง ์ธ๋ฑ์ค ์ฌ์ด ์ค๊ฐ ๋ฒํธ ์ธ๋ฑ์ค์ ์ฐพ๊ณ ์ ํ๋ ์์ ๋น๊ต
์ฐพ๊ณ ์ ํ๋ ์๊ฐ ์ค๊ฐ ๋ฒํธ ์ธ๋ฑ์ค์ ๊ฐ๋ณด๋ค ํฌ๋ฉด ์ค๊ฐ๊ฐ ์ดํ์ ๊ฐ๋ง ํ์ธ
์ฒซ ์ธ๋ฑ์ค์ ๋ง์ง๋ง ์ธ๋ฑ์ค ์ฌ์ด ์ค๊ฐ ์ธ๋ฑ์ค์ ๊ฐ๊ณผ ์ฐพ๊ณ ์ ํ๋ ์์ ๋น๊ต
์ฐพ๊ณ ์ ํ๋ ์๋ณด๋ค ์ค๊ฐ๊ฐ๋ณด๋ค ํฌ๋ฉด ์ค๊ฐ๊ฐ ์ดํ์ ๊ฐ ํ์ธ
์์ ์ํฉ์ ๋ฐ๋ณต. ์ค๊ฐ๋ฒํธ ์ธ๋ฑ์ค์ ๊ฐ์ด ์ฐพ๊ณ ์ ํ๋ ์์ ๊ฐ์ ๋๊น์ง.
package ์๊ณ ๋ฆฌ์ฆ;
public class Ex06์ด์ง๊ฒ์์๊ณ ๋ฆฌ์ฆ {
public static void main(String[] args) {
//์ด์ง๊ฒ์์๊ณ ๋ฆฌ์ฆ
//๋ณ์ 3๊ฐ๋ฅผ ์ฌ์ฉํด์ ๋ฐ์ดํฐ๋ฅผ ๊ฒ์
//lowIndex, highIndex, middleIndex
//์ฅ์ : ์๊ฐ๋ณต์ก๋๊ฐ 1/2๋ก ๋น ๋ฅธ ํ์ ์๋๋ฅผ ๊ฐ์ง๊ณ ์์!
//๋จ์ : ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ ์ ์ ๋ ฌ๋ ๋ฆฌ์คํธ์์๋ง ์ฌ์ฉํ ์ ์์!
int[] arr = {1,7,16,25,30,33,41,66,78,90};
//lowIndex : ์ต์ index ๊ฐ
int lowIndex = 0;
//highIndex : ์ต๋ index ๊ฐ
int highIndex = arr.length - 1;
int num = 78; //์ฐพ๊ณ ์ ํ๋ ์
while(true) {
//middleIndex ์ด๊ธฐํ
int middleIndex = (lowIndex + highIndex) / 2 ;
if(arr[middleIndex] == num) { //7
System.out.println("์ธ๋ฑ์ค ๋ฒํธ : " + middleIndex);
break;
}else {
if(arr[middleIndex] > num) {
highIndex = middleIndex - 1;
}else {
lowIndex = middleIndex + 1;
}
}
}
}
}