๊ด€๋ฆฌ ๋ฉ”๋‰ด

JiYoung Dev ๐Ÿ–ฅ

[์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜] ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜, ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (2023.04.04) ๋ณธ๋ฌธ

full stack/JAVA

[์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜] ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜, ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (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; 
				}
			}
		}
		

	}

}