LIS, LDS

👉 11053 LIS

[정답 코드]

import sys
input = sys.stdin.readline

n = int(input())
seq = list(map(int, input().split()))
res = [1] * n # 메모이제이션을 위한 배열
for i in range(1, n):
    for j in range(i - 1, -1, -1):
        if seq[i] > seq[j]:
            res[i] = max(res[i], res[j] + 1)
print(max(res))

[풀이]

• 수열의 모든 항들을 차례대로 방문한다.(첫번째 for문)
• 0번째 항까지 거꾸로 하나씩 방문해가는데, 이 때 자신의 값보다 작은 값을 가진 항을 만났을 시 결과값을 max(res[i], res[j] + 1)로 갱신한다.(두번째 for문, 메모이제이션)

👉 11055 LIS & Sum

[정답 코드]

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

int main() {
    int n, i, j;
    int arr[1000] = {0};
    int memo[1000] = {0};
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> arr[i];
    }
    memo[0] = arr[0];
    for (i = 1; i < n; i++) {
        for (j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j]) {
                memo[i] = max(memo[i], memo[j] + arr[i]);
            }
        }
        if (memo[i] == 0) memo[i] = arr[i];
    }
    int res = 0;
    for (i = 0; i < n; i++) {
        res = max(res, memo[i]);
    }
    cout << res << endl;
    return 0;
}

[오류 해결]

✔ 배열 초기화

• 만약 현재 칸(arr[i]) 전까지의 모든 칸에서 자신의 값보다 작은 값으로 이루어진 증가 부분 수열이 발견되지 않았다면, 메모이제이션 배열 칸(memo[i])에 현재 칸의 값(arr[i])을 넣어주어야 한다.
  if (memo[i] == 0) memo[i] = arr[i];
• input과 동시에 memo[i]을 arr[i] 값으로 초기화하는 방법도 있다.

👉 11054 Bitonic

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

int main() {
    int n, i, j;
    int arr[1000] = {0};
    int memo_in[1000], memo_de[1000];
    int res = 0;
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> arr[i];
        memo_in[i] = 1;
        memo_de[i] = 1;
    }
    // LIS
    for (i = 0; i < n; i++) {
        for (j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j]) {
                memo_in[i] = max(memo_in[i], memo_in[j] + 1);
            }
        }
    }
    // LDS
    for (i = n - 1; i >= 0; i--) {
        for (j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                memo_de[i] = max(memo_de[i], memo_de[j] + 1);
            }
        }
        // LIS + LDS - 1
        res = max(res, memo_in[i] + memo_de[i] - 1);
    }
    cout << res << endl;
    return 0;
}

[적용 자료구조 및 알고리즘]

• Dynamic Programming