강사님 LIS 설명해주실때..

안녕하세요 공부님 ㅎㅎ

음 이코드 말씀하시는거죠?

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[1001], cnt[1001], ret;
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 0; i < n; i++) {
      int maxValue = 0;
      for (int j = 0; j < i; j++) {
        if (a[j] < a[i] && maxValue < cnt[j]) maxValue = cnt[j];
      }
      cnt[i] = maxValue +1;
      ret = max(ret,cnt[i]);
    }
    printf("%d\n", ret);
}

자, 저 maxValue는 최대의 cnt를 만들기 위한 임시 변수입니다.

예를 들어

10 20 10 20 30 이 있다고 해볼게요.

처음입니다. maxValue는 0이기 때문에 0 + 1을 해서 1입니다.

10 20 10 20 30

이상태에서

20을 탐색을 해나갑니다. 20보다 작은 수는 10이죠? 이 10의 cnt값은 1입니다. 여기에다 + 1을 한게 20의 lis가 되는 것이죠.

10 20 10 20 30

1 2

그러나 10보다 작은 수는 존재하지 않습니다.

10 20 10 20 30

1 2 1

그 다음으로 가서 20보다 작은 수를 보니 10밖에 없습니다. maxValue는 10의 cnt값을 가져옵니다. 여기서 maxValue는 1입니다. 20보다 작은 수, 그리고 최대의 cnt를 만들기 위한 임시 변수는 1로 담겼다가

10 20 10 20 30

1 2 1 2

나중에

      cnt[i] = maxValue +1;

이걸 거쳐서 cnt에는 2가 담기게 됩니다.

그 다음, 30으로 가서 30보다 작은 수, 10, 20 이 있습니다. maxValue는 10의 cnt, 20의 cnt 를 거치는데 원래 maxValue가 1이였다 20의 cnt를 거치면서 maxValue = 2가 됩니다.

왜냐하면

        if (a[j] < a[i] && maxValue < cnt[j]) maxValue = cnt[j];

앞의 코드에 부합하면서

10 >> maxValue = 0, 10의 cnt : 1 >>>

maxValue = 1 을거쳐...

20 >> maxValue = 1, 20의 cnt : 2 >>>

maxValue = 2가 되는 것이죠.

10 20 10 20 30

1 2 1 2 3

그렇게 해서 해당 cnt에는 +1을 한 3이 담기게 됩니다.

또한, 공부님 앞으로 공부하실 때 문제 링킹좀 부탁드립니다.

해당 부분은 0주차 질문하는법 보시면 나와있어요. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변