📝 Baekjoon 12015 문제풀이

---

💡문제 정의

baekjoon 12015

문제는 위와 같다. input의 최대 크기가 1,000,000이기 때문에 O(N^2)의 시간복잡도로 문제를 해결할 수 없으며, O(NlogN)의 해법을 찾아야 한다.
결국 Binary Search를 이용하라는 의미였다.

처음에 문제를 해결하지 못해서 구글링을 해보니, 이러한 유형의 문제를 최장 증가 수열 (LIS: Longest Increasing Subsequence) 문제라고 한다.

arr = 10 20 40 25 20 50 30 70 85 와 같은 배열이 있다고 해보자.
여러 블로그를 참고하여.. 내가 문제를 해결한 방식은 아래와 같다.

1. LIS라는 빈 배열을 하나 만든다.
2. 배열 요소들을 하나씩 돌면서 LIS 배열에 추가하는데, 이때 어느 위치에 넣으면 좋을지 최적의 위치를 찾아야 한다 -> 이처럼 LIS 배열 내의 최적의 삽입 위치를 찾는 과정에서 Binary Search 시행

1) 10 -> LIS = {10}

2) 20 -> LIS = {10, 20}

3) 40 -> LIS = {10, 20, 40}

위와 같이 LIS 배열의 마지막 요소보다 해당 요소가 더 크다면, LIS 배열의 마지막에 해당 요소를 삽입하면 끝.

4) 25 -> LIS = {10, 20, 25}

문제는 4번과 같은 경우를 어떻게 처리해야 하냐이다. 10, 20 뒤에 40을 그대로 두냐 vs 25를 새로 넣냐인데, 당연히 40 대신 25를 넣는 것이 이득이다. 만약 25 다음 요소가 30이라고 해보자. 이때 LIS가 {10, 20, 40} 이라면 30을 넣을 수 없으므로 배열의 길이는 3이다. 반면 40 대신 25를 넣어서 LIS가 {10, 20, 25}가 된다면 30을 마지막에 삽입하여 LIS는 {10, 20, 25, 30}이 되고, 배열의 길이가 더 길어질 수 있다.

5) 20 -> LIS = {10, 20, 25}

6) 50 -> LIS = {10, 20, 25, 50}

7) 30 -> LIS = {10, 20, 25, 30}

8) 70 -> LIS = {10, 20, 25, 30, 70}

9) 85 -> LIS = {10, 20, 25, 30, 70, 85}

위의 과정을 아래와 같이 코드로 구현해 보았다.

1) C

#include <stdio.h>

int LIS[1000000];

int main(void)
{
  int N;
  scanf("%d", &N);

  int index = 0;

  for (int i = 0; i < N; i++)
  {
    int num;
    scanf("%d", &num);

    if (index == 0)
      LIS[index++] = num;
    else if (LIS[index - 1] < num)
      LIS[index++] = num;
    else
    {
      int l = 0, r = index - 1;

      while (l <= r)
      {
        int mid = (l + r) / 2;
        if (LIS[mid] == num) {
          l = mid;
          break;
        }
        
        if (LIS[mid] < num)
          l = mid + 1;
        else
          r = mid - 1;
      }

      LIS[l] = num;
    }

  }

  printf("%d\n", index);

  return 0;
}

---

💡참고

https://jason9319.tistory.com/113
https://canoe726.tistory.com/9