๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ’พ Algorithm/-- ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด๋ก 14

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ†ตํ•œ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜์™€ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ๊ตฌํ•˜๊ธฐ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• (์•Œ๊ณ ๋ฆฌ์ฆ˜)์€ ์„ธ๊ณ„ ์ตœ์ดˆ์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ด ์„ธ๊ณ„ ์ตœ์ดˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์–ด๋–ค ๋™์ž‘์„ ํ•˜๊ณ  ์–ด๋–ค ๊ฒฐ๊ณผ๋ฅผ ๋‚ด๋Š”์ง€ ์•Œ์•„๋ณด์ž. ์šฐ๋ฆฌ๊ฐ€ ๋ฐฐ์šธ ๊ฒƒ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ Java๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•œ ๊ตฌํ˜„ ์žฌ๊ท€ํ˜ธ์ถœ์„ ํ†ตํ•œ ๊ตฌํ˜„ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ ์‹œ๊ฐ„๋ณต์žก๋„ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ 2๊ฐœ์˜ ์ž์—ฐ์ˆ˜์˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜๋ž€ ๋ฌด์—‡์ธ์ง€ ๊ธฐ์–ต์ด ๋‚˜๋ฉด ์ข‹๊ฒ ์ง€๋งŒ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋Š” ์ค‘ํ•™๊ต 1ํ•™๋…„ ๊ต์œก ๊ณผ์ •์— ๋‚˜์˜ค๋Š” ๋‚ด์šฉ์ด๋ผ ๊นŒ๋จน์—ˆ์„ ์ˆ˜ ์žˆ๋Š” ์—ฌ๋Ÿฌ๋ถ„์—๊ฒŒ ๋‹ค์‹œ ํ•œ๋ฒˆ ์ƒ๊ธฐ์‹œ์ผœ์ฃผ์ž๋ฉด ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜๋ฅผ ๊ฐ€์žฅ ๋นจ๋ฆฌ ์ƒ๊ธฐ์‹œํ‚ค๋Š” ๋ฐฉ๋ฒ•์€ ์šฐ๋ฆฌ๊ฐ€ ์ฃฝ์–ด๋ผ ํ–ˆ๋˜ ๊ณต์‹์„ ํ•œ ๋ฒˆ ๋ณด์—ฌ์ฃผ๋Š” ๊ฒƒ์ด๋ผ ์ƒ๊ฐํ–ˆ๋‹ค. ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD) ๋Š” ์–ด๋–ค ๋‘ ์ˆ˜ A, B๊ฐ€.. 2021. 2. 4.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„] Java๋กœ ์„ ํƒ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„ํ•˜๊ธฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‹œ์ž‘ํ•˜๋ฉด ๋Œ€๋ถ€๋ถ„์˜ ์ฑ…์— ๊ฐ€์žฅ ์•ž์—์„œ ์†Œ๊ฐœ๋˜๋Š” Selection Sort. ์„ ํƒ ์ •๋ ฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด์ž. ์„ ํƒ ์ •๋ ฌ ์„ ํƒ ์ •๋ ฌ์€ ๋ฐฐ์—ด์˜ ์›์†Œ ์ค‘ ๊ฐ€์žฅ ์ž‘์€(ํฐ) ๊ฐ’์„ ๋ฐฐ์—ด์˜ ๋์œผ๋กœ ๋ณด๋‚ด๋Š” ์ž‘์—…์„ ๋ฐ˜๋ณตํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ฐ„๋‹จํ•œ ์ปจ์…‰์ธ ๋งŒํผ ํšจ์œจ์„ฑ์€ ๋–จ์–ด์งˆ ์ˆ˜ ์žˆ์œผ๋‚˜ ์ ์€ ์–‘์˜ ๋ฐ์ดํ„ฐ์—์„œ๋Š” ํšจ๊ณผ์ ์ผ ์ˆ˜ ์žˆ๋‹ค. ์ •๋ ฌ ๊ณผ์ • ์ฃผ์–ด์ง„ ๋ฆฌ์ŠคํŠธ์—์„œ ์ตœ์†Œ๊ฐ’์„ ์ฐพ๊ธฐ ๊ทธ ๊ฐ’์„ ๋งจ ์•ž์˜ ๊ฐ’๊ณผ ๊ต์ฒด ์ฒ˜์Œ ๋งจ ์œ„์น˜๋ฅผ ๋บ€ ๋‚˜๋จธ์ง€๋ฅผ ์œ„์™€ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ต์ฒด ์˜ ๊ณผ์ •์œผ๋กœ ์ •๋ ฌ์ด ์ด๋ฃจ์–ด์ง„๋‹ค. ์ƒ๊ฐํ•ด๋ณด์ž. ๋งŒ์•ฝ [9, 1, 6, 8 ,4, 3, 2, 0] ์ด๋ผ๋Š” ๋ฐฐ์—ด์ด ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ณด์ž. ๋ฐฐ์—ด : [9, 1, 6, 8, 4, 3, 2, 0] ์ตœ์†Œ๊ฐ’ : 0 ๋ฐฐ์—ด : [0, 1 ,6 ,8 ,4 ,3 ,2, 9] ์ตœ์†Œ๊ฐ’ : 1 ๋ฐฐ์—ด .. 2021. 1. 13.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด๋ก ] ๋ณ‘ํ•ฉ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž๋ฐ”๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ :: Merge Sort Algorithm implementing by java package theory.sort; import java.util.Arrays; public class MergeSort { static int[] sorted; public static void main(String[] args) { int[] arr = {4, 3, 9, 2, 7, 1, 6, 5, 8}; sorted = new int[arr.length]; mergeSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } private static void mergeSort(int[] arr, int start, int end){ if(start < end) { int mid = (start + end) / 2; mergeS.. 2020. 6. 20.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด๋ก ] ์ด์ง„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž๋ฐ”๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ:: Binary Search Algorithm implementing by java package algorithm.class01_BinarySearch; import java.util.Arrays; public class Prob00_MyBS { public static void main(String[] args) { int[] arr = {5,1,23,11,4,15,2,3,55,7}; // 1, 2, 3, 4, 5, 6, 7, 8, 9 int key = 1; Arrays.sort(arr); int loop = binarySearch_Loop(arr, key); int recursion = binarySearch_Recursion(arr, key, 0, arr.length-1); System.out.println("index : " + loop + " ๋ฐ˜๋ณต๋ฌธ ์‚ฌ์šฉ"); System.o.. 2020. 6. 20.