-
728x90๋ฐ์ํ
๋ ์ง : 2021 ๋ 11์ 1 ์ผ
์์ฒญ ๊ฐ์ : ๋์ ๊ณํ๋ฒ๊ณผ ๋ถํ ์ ๋ณต, ๋ณํฉ ์ ๋ ฌ (1), ๋ณํฉ ์ ๋ ฌ (2)๋์ ๊ณํ๋ฒ๊ณผ ๋ถํ ์ ๋ณต
๋์ ๊ณํ๋ฒ (DP)
- ์ ๋ ฅ ํฌ๊ธฐ๊ฐ ์์ ๋ถ๋ถ์ ํด๊ฒฐํ์ฌ ํฐ ๋ฌธ์ ํด๊ฒฐ์ ์ ์ฉํ๋ ๋ฐฉ์
- ์ํฅ์ (sub problems -> main problem )
- Memoization ๊ธฐ๋ฒ ์ฌ์ฉ
Memoization
์ด๋, ์ด์ ๊ฐ์ ๊ธฐ์ตํ์ฌ runtime์ด๋ memory ๋ฌธ์ ๋ฅผ ํด๊ฒฐํด์ค๋ค. -> ๋ฐฑ์ค ๋ฌธ์ ์์ ์ ์ฉํ๊ฒ ์ฌ์ฉ๋ถํ ์ ๋ณต (Divide and Conquer)
- ๋ฌธ์ ๋ฅผ ๋๋ ์ ์์๋๊น์ง ๋๋์ด ํผ ํ, ํด๋ต์ ํฉ์น๋ค
- ํํฅ์ (main problem -> sub problems)
DP vs ๋ถํ ์ ๋ณต ์์ฝ
DP ๋ถํ ์ ๋ณต common ๋ฌธ์ ๋ฅผ ์ชผ๊ฐ์ด (๋๋์ด) ํ์ดํ๋ค Differences sub-problems: ์ค๋ณต๋๋ฉฐ, ์ด sub-problems๋ก ์์ ๋ฌธ์ ๋ฅผ ํ ์ ์๋ค. ๋ถ๋ถ ๋ฌธ์ ๋ค์ ์ค๋ณต๋์ง ์๋๋ค Memoization์ ํตํด ์ค๋ณต๋๋ ์ฐ์ฐ ๊ธฐํผ ๋ฐ๋ผ์, Memo๋ฅผ ํ ํ์๊ฐ ์๋ค
DP Example
DP ์ ๊ฐ์ฅ ๋ํ์ ์ธ ์์๋ก๋ ํฉํ ๋ฆฌ์ผ, ํผ๋ณด๋์น ์์ด, ๋ต์น ๋ฑ์ด ์๋ค.
์ด์ค ๋น๊ต์ ๊ฐ๋จํ ํฉํ ๋ฆฌ์ผ๋ก ์์๋ฅผ ๋ค๊ณ ์ ํ๋ค.Previously,
์ฌ๊ท๋ฅผ ํตํด์ ํฉํ ๋ฆฌ์ผ์ ํธ๋ ๋ฐฉ์์ด ๋ณดํธ์ ์ด๋ค
์ฌ๊ท๋ฅผ ์ฌ์ฉํ์ฌ ํฉํ ๋ฆฌ์ผ์ ์ฐ์ฐํ๊ฒ ๋๋ฉด, ๋งค๋ฒ ๊ฐ์ ๊ณ์ฐํด์ผ ํด์ ์ค๋ณต๋๋ ๊ณ์ฐ๋ค์ด ๋ง์์ง๋ค.public static int recursive(int number) { if(number == 1) return 1; return recursive(number-1)*number; }
With DP,
DP๋ฅผ ์ฌ์ฉํ์ฌ ํ๋ฉด, ์ด์ ๊ฐ๋ค์ด ์ ์ฅ๋๊ธฐ ๋๋ฌธ์ ์ค๋ณต ์ฐ์ฐ์ด ์์ด์ง๋ค/** * Dynamic Programming * Memoization์ ์ฌ์ฉํ๋ค * ํ๋ฒ ๊ณ์ฐํ ๊ฐ์, D[current_index]์ ์ ์ฅ๋๊ธฐ ๋๋ฌธ์ ๋ค์ ๊ณ์ฐ๋ ํ์ ์๋ค * */ public static int dynamic(int number) { //Step 1 : D[] ๋ฐฐ์ด ์์ฑ Integer[] D = new Integer[number+1]; //Step 2 : Initialize init_values D[0] = 0; D[1] = 1; //Step 3 : for loop๋ฅผ ๋๋ฉด์ ๊ฐ ๋ฐฐ์ด์ ๊ฐ์ ์ ๋ฐ์ดํธ (ํ์ฌ๊ฐ์ ์ด์ ๊ฐ์ ์ฐธ๊ณ ํ์ฌ ์ ๋ฐ์ดํธํ๋ค) for(int i = 2 ; i<= number ; i ++) { D[i] = D[i-1] * i;//์ด์ ๊ฐ * ํ์ฌ๊ฐ } return D[number]; //๋งจ ๋ง์ง๋ง ๋ฐฐ์ด์ ์์๊ฐ ์ต์ข ๊ฐ์ }
Example - ๋ถํ ์ ๋ณต
๋ณํฉ ์ ๋ ฌ์ด ๊ฐ์ฅ ๋ํ์ ์ธ ๋ถํ ์ ๋ณต์ ์๋ก ๋ค ์ ์๋ค.
๋ณํฉ ์ ๋ ฌ (Merge Sort)
๋ณํฉ ์ ๋ ฌ์ ์ฌ๊ท ์ฉ๋ฒ์ ์ด์ฉํ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก,
6 5 1 2 7 4 5 ์์ ๊ฐ์ ๋ฐฐ์ด์ด ์์ ๋ ์ต์์ ๋จ์๋ก ๋๋์ด์ง ๋ ๊น์ง ๋ฐ์ผ๋ก ๊ณ์ ๋๋๊ณ (divide)
์ฌ์กฐ๋ฆฝ ๋ ๋ ์ ๋ ฌ(sort)ํ์ฌ ํฉ์น๋(merge) ๋ฐฉ์์ด๋ค.
Step 1: Divide
mid = 7/2 = 3
6 5 1 2 7 4 5 Step 2 : Divide
mid = 4/2 = 2, 3/2 = 1
6 5 1 2 7 4 5 Step 3: Divide (Completed)
6 5 1 2 7 4 5 Step 4 : Merge - index 0๊ณผ 0๋ผ๋ฆฌ ๋น๊ต
left array:
5 6 right array:
1 2 left array 2:
4 7 right array 2:
5 Step 5 : Merge - index 01 ~ 01 ๋ผ๋ฆฌ ๋น๊ต
Array 1๋ผ๋ฆฌ ๋น๊ต
index 0 vs 0 : 5 > 1
1 index 0 vs 1 : 5 > 2
1 2 left Array๋ง ๋จ์๊ธฐ ๋๋ฌธ์ left Array๋ฅผ sorted array ๋ค์ ๋ถํ๋ค
1 2 5 6 Array 2 ๋ผ๋ฆฌ ๋น๊ต
index 0 vs 0 : 4 < 5
4 index 1 vs 0 : 7 > 5
4 5 4 5 7 Step 5 :
Array 1 vs Array 2
1 2 5 6 4 5 7 sorted array :
1
1 2 5 6 4 5 7 sorted array :
1 2
1 2 5 6 4 5 7 sorted array :
1 2 4
1 2 5 6 4 5 7 sorted array :
1 2 4 5
1 2 5 6 4 5 7 sorted array :
1 2 4 5 5
1 2 5 6 4 5 7 sorted array :
1 2 4 5 5 6
1 2 5 6 4 5 7 sorted array :
1 2 4 5 5 6 7 ์์์ MergeSort ์๊ณ ๋ฆฌ์ฆ์ ์ดํด๋ณด์๋ค.**
์ด์ , ์ฌ๊ท๋ฅผ ํตํด Merge Sort๋ฅผ ๊ตฌํํด๋ณด๋ฉด,**
import java.util.Arrays; /** * @author June Park * @date 11/01/2021 * Merge Sort ๊ตฌํ * ์ฌ๊ท๋ก ๊ตฌํ * */ public class MergeSort { static int N = 10; static int [] sorted = new int[N]; public static void main(String[] args) { //Create an random array int[] given = new int [N]; for(int i = 0 ; i < N ; i ++) { given[i] = (int) (Math.random()*100)+1; } split(given,0,N-1); //0~N-1 (์ด N๊ฐ) ๊น์ง ์ชผ๊ฐค ๊ฒ for(int i : given) {System.out.print(i+ " ");} } /** * Split Method * Splits arrays to half (start ~ mid, mid ~ end ) whereas mid = start+end / 2 * Splits until start < end -> splits everyeach elements * Merge the split array * * */ private static void split(int[] given, int start, int end) { if(start < end ) { //stops the recursion when its all split int mid = (start + end ) /2 ; //Recursive: split(given, start , mid );//0~half split(given, mid+1, end); //half ~ end //merge the split array merge(given, start, mid, end); } } /** Case 1 : left side ์ right side array ๊ฐ ๋ ๋ค ์ค์ฌํ ๋ : * given[startpointer] ์ given[endpointer] ๋ฅผ ๋น๊ตํ์ฌ sort ํ ํ, ์ฌ์ฉํ ํฌ์ธํฐ๋ ++ํ์ฌ ๋ค์์ผ๋ก ๋๊ฒจ์ค * * Case 2 : left ๋ง ๋จ์ * sorted array์ left๋ฅผ ๋ถ์ * * Case 3 : right ๋ง ๋จ์ * sorted array์ right ๋ถ์ * */ private static void merge(int[] given, int start, int mid, int end) { int startPointer = start; int index = start; int endPointer = mid+1; //๋ ๋ฐฐ์ด ์ค ํ๋๋ฅผ ๋ค ์ฎ๊ธธ ๋ ๊น์ง ๋ฐ๋ณต //Case 1 : while(startPointer <= mid && endPointer<= end) { if(given[startPointer] < given[endPointer]){ //startPointer๊ฐ ๋ ์์ผ๋ฉด, startpointer++ sorted[index] = given[startPointer]; startPointer ++; } else { sorted[index] = given[endPointer]; endPointer ++; } index++; //sorted array์ ์ธ๋ฑ์ค๋ฅผ ํ ์นธ ์ฎ๊น } //Case 2 and 3 : Case 1์ด ๋๋๊ณ , left ๋ right ์๋ง ๋จ์ if(startPointer > mid ) { //right ๋ง ๋จ์ for(int i = endPointer ; i <= end ; i ++) { //endpointer ~ end ๊น์ง sorted ์ ๋ํจ sorted[index] = given[i]; index++; } } else { //left ๋ง ๋จ์ for(int i = startPointer ; i<= mid ; i++) { //startpointer ~ mid ๊น์ง sorted์ ๋ํจ sorted[index] = given[i]; index++; } } //์ ๋ ฌ๋ ๋ฐฐ์ด์ ์ฝ์ for(int i = start ; i <= end ;i ++) { given[i] = sorted[i]; //given ์ ํ์ฌ sorted process๋ฅผ ํด๋์์ผ๋ง, split์ด ๋ค์ merge๋ฅผ ๋ถ๋ ์ ๋ current process๊ฐ ์ ์ง } System.out.println(Arrays.toString(given)); } }
์ฌ๊ท๋ฅผ ํตํด ๋ฐฐ์ด์ ๋ฐ์ผ๋ก ๋ถํ ํ ํ, sort ์ํค๋ ๊ณผ์ ์ ๋ฐ๋ณตํ์ฌ ๊ตฌํํด ๋ณผ ์ ์๋ค.
ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ๋ฐ๋ก๊ฐ๊ธฐ๐ https://bit.ly/3FVdhDa
์๊ฐ๋ฃ 100% ํ๊ธ ์ฑ๋ฆฐ์ง | ํจ์คํธ์บ ํผ์ค
๋ฑ 5์ผ๊ฐ ์งํ๋๋ ํ๊ธ์ฑ๋ฆฐ์ง๋ก ์๊ฐ๋ฃ 100% ํ๊ธ๋ฐ์ผ์ธ์! ๋ ๋ฆ๊ธฐ์ ์ ์๊ธฐ๊ณ๋ฐ ๋ง์ฐจ ํ์น!
fastcampus.co.kr
๋ณธ ํฌ์คํ ์ ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ์ฐธ์ฌ๋ฅผ ์ํด ์์ฑ๋์์ต๋๋ค.
728x90๋ฐ์ํ'๐ STUDY > FASTCAMPUS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 5์ผ์ฐจ (0) 2021.11.05 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 4์ผ์ฐจ (0) 2021.11.04 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 3์ผ์ฐจ (0) 2021.11.03 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 2์ผ์ฐจ (0) 2021.11.02 [FASTCAMPUS] ๊ฐ์์ด๊ธฐ 30์ผ 100% ํ๊ธ ์ฑ๋ฆฐ์ง (0) 2021.11.01 ๋๊ธ