Gliver
알고리듬
Gliver
ally.coding@gmail.com
전체 방문자
오늘
어제
  • 분류 전체보기 (63)
    • ✏️ 알고리즘 (43)
      • 필독⭐ (2)
      • 기본 알고리즘 (7)
      • 필수 알고리즘 (6)
      • 그래프 알고리즘 (6)
      • PS 기록 (22)
    • 📐 Math (7)
      • Linear Algebra (7)
    • 📁 About .. (5)
      • About AI (0)
      • About CS (0)
      • About Develope (2)
      • 알아두면 좋은 내용들 (3)
    • 📜 기록 (2)
      • 컴공 학부생 4년 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • python
  • 알고리즘 강의

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Gliver

알고리듬

강의 대표 이미지
이 글의 저자가 직접 가르치는 강의가 보고 싶다면?
⭐️ 24시간 만에 코딩테스트 정복하기 ⭐️
✏️ 알고리즘/PS 기록

[백준 12015번] 가장 긴 증가하는 부분 수열2 - 세그먼트 트리

2023. 3. 27. 11:36

 

12015번: 가장 긴 증가하는 부분 수열 2

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net


 

목차

  • 사전 지식
  • DP 풀이
  • 세그먼트 트리 풀이

 

가장 긴 증가하는 부분 수열 문제는 LIS(Longest Increasing Subsequences)로 잘 알려진 문제이다.

이번 글에서는 LIS 문제를 세그먼트 트리를 이용하여 풀어보겠다.

 

 

사전 지식

  • LIS의 DP(Dynamic Programming) 풀이를 이해해야 한다. (링크)
  • 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)

 

 

 

DP 풀이 - $\scriptsize{O(N^2)}$

LIS를 푸는 가장 잘 알려진 방법은 DP를 이용하는 것이다.

배열의 각 원소를 탐색하며, 현재 원소를 끝으로 하는 가장 긴 LIS를 구하는 방법이다.

arr[i]: 인덱스가 i인 원소
dp[i]: 인덱스가 i인 원소로 끝나는 LIS 길이

dp[i]를 구하는 법은 인덱스 1부터 i-1까지 살펴보며 아래와 같은 코드로 구할 수 있다. (인덱스는 1부터 사용한다)

for (int i=1; i<=N; i++) {
   int best = 0;
   for (int j=1; j<i; j++) {
      if (arr[j] < arr[i]) best = max(best, dp[j]);
   }
   dp[i] = best + 1;
}

 

 

 

세그먼트 트리 풀이 - $\scriptsize{O(N \cdot \log N)}$

이 풀이는 DP 풀이의 논리는 비슷하지만, dp[i]를 갱신하는 과정이 $\log N$ 시간에 수행 가능하다.

 

세그먼트 트리의 리프 노드 인덱스는 배열의 인덱스가 아닌 원소들의 값에 대응되고,

리프 노드에 들어 있는 값은 (dp 풀이와 비슷하게) 그 값을 끝으로 하는 LIS 길이가 들어있다.

 

이렇게 구성하면 어떤 원소보다 작은 원소들 중에서 최대값을 세그먼트 트리를 이용하여 바로 구할 수 있다!

 

 

 

'✏️ 알고리즘 > PS 기록' 카테고리의 다른 글

[백준 25639번] 수열과 최대 상승 쿼리  (2) 2023.03.29
[백준 2336번] 굉장한 학생  (2) 2023.03.27
[AtCoder] ABC295 A~D 업솔빙  (2) 2023.03.26
2022 ICPC Seoul Regional 후기  (4) 2022.12.21
2022 ICPC Seoul Regional 예선 후기  (4) 2022.10.10
    '✏️ 알고리즘/PS 기록' 카테고리의 다른 글
    • [백준 25639번] 수열과 최대 상승 쿼리
    • [백준 2336번] 굉장한 학생
    • [AtCoder] ABC295 A~D 업솔빙
    • 2022 ICPC Seoul Regional 후기
    Gliver
    Gliver

    티스토리툴바