[0624] 알고리즘

  동아리 알고리즘 스터디는 사실상 끝나긴 했는데... 그래도 하루 한 문제씩 풀다보니 나름 뭔갈 하고 있다는 기분이 들어서 할 수 있는대로 이어가보려고 한다. 어차피 알고리즘 공부는 해야했고...

---

11053. 가장 긴 증가하는 부분 수열

  다이내믹 프로그래밍 문제. 고민을 좀 오래했는데 코드 자체는 무척 간결하게 나왔다.

 

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);

    int n;
    std::cin >> n;

    std::vector<int> num(n);
    std::vector<int> memory(n, 1);

    for (int i = 0; i < n; i++)
    {
      std::cin >> num[i];
    }

    //memory[i] = i번째 인덱스까지의 LIS 배열 크기

    for (int i = 0; i < n; i++)
    {      
      for (int j = 0; j < i; j++)
      {
        if (num[j] < num[i])
        {
          memory[i] = (memory[i] > memory[j] + 1 ? memory[i] : memory[j] + 1);          
        }
      }
    }

    int max = * std::max_element(memory.begin(), memory.end());
    std::cout << max << '\n';

    return 0;
}

  처음엔 2중 for문을 돌면서 바로 직전에 검사한 수를 변수로 저장하고 이번에 들어온 배열 속 수가 변수 속 수보다 크면 LIS 길이를 하나 늘리는 식으로 구현했었는데... 이렇게 하면 메모이제이션을 하는 이유도 없고 애초에 잘못된 구현이었다. 그 후 다시 거쳤던 사고의 흐름을 정리하자면

 

• 전체 배열의 '가장 긴 증가하는 부분 수열(이하 LIS)'을 구하기 위해 각 부분의 LIS를 구할 필요가 있음.
• 각 부분의 LIS는 메모이제이션을 이용해 memory 배열에 저장할 것.
  * 이 때의 memory[i] : i번째 인덱스 까지의 LIS 배열의 길이.
• memory 배열은 미리 1로 초기화해둔다. 이는 LIS의 최소값이 무조건 1일 것이기 때문.
• 반복문을 돌며 LIS를 구한다.

 

  memory 배열에 대한 메모가 왜 되어있냐면 중간에 memory 배열이 구체적으로 뭘 가리키는지 잠깐 까먹어서 그랬다. 중간에 반복문 잘못 쓸 뻔한 원흉(한참 쳐다보다 아 싶었다).

 

  문제 자체는 별 생각 없이 다이내믹 프로그래밍 문제 모음 안에 있어서 풀었던 거였는데... 자세히 보니 이거 말고도 LIS 문제가 더 있더라. 알아보니 위의 구현 방식은 시간 복잡도가 O(N^2)고, 다른 LIS문제는 복잡도를 더 빠르게 구현해야 한다는 듯? 바리에이션이 다양한 문제인듯 하니 좀더 다양한 구현방법을 알아봐야겠다...