leesangwon0114

I am Research Engineer. Currently working in KT.

C++Algorithm 17. 다이나믹 프로그래밍 문제풀이 3

05 Feb 2019 » Algorithm, c++

codeplus 백준 강사 강의 내용기반으로 정리한 내용입니다.(비공개 포스트)

가장 긴 증가하는 부분 수열 문제

Longest Increasing Subsequence(LIS) 문제

가장 긴 증가하는 부분 수열 문제

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int N = 0;
  cin >> N;

  vector<int> arr(N + 1, 0);
  vector<int> dp(N + 1, 0);

  for (int i = 0; i < N; ++i) {
    cin >> arr[i];
  }


  for(int i=0; i<N; ++i) {
    dp[i] = 1;
    for (int j = 0; j < i; ++j) {
      if (arr[j] < arr[i] && dp[j]+1 > dp[i]) {
        dp[i] = dp[j] + 1;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    if (ans < dp[i])
      ans = dp[i];
  }
  cout << ans << '\n';
  return 0;
}

가장 긴 증가하는 부분 수열4 문제

가장 긴 증가하는 부분 수열4 문제

#include <iostream>
#include <vector>

using namespace std;

void go(int p, vector<int>& a, vector<int>& v) {
  if (p == -1) {
    return;
  }
  go(v[p], a, v);
  cout << a[p] << ' ';
}

int main() {
  int N = 0;
  cin >> N;

  vector<int> arr(N + 1, 0);
  vector<int> dp(N + 1, 0);
  vector<int> prev(N + 1, -1);

  for (int i = 0; i < N; ++i) {
    cin >> arr[i];
  }

  for (int i = 0; i<N; ++i) {
    dp[i] = 1;
    for (int j = 0; j < i; ++j) {
      if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        prev[i] = j;
      }
    }
  }
  int ans = 0;
  int max_index = 0;
  for (int i = 0; i < N; ++i) {
    if (ans < dp[i]) {
      ans = dp[i];
      max_index = i;
    }
  }
  cout << ans << '\n';
  go(max_index, arr, prev);
  cout << '\n';
  return 0;
}

가장 큰 증가하는 부분 수열 문제

가장 큰 증가하는 부분 수열 문제

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int N = 0;
  cin >> N;

  vector<int> arr(N + 1, 0);
  vector<int> dp(N + 1, 0);

  for (int i = 0; i < N; ++i) {
    cin >> arr[i];
  }


  for (int i = 0; i<N; ++i) {
    dp[i] = arr[i];
    for (int j = 0; j < i; ++j) {
      if (arr[j] < arr[i] && dp[j] + arr[i] > dp[i]) {
        dp[i] = dp[j] + arr[i];
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    if (ans < dp[i])
      ans = dp[i];
  }
  cout << ans << '\n';
  return 0;
}

연속합 문제

연속합 문제

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n = 0;
  cin >> n;
  vector<int> arr(n + 1, 0);
  vector<int> dp(n + 1, 0);
  for (int i = 0; i < n; ++i)
    cin >> arr[i];
  dp[0] = arr[0];
  for (int i = 1; i < n; ++i) {
    dp[i] = arr[i];
    if (dp[i] < dp[i - 1] + arr[i]) {
      dp[i] = dp[i - 1] + arr[i];
    }
  }
  int ans = dp[0];
  for (int i = 1; i < n; ++i) {
    if (ans < dp[i])
      ans = dp[i];
  }
  cout << ans << '\n';
  return 0;
}

연속합2 문제

연속합2 문제

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n = 0;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i<n; i++) {
    cin >> a[i];
  }
  vector<int> d(n);
  vector<int> dr(n);
  for (int i = 0; i<n; i++) {
    d[i] = a[i];
    if (i == 0) continue;
    if (d[i] < d[i - 1] + a[i]) {
      d[i] = d[i - 1] + a[i];
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    dr[i] = a[i];
    if (i == n - 1) continue;
    if (dr[i] < dr[i + 1] + a[i]) {
      dr[i] = dr[i + 1] + a[i];
    }
  }
  int ans = d[0];
  for (int i = 1; i<n; i++) {
    if (ans < d[i]) {
      ans = d[i];
    }
  }
  for (int i = 1; i<n - 1; i++) {
    if (ans < d[i - 1] + dr[i + 1]) {
      ans = d[i - 1] + dr[i + 1];
    }
  }
  cout << ans << '\n';
  return 0;
}

Related Posts