샘플 문제 : LIS

📌 1. 문제 정의: LIS란?

• LIS (Longest Increasing Subsequence)는 주어진 수열에서 순서대로 증가하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다.
• 일부 숫자를 생략하되, 순서는 유지되어야 합니다.
• 예를 들어:

입력: 1, 9, 2, 5, 7
가능한 증가 수열: 
  - 1, 2, 5 (길이 3)
  - 1, 2, 5, 7 (길이 4) ← 가장 긴 순 증가 부분 수열
정답: 4

---

🔁 2. 해결 전략: 동적 계획법(DP)

✨ 핵심 아이디어

• 모든 위치에서 시작하여, 해당 위치 이후의 수들 중 현재 수보다 큰 수들만 탐색.
• 각 위치에서 최장 증가 수열의 길이를 재귀적으로 계산하고, 이미 계산한 값은 캐시에 저장.

💡 메모이제이션 활용

• 동일한 위치에서 중복 계산을 피하기 위해 cache[pos]를 사용.
• 중복 호출 제거로 시간 복잡도를 줄임.

---

📄 3. 전체 코드 구조

#include <iostream>
#include <vector>
#include <cstring>  // memset
using namespace std;

int cache[100];
vector<int> seq;

int LIS(int pos) {
    int& ret = cache[pos];
    if (ret != -1) return ret;

    ret = 1;  // 최소는 자기 자신 1개
    for (int next = pos + 1; next < seq.size(); next++)
        if (seq[pos] < seq[next])
            ret = max(ret, 1 + LIS(next));
    return ret;
}

int main() {
    memset(cache, -1, sizeof(cache));
    seq = {10, 1, 9, 2, 5, 7};

    int result = 0;
    for (int i = 0; i < seq.size(); i++)
        result = max(result, LIS(i));

    cout << "LIS 길이: " << result << endl;
}

---

🔍 4. 코드 상세 분석

🔹 4.1 전역 변수 설정

int cache[100];
vector<int> seq;

• cache[100]: LIS(pos)의 반환값을 저장하는 캐시 배열
• seq: 입력 수열 저장용 벡터

🔹 4.2 메인 알고리즘: LIS(pos)

int LIS(int pos) {
    int& ret = cache[pos];
    if (ret != -1) return ret;  // 캐시 재활용

    ret = 1;  // 기본은 자기 자신 1개
    for (int next = pos + 1; next < seq.size(); next++)
        if (seq[pos] < seq[next])
            ret = max(ret, 1 + LIS(next));  // 조건 만족 시 재귀 탐색
    return ret;
}

• 기저 사례는 따로 없다. 가장 마지막 원소는 다음 원소가 없으므로 for 루프에 들어가지 않음.
• 현재 위치보다 큰 값만 고려 → 순 증가 조건
• 가장 큰 LIS 길이를 갱신하며 반환

🔹 4.3 main 함수

int main() {
    memset(cache, -1, sizeof(cache));  // 캐시 초기화
    seq = {10, 1, 9, 2, 5, 7};

    int result = 0;
    for (int i = 0; i < seq.size(); i++)
        result = max(result, LIS(i));  // 모든 위치에서 시작해보기

    cout << "LIS 길이: " << result << endl;
}

• 모든 인덱스에서 LIS(i) 실행:
  • 왜냐면 수열의 시작 위치는 제한이 없기 때문
• result는 전체 LIS 중 가장 긴 길이

---

🧠 5. 예제 시퀀스 흐름 설명

seq = {10, 1, 9, 2, 5, 7}

LIS(1) → 1, 2, 5, 7 → 길이 4
LIS(2) → 9만 남음 → 길이 1
LIS(3) → 2, 5, 7 → 길이 3
...
최종 정답: 4

• LIS(1) 경로는 최장 증가 부분 수열이므로 정답은 4

---

🧮 6. 시간 & 공간 복잡도 분석

항목	설명
시간 복잡도	O(N²) — 각 위치에서 다음 위치를 모두 탐색
공간 복잡도	O(N) — 캐시 배열 저장 용도

---