M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 11053 - 가장 긴 증가하는 부분 수열(LIS)

최대 1 분 소요

문제

백준 11053 - 가장 긴 증가하는 부분 수열 풀러가기

문제 분석

이 문제는 유명해서 약자가 있는 문제다.

L ongest

I ncreasing

S ubsequence

어떤 한 시점에서 봤을 때, 그 시점까지 증가하는 가장 긴 길이는 답이 하나 뿐이다. 따라서 Dynamic Programming 을 이용하여 풀 수 있다.

현재 시점에서 이전 값들을 살펴보며, 자신보다 작은 값들 중 현재 길이가 max인 녀석을 지금 값으로 가지면 된다.

문제 풀이(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #include <cstdio>
    #include <vector>
    #include <algorithm>
     
    using namespace std;
     
    int main() {
        int n;
     
        scanf("%d", &n);
     
        vector<int> a(n);
        vector<int> d(n);
     
        for (int i = 0;i < n; i++) {
            scanf("%d", &a[i]);
        }
     
        for (int i = 0; i < n; i++) {
            d[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i] && d[i] < d[j] + 1) {
                    d[i] = d[j] + 1;
                }
            }
        }
     
        printf("%d", *max_element(d.begin(), d.end()));
     
        return 0;
    }
    		cs





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고