๐™‡๐™„๐™Ž

uuuouuoยท2022๋…„ 7์›” 25์ผ
0
post-thumbnail

๐Ÿ“– ์ตœ์žฅ ์ฆ๊ฐ€ ์ˆ˜์—ด (Longest Increasing Subsequence)


๐Ÿ’ฌ ๋ฌธ์ œ ์˜ˆ์‹œ


๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ˆ˜์—ด์ด ๋‚˜์—ด๋˜์žˆ๋‹ค. ์ด ๋ฐฐ์—ด์˜ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•˜๋ฉด์„œ ํฌ๊ธฐ๊ฐ€ ์ ์ง„์ ์œผ๋กœ ์ปค์ง€๋Š” ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„์˜ ์ˆ˜์—ด ๊ธธ์ด๋ฅผ ๊ตฌํ•˜์‹œ์˜ค. [ 3, 2, 6, 4, 5, 1 ]

  • ์ตœ์žฅ ์ฆ๊ฐ€ ์ˆ˜์—ด์€ 2, 4, 5 ์ด๊ณ , ๊ธธ์ด๋Š” 3์ด๋‹ค.

โ—พ ๋ฐฉ๋ฒ• 1

  • ํ•ด๋‹น ์ˆ˜์—ด ์›์†Œ๋“ค์„ ์ฐจ๋ก€๋กœ ํ™•์ธํ•˜๋Š” ๋ฐฉ๋ฒ•
  • ํ™•์ธํ•˜๋ ค๋Š” ํ•ด๋‹น ์›์†Œinput[i]์˜ ์ „ ์›์†Œ๋“ค(๋ฒ”์œ„: j = 0 ~i)๊ณผ ๋น„๊ตํ•จ
  • ์ž๊ธฐ ์ž์‹ ๋ณด๋‹ค ์ž‘์„ ๋•Œ ๋‚˜์˜ ํ˜„์žฌ ์ตœ์žฅ ์ฆ๊ฐ€ ์ˆ˜์—ด ๊ธธ์ดlength[i]๋ณด๋‹ค ๋‚˜๋ณด๋‹ค ์ž‘์€ ์ˆ˜input[j]์˜ ์ตœ์žฅ ์ฆ๊ฐ€ ์ˆ˜์—ด ๊ธธ์ดdml +1์ธ ๊ฐ’ length[j]+1 ๋” ํด ๋•Œ ํฐ ์ˆ˜ ๊ฐฑ์‹ 
  • ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n^2)
int[] input = {3, 2, 6, 4, 5, 1};
int[] length = new int[6]; // ํ•ด๋‹น ์ธ๋ฑ์Šค์—์„œ ๋๋‚˜๋Š” ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด

for (int i = 0; i < 6; i++) {
	lis[i] = 1;
	
	for (int j = 0; j < i; j++) {
		// ํ˜„์žฌ ๋‚˜(i)๋ณด๋‹ค ์ด์ „ ๊ฐ’(j)์ด ๋” ํฌ๋ฉด ๋„˜์–ด๊ฐ€
		if(input[j] > input[i]) continue;
		
		if(length[j] + 1 > length[i]) {
			length[i] = length[j] + 1;
			
		}
	}
}

// ์ด์ค‘ ๊ฐ€์žฅ ๊ธด ๊ธธ์ด๊ฐ€ ๋‹ต
for (int i = 0; i < 6; i++) {
	System.out.println(length[i]);			
}

โ—พ ๋ฐฉ๋ฒ• 2

์ด๋ถ„ ํƒ์ƒ‰์„ ์ด์šฉํ•œ ๋ฐฉ๋ฒ•

  • ๊ธธ์ด์™€ ํ•ด๋‹น ์›์†Œ๋“ค์„ ์•Œ ์ˆ˜ ์žˆ์Œ
  • ์‹œ๊ฐ„๋ณต์žก๋„ : O(nlogn)
public static void main(String[] args) {
	int[] input = {3, 2, 6, 4, 5, 1};
	int[] lis = new int[6]; // ์ตœ์žฅ ์ฆ๊ฐ€ ์ˆ˜์—ด ์ง‘ํ•ฉ
		
	lis[0] = input[0];
		
	int i = 1;
	int j = 0;
	while (i < 6) {
		// input[i] ๊ฐ’์ด ๋” ํฌ๋ฉด, lis ๋ฐฐ์—ด์˜ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๊ฐ’ ๋’ค์— ์‚ฝ์ž…
		if (lis[j] < input[i]) {
			lis[j + 1] = input[i];
			j += 1;
		}
		// input[i] ๊ฐ’์ด ๋” ์ž‘์œผ๋ฉด, ์ด๋ถ„ํƒ์ƒ‰
		else {
		    // 0๋ถ€ํ„ฐ j๊นŒ์ง€ ํƒ์ƒ‰ํ•˜๋ฉด์„œ input[i]์— ๋“ค์–ด๊ฐˆ ์œ„์น˜๋ฅผ ์ฐพ์•„์„œ idx์— ๋ฐ˜ํ™˜
			int idx = binarySearch(0, j, input[i], lis);
			lis[idx] = input[i];
		}
		i += 1;
	}
        
    // ์ตœ์žฅ ์ฆ๊ฐ€ ์ˆ˜์—ด์˜ ์›์†Œ๋“ค ์ถœ๋ ฅ
	for (int k = 0; k < 6; k++) {
		System.out.println(lis[k]);			
	}
	
}

static int binarySearch(int left, int right, int target, int[] lis) {
	int mid = 0;
		
	while(left < right) {
		mid = (left + right) / 2;
			
		if(lis[mid] < target) left = mid + 1;
		else right = mid;
	}
	return right;
}

0๊ฐœ์˜ ๋Œ“๊ธ€