백준 3745번 오름세

문제

주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.

정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다.

n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다.

n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘: 최장 증가 부분수열

(0) 생각

 최장 증가 부분수열 문제입니다.
 보통 2가지 풀이가 생각되는데요,
    1. lower_bound 를 활용한 방법
    2. segtree 를 활용한 방법
 입니다. 둘 다 NlogN 의 시간복잡도가 나오겠네요.

1. lower_bound 이용한 풀이

(1) 코드 5

 이전의 증가 순열을 기록할 vector 하나가 필요합니다.

(2) 코드 14~17

 i번째 수를 탐색할 때,
    1. vector에 저장된 가장 큰 수 ( 가장 뒤에 수 ) 보다 큰 경우 vector 뒤에 i번째 수를 붙입니다.
    2. 그렇지 않은 경우 lower_bound 를 활용하여 vector에 i번째 이상의 수 중 가장 작은 수를 i번째 수로 바꿔줍니다.

(3) 코드 20

 탐색이 끝난 후 vector 의 크기가 구하고자 하는 최장 증가 부분수열 입니다.

(4) 이해

 이 코드가 왜 돌아가는지 예를 통해 생각해보겠습니다.
 Input:
 8
 1 6 2 5 7 3 5 6
 이 주어졌다고 생각해보겠습니다.

 먼저 vector 하나 만들어 놓습니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector

탐색 순서대로 가겠습니다.
( 탐색 중 vector에는 항상 오름차순으로 저장되게 될 수 밖에 없습니다. )

    1) 0번째 수를 보게 되면, vector는 비어 있기 때문에 그냥 넣어줍니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1

    2) 1번째 수를 보면, vector의 마지막 수보다 크니 vector에 추가해줍니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1	6

    3) 2번째 수를 보면, vector의 마지막 수보다 크지 않습니다.
       그렇다면 2번째 수보다 크거나 같은 수 중, 가장 작은 수를 찾아줍니다.
       이 경우 1번째 수인 6 이겠네요. 이를 2로 바꾸어 줍니다.
       이게 무슨 의미이냐면, 1, 6 이든 1,2 이든 길이 2인 증가 수열입니다.
       1,6 은 이후 6보다 큰 수가 있어야 길이 3인 증가 수열을 만들 수 있지만,
       1,2 는 이후 2보다 큰 수만 있으면 길이 3인 증가 수열을 만들 수 있습니다.
       따라서 6보다 더 유리한 2로 바꾸어주는 것입니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1	2

     이후는 위 과정의 반복입니다.
     4) 3번째 수를 보면 5 입니다. vector의 마지막 수보다 크니 붙여줍니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1	2	5

     5) 4번째 수를 보면 7이니 vector의 마지막 수보다 큽니다. 붙여줍니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1	2	5	7

     6) 5번째 수를 보면 3이네요. vector에서 3 이상의 가장 작은 수를 찾아줍니다.
        vector의 2번째 수 5가 3 이상의 가장 작은 수이네요. 이를 3으로 바꾸어줍니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1	2	3	7

    7) 6번째 수를 보면 5네요. vector의 3번째 수 7이 5 이상의 가장 작은 수 입니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1	2	3	5

    8) 7번째 수를 보면 6 입니다. vector의 마지막 수보다 크니 붙여줍니다.

	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6
Vector	1	2	3	5	6

 이로써 1 6 2 5 7 3 5 6 의 최장 증가 부분수열은 1 2 3 5 6 인걸 알 수 있습니다.
 길이는 5 겠네요.
 output:
 5

2. Segtree 를 이용한 풀이

아.... 설명이.... 귀찮네요...

설명이 너무 길어질 것 같아서 코드만 올려놓겠습니다...
혹시 풀이를 원하시는 댓글이 있다면, 풀이를 작성하겠습니다.
감사합니다.

세그먼트 풀이를 원하신다는 댓글이 있어서 풀이를 작성해보겠습니다.

기본적인 아이디어는 

주어진 수열 값을 작은 것부터 큰 순으로 보면서,

각 수열 값의 위치 이전에 자신보다 작은 수를 끝으로 하는 가장 긴 증가 수열 길이 +1 이

자신을 맨 끝 값으로 만드는 증가 수열 길이의 최대 값임을 생각해주는 것입니다.

이를 위해 각 위치가 만들 수 있는 최장 증가 수열 길이 값을 갖고, 

segtree로 큰 값을 쌓아줍니다.

우선 priority_queue를 이용해 주어진 수열을 pair<위치, 수열값> 으로 저장해줍니다.

값이 작은 것 우선, 값이 같다면 위치가 뒤인 것 우선으로 보게 끔 설정해줍니다.

 

예를들어 생각해보겠습니다.

Input:
 8
 1 6 2 5 7 3 5 6
 이 주어졌다고 생각해보겠습니다.

Index	0	1	2	3	4	5	6	7
입력	1	6	2	5	7	3	5	6

'seg[x] : x 위치의 수열 값을 맨 끝 값으로 하는 증가 수열의 최대 길이' 로 생각합니다.

초기 segtree는 모두 0으로 초기화 되어 있습니다.

(seg트리의 리프값들만 생각해보겠습니다.)

위치	0	1	2	3	4	5	6	7
Seg값	0	0	0	0	0	0	0	0

priority_queue에는 다음과 같은 순으로 쌓여 있습니다. 

<위치, 수열값>

< 0, 1 >    <- 제일 먼저 보는 pair

< 2, 2 >

< 5, 3 >

< 6, 5 >

< 3, 5 >

< 7, 6 >

< 1, 6 >

< 4, 7 >

    1) 위치 : 0 , 수열 값 : 1

    (이전에 segtree에 쌓인 정보가 없네요)

    위치 0 의 수열 값 1을 끝 값으로 하는 증가 수열 길이는 seg[0] = 0 + 1 = 1 입니다.

위치	0	1	2	3	4	5	6	7
Seg값	1	0	0	0	0	0	0	0

    2) 위치 : 2, 수열 값 : 2

    segtree로 위치 2 이전의 위치를 끝 값으로 하는 증가 수열들의 길이 중 최대를 찾습니다.

    위치 0을 끝으로 하는 증가 수열 길이가 1이고 이게 최대네요.

    따라서 seg[2] = 1 + 1 = 2 입니다.

위치	0	1	2	3	4	5	6	7
Seg값	1	0	2	0	0	0	0	0

    위 과정의 반복입니다.

    3) 위치 : 5, 수열 값 : 3

    이전 위치를 끝 값으로 하는 증가 수열들의 길이 중 최대 : 2 (seg[2] = 2)

    seg[5] = 2 + 1 = 3

위치	0	1	2	3	4	5	6	7
Seg값	1	0	2	0	0	3	0	0

    4) 위치 : 6, 수열 값 : 5

    이전 위치를 끝 값으로 하는 증가 수열들의 길이 중 최대 : 3 (seg[5] = 3)

    seg[5] = 3 + 1 = 4

위치	0	1	2	3	4	5	6	7
Seg값	1	0	2	0	0	3	4	0

     4) 위치 : 3, 수열 값 : 5

    이전 위치를 끝 값으로 하는 증가 수열들의 길이 중 최대 : 2 (seg[2] = 2)

    seg[3] = 2 + 1 = 3

위치	0	1	2	3	4	5	6	7
Seg값	1	0	2	3	0	3	4	0

     4) 위치 : 7, 수열 값 : 6

    이전 위치를 끝 값으로 하는 증가 수열들의 길이 중 최대 : 4 (seg[6] = 4)

    seg[7] = 4 + 1 = 5

위치	0	1	2	3	4	5	6	7
Seg값	1	0	2	3	0	3	4	5

    4) 위치 : 1, 수열 값 : 6

    이전 위치를 끝 값으로 하는 증가 수열들의 길이 중 최대 : 1 (seg[0] = 1)

    seg[1] = 1 + 1 = 2

위치	0	1	2	3	4	5	6	7
Seg값	1	1	2	3	0	3	4	5

    4) 위치 : 4, 수열 값 : 7

    이전 위치를 끝 값으로 하는 증가 수열들의 길이 중 최대 : 3 (seg[3] = 3)

    seg[4] = 3 + 1 = 4

위치	0	1	2	3	4	5	6	7
Seg값	1	1	2	3	4	3	4	5

따라서 위치 7을 (수열 값 : 6) 끝으로 하는 증가 수열이 길이가 가장 길고,

그 값은 5 임을 알 수 있습니다.

위에서 우리가 seg를 쌓을 때, 이전에 만들어 놓은 것 중에서 가장 긴 값 + 1을 해주었습니다.

이를 위해 priority_queue를 값이 작은 순, 값이 같다면 위치가 큰 순으로 설정한 것입니다.

부족하지만 도움이 된 설명이면 좋겠습니다....