99클럽 코테 스터디2 -11일차(LIS)

🚨오늘의 학습🚨

문제: https://www.acmicpc.net/problem/11053
관련 : https://www.acmicpc.net/problem/11663

⭐️LIS (최대 증가 부분 수열)⭐️

원본 수열의 부분 수열 중에서 증가하는 형태의 수열을 찾는 문제.

✅ 동적 프로그래밍(DP)

• 원본 수열의 각 원소에 대해 현재까지 가능한 가장 긴 증가 부분 수열(LIS)을 계산하는 방식.
• 각 원소마다 LIS의 길이를 업데이트하며, 최대 LIS 길이를 추적.

✅ 이진 탐색

• 부분 수열에 값을 추가할 적절한 위치를 찾기 위해 사용.
• 현재 값이 기존 LIS에 추가될 위치를 이진 탐색으로 찾고, 해당 위치에 값을 갱신하거나 추가.
  - 🅾️ 부분수열에 중간에 끼워넣는 경우 : 하한 탐색 필요

※ 정렬된 배열을 유지하면서 새로운 숫자를 삽입할 수 있는 위치를 찾는 데 유용(상한선,하한선)

💡하한선_이진탐색(Lower_Bound)

• 목적 : 정렬된 배열내 목표값과 동일하거나 큰값 중 최소값/위치 찾기

public static int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {  // ✅ 종료 조건 (left == right)
        int mid = (left + right) / 2;
        if (arr[mid] >= target) {  // 🔥 target보다 크거나 같다면, 더 작은 mid를 찾아야 함
            right = mid;
        } else {  // 🔽 target보다 작으면 left 증가
            left = mid + 1;
        }
    }
    return left;  // 🎯 target 이상의 첫 번째 위치 반환
}

💡상한선_이진탐색(UpperBound)

• 목표 : 정렬된 배열 내 목표값과 동일하거나 작은값 중 최대값/위치 찾기

static int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] > target) {  // target 초과인 경우
            right = mid; 
        } else {
            left = mid + 1; // target 이하일 경우 오른쪽 탐색
        }
    }
    return left; // target 초과 값이 처음 등장하는 위치 반환
}

💡이진탐색(BinarySearch)

• 목적 : 정렬된 배열내 목표값 찾기