[ 백준 11053 &11054 ] 가장 긴 증가하는 부분 수열 & 가장 긴 바이토닉 부분 수열(C++)

 

11053번: 가장 긴 증가하는 부분 수열

 

 

11054번: 가장 긴 바이토닉 부분 수열

문제!

---

두문제 모두 부분수열에 대한 문제로서 

11053  -- 증가하는 부분수열에 대해서 구하는 문제

 

11054 --  바이토닉 수열을 구하는 문제

// 바이토닉 수열 -- > 한 값을 기준으로 연속된 수들이 거나, 계속하여 증가수열, 감소수열이 되는 수열

 

였습니다. 풀이 방식이 비슷하여 한 글로 묶었습니다!

 

 

 

 

 

먼저 가장 긴 증가하는 부분 수열!

---

만약

A = {10, 20, 10, 30, 20, 50}  이라는 수열이 있다면

{10},{10, 20},{10, 20, 10, 30},{20}.... 등의 여러 부분수열이 존재합니다.

 

그중 증가하는 부분수열을 찾아야하는 문제로 완전탐색을 통해 모든 수열을 만들어 볼수도있지만

 

이렇게하면.. 당연히 시간초과...

 

그렇기에 부분수열을 구하는 방법을 동적계획법으로 풀어 보았습니다.

 

 

 

 

시작!

---

먼저 어떻게 저장할지를 생각해보았는데 여러 방법중....

n번째에서 끝나는 부분수열의 최대길이를 저장하는것이 정답이었습니다.

int grap[1001] = { 0 };// 부분수열 수
int dp[1001] = { 0 };

//부분수열의 길이? , n번째를 선택했을때의 최대길이? (x)
// 아니면 이분법으로  n번 선택시 몇개되는지 탐색? (x)

//... n번째에서 끝나는 부분수열의 최대길이 저장 ooooo

바로 현재 위치에서 왼쪽에 있는 dp들을 참고해서 점점 오른쪽으로 확장해 나가는 방법입니다!

 

 

 

코드로 보면 아래처럼 나오게됩니다.

for (int i = 1; i < n + 1; i++) {
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (grap[j] < grap[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
                // 현재 저장된 값과 전번에서 현재위치까지 포함한 길이
			}
		}
	}

증가수열이기에  grap[j] < grap[i] 이러한 조건을 통과하면 dp에 저장하게끔 해주는 방식!

 

 

그리고 dp중에서 제일 큰 값을 출력해주면 끝!

 

 

 

 

 

 

 

다음은 가장 긴 바이토닉 부분 수열!

---

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

위의 정의를 따르는 가장 긴 부분수열을 만드는 문제입니다.

 

방법은 위의 가장 긴 부분수열 문제와 동일합니다!

 

전 문제에서는 한쪽으로만 탐색을 했다고 하면

이번엔 한 위치에서 양쪽으로 탐색을 해주어 총합의 최대값을 구해주면 됩니다!

 

 

 

 

 

 

시작!

 

---

먼저 기본적인 값들을 선언해주고 이번엔 오른쪽 왼쪽으로 나누어줍시다.

int grap[1001] = { 0 };// 부분수열 수
int dp_r[1001] = { 0 }; // 이번엔 n번째를 기준으로 바이토닉 수열이 되는지?
int dp_l[1001] = { 0 }; // 이번엔 n번째를 기준으로 바이토닉 수열이 되는지?

 

 

왼쪽으로 이동하는 탐색은 위의 문제와 동일합니다.

dp_l[1] = 1;
	for (int i = 2; i < n + 1; i++) {// 왼쪽으로
		dp_l[i] = 1;
		for (int j = 1; j < i; j++) {
			if (grap[j] < grap[i]) {
				dp_l[i] = max(dp_l[i], dp_l[j] + 1);
			}
		}
	}

 

 

이제 오른쪽으로 탐색을 돌려주어야하는데

여기서 약간의 거꾸로? 반대로 탐색을 돌려주어야 합니다.

 

dp_r[n] = 1;
	for (int i = n-1; 0<=i; i--) {// 오른쪽으로
		dp_r[i] = 1;
		for (int j = i + 1; j < n + 1; j++) {
			if (grap[j] < grap[i]) {
				dp_r[i] = max(dp_r[i], dp_r[j] + 1);
			}
		}
	}

 

 

이제 이 합에다 -1 을 해준값의 최대를 구해서 출력하면 끝!

 

 

 

---

 

ALL 1

#include <iostream>
#include <algorithm>
using namespace std;

int grap[1001] = { 0 };// 부분수열 수
int dp[1001] = { 0 };

//부분수열의 길이? , n번째를 선택했을때의 최대길이? (x)
// 아니면 이분법으로  n번 선택시 몇개되는지 탐색? (x)

//... n번째에서 끝나는 부분수열의 최대길이 저장 ooooo

int main() {
	int n;
	int answer=0;

	cin >> n;

	for (int i = 1; i < n+1; i++) {
		cin >> grap[i];
		
	}

	for (int i = 1; i < n + 1; i++) {
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (grap[j] < grap[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}


	for (int i = 1; i < n + 1; i++) {
		answer = max(dp[i], answer);
	}

	
	

	cout << answer << endl;
}

 

 

 

ALL 2

#include <iostream>
#include <algorithm>
using namespace std;
// 동적계획법 - > 직전의 정보를 현재의 정보를 구하는데 사용할수 있다 -- > 점화식이 존재 --> 단순한 앞뒤 계산가능할때

int grap[1001] = { 0 };// 부분수열 수
int dp_r[1001] = { 0 }; // 이번엔 n번째를 기준으로 바이토닉 수열이 되는지?
int dp_l[1001] = { 0 }; // 이번엔 n번째를 기준으로 바이토닉 수열이 되는지?



// 바이토닉 수열 -- > 한 값을 기준으로 연속된 수들이 거나, 계속하여 증가수열, 감소수열이 되는 수열
//{10, 20, 30, 25, 20} , {10, 20, 30, 40}, {50, 40, 25, 10}
int main() {
	int n;
	int answer=0;

	cin >> n;

	for (int i = 1; i < n+1; i++) {
		cin >> grap[i];
		
	}

	dp_l[1] = 1;
	for (int i = 2; i < n + 1; i++) {// 왼쪽으로
		dp_l[i] = 1;
		for (int j = 1; j < i; j++) {
			if (grap[j] < grap[i]) {
				dp_l[i] = max(dp_l[i], dp_l[j] + 1);
			}
		}
	}

	dp_r[n] = 1;
	for (int i = n-1; 0<=i; i--) {// 오른쪽으로
		dp_r[i] = 1;
		for (int j = i + 1; j < n + 1; j++) {
			if (grap[j] < grap[i]) {
				dp_r[i] = max(dp_r[i], dp_r[j] + 1);
			}
		}
	}
	
	for (int i = 1; i < n + 1; i++) {
		answer = max(dp_r[i]+ dp_l[i]-1, answer);
	}

	cout<<answer << endl;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!