[Inflearn] 연속 부분 증가수열(LIS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 연속으로 증가하는 부분 수열의 최대 길이

     - 값이 같을 때는 증가하는 것으로 간주

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

     - 최대 N 은 100,000

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 예제로

      5 7 3 3 12 12 13 10 11 를 입력받았다고 먼저 생각해보자.

      이 문제도 그냥 풀었다간 시간초과 BAAAAM 을 볼 것이다.

      첫 번째 index 부터 

      5, sum = 1

      7, sum = 2

      3 ?! 이전 인덱스의 숫자보다 작다. sum이 max보다 크다면 저장하고 다시 sum = 1

      3, sum = 2

      12, sum = 3

      12, sum =4

      13, sum = 5

      10 ?! 이전 인덱스의 숫자보다 작다. sum이 max 보다 크다면 저장하고 다시 sum = 1

      11, sum = 2

  

      이 과정을 코드로 옮겨보자 !

#. Code

#include <cstdio>
#include <vector>
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
    int n, i, sum = 1, max = 1;
 
    scanf("%d", &n);
    std::vector<int> v(n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);
 
    for (i = 1; i < n; i++)
    {
        if (v[i] >= v[i - 1])
            sum++;
        else
        {
            max = sum > max ? sum : max;
            sum = 1;
        }
    }
 
    printf("%d\n", max);
        
    return 0;
}

#. Other code

#include<stdio.h>            
 
int main(){
    int n, i, pre, now, cnt, max;
 
    scanf("%d", &n);
    scanf("%d", &pre);
    cnt=1;
    max=1;
 
    for(i=2; i<=n; i++){
        scanf("%d", &now);
 
        if(now>=pre){
            cnt++;
 
            if(cnt>max) max=cnt;
        }
        else cnt=1;
 
        pre=now;
    }
 
    printf("%d\n", max);    
 
    return 0;
}

로직은 유사하지만 위 코드에서는 데이터를 저장하는 배열을 사용하지 않고 입력을 받자마자 바로 처리를 해주어서 더 효율적인 것 같다.

내 코드같은 경우는 vector도 생성해주고 그 안에 데이터도 넣어준 후에야 처리를 한다.. 

pre, now 변수를 사용하여 배열을 사용하지 않고 문제를 해결해내는 센스는 배우면 좋을 것 같다.

그리고 내가 실수한게 있었는데 test case 가 적어서 넘어간 것 같지만 max 값 갱신을 내 코드에서는 연속 부분 증가수열이 끊길 때

하기때문에 만일 끝까지 끊기지 않는다면 max 갱신이 되지 않을 것이다.

여기서 얻어갈 부분은 

1. 배열을 사용하지 않고 변수로 문제를 해결해내는 센스

2. max 를 갱신하는 위치 다시 체크

3. 웬만하면 반복문이 많아지면 프로그램 속도가 느려지기 때문에 위 코드처럼 반복문 안에서 입력과 처리를 동시에 해주는 것이 좋다.

   O(2N) 에 해결한 문제를 O(N) 만에 해결할 수 있게 될 것이다. 

#. Result

  - Input --------------------------------------------------------

9

5 7 3 3 12 12 13 10 11

------------------------------------------------------------------

  - Output --------------------------------------------------------

5

------------------------------------------------------------------