Hyun's_Devlog

https://www.acmicpc.net/problem/2243

세그먼트트리 문제다. 접근방법이 떠오르지 않아 풀이를 찾아보았다.

풀이

1번 맛부터 1,000,000번 맛에 해당하는 사탕의 개수를 표현하는 세그먼트트리를 생성한다. 최대합 세그먼트 트리를 구현하면 된다.

고민할 부분은 문제의 요점인 i번째 순번의 사탕을 찾는 것인데, 해당 부분도 재귀호출을 통해 접근해야 한다. 부모노드부터 시작하여 좌측자식으로 탐색할지 우측자식으로 탐색할지 결정해야 한다. 만일 좌측노드의 값이 i이상이라면, 즉 좌측 노드에서 i번째 사탕을 찾을 수 있다면 그대로 좌측노드로 탐색을 시작하면 되고, 만일 좌측노드의 값이 i 보다 작다면, 즉 좌측노드에서 i번째 사탕을 찾을 수 없다면 우측노드로 탐색을 시도해야 하는데, 우측노드를 탐색한다는 뜻은 (i - 좌측노드의 값) 번째 사탕을 찾는다는 의미이다. 문제에서 현재 없는 사탕을 찾는 경우는 주어지지 않으므로 리프노드에 도달할 때까지 찾아야 할 사탕의 순번을 조절해서 탐색을 시도하면 된다.

예제를 기준으로 설명하면 다음과 같다.

0으로 초기화된 세그먼트 트리 생성 예제의 경우 큰 번호의 사탕이 나오지 않았기에 6번까지의 범위만 그렸다.

1번 사탕 2개 추가. 3번 사탕 3개 추가.

두 번째로 맛있는 사탕을 찾는다. 1번이 두 개 있기에 1번을 반환. 방문하는 모든 좌측노드가 2 이상이기에 1번 사탕까지 바로 접근. 사탕을 빼내는 작업이기에 방문한 리프노드에 도달할 때까지 방문한 모든 노드는 1만큼 차감해 준다.

이번에도 두 번째로 맛있는 사탕을 탐색, 0-3 범위에 도달할 때까지는 노드 값이 4이기에 좌측 노드 탐색.

이후에는 좌측 노드의 값이 1이므로 해당 노드에는 두 번째로 맛있는 사탕을 찾을 수 없다. 따라서 우측 노드 탐색 수행.

우측에서는 전체 범위에서 두 번째로 맛있는 사탕을 찾기 위해선 해당 범위에서 첫 번째로 맛있는 사탕을 찾아야 하기에 순번을 1로 변경하여 탐색을 진행하면 된다. 마찬가지로 방문했던 노드는 1 차감한다.

1번 사탕의 개수 변동. 마찬가지로 리프노드를 만날 때까지 변경 값을 반영하면 된다.

마지막으로 두번째로 맛있는 사탕 탐색. 위에서 탐색한 방법과 같은 방법으로 탐색 후 3번을 반환 후 방문했던 노드의 값 1을 차감한다.

정답 코드

https://www.acmicpc.net/problem/3745

최장증가 부분수열(LIS) 문제다. DP로 푸는 방법, 이분탐색을 이용하는 방법, 세그먼트 트리를 이용한 방법 총 세 가지 방법이 있다. 

지난번에는 이분탐색을 통해 문제를 풀어보았고 현재 세그먼트 트리를 공부 중이라, 이번에는 세그먼트 트리를 이용하여 접근해 보았다. 이분탐색 풀이와 마찬가지로 O(N*logN)의 복잡도로 풀 수 있다.

풀이

해당범위의 LIS의 길이를 담은 구간 최댓값 세그먼트 트리를 생성한다. 초기값은 0이다.

주가를 입력받을 때, (가격, 인덱스) 튜플형태로 입력받은 뒤, 주가를 기준으로 오름차순, 주가가 같다면 인덱스 기준 내림차순으로 정렬을 한다. 이후 정렬된 주가정보를 순차 탐색하면서 세그먼트 트리를 갱신해 주면 된다.

원리는 다음과 같다. 주가가 작은 값부터 탐색을 시작하기에 들어오는 정보 (주가, 인덱스)는 곧 0부터 인덱스 i까지의 최장증가 부분수열의 길이이며, 해당 수열에 입력된 주가 값을 덧붙이면(+1) 새로운 최장증가부분수열의 길이를 구할 수 있는 것이다.

예제 [5,2,1,4,5,3]을 기준으로 세그먼트를 완성시켜 보자.

가장 먼저 0으로 초기화된 세그먼트트리와 (값, 인덱스) 튜플형태를 정렬한 모습이다.

가장 먼저 인덱스 0-2 값을 조회, 길이가 0이고 여기에 배열의 가장 최솟값인 1을 붙여 길이가 1인 LIS길이가 생성된다. 해당 범위인 0-2까지의 LIS길이가 1이 되는 것이다. 따라서 0-2 범위를 1로 갱신하게 된다.

다음 값은 2이며 범위 0-1에 해당하는 값을 참고, 해당 수열에 2를 붙여 갱신하게 된다. 다음과 같은 작업을 반복하면 된다.

0-5 범위의 최장수열에 3을 붙여 길이 2인 최장수열이 생성된다. 해당 범위의 트리에 값 갱신.

0-3 범위 조회 후 갱신

0-4 범위 조회 후 갱신

가장 마지막으로 0-0 범위 조회 후 갱신

다음과 같은 과정으로 트리가 완성되며 문제에서 요구하는 전체 범위의 최장증가 부분수열의 길이는 루트 노드에 담겨있게 된다.

정답 코드

스위프트의 경우 입력 부분에서 제약이 생긴다. 라인이 분리되어서 주가가 입력되는 경우가 들어오게 되는데, 기본적인 입력으로는 해결하기 까다로워 보였다. 결국 해당 문제 질문 게시판에서 발견한 honghoker님의 글을 참고해서 입력을 처리하였다.

https://www.acmicpc.net/problem/12837

세그먼트트리 문제다.

풀이

구간합 문제와 동일하게 접근했으나 문제에서 오해하기 쉬운 요소가 있어 오답을 받았다. 1 쿼리의 경우 해당 구간의 정보를 변경하는 것으로 이해했으나, 그게 아닌 입력 값만큼 추가만 해주면 된다.

기본의 구간 합 문제의 경우 바꾸려는 인덱스가 포함된 범위를 탐색하면서 변경할 값과 기존값의 차를 트리에 반영했다면, 이번에는 새로 입력되는 값을 범위 내에 트리에 더해주기만 하면 된다.

정답 코드

https://www.acmicpc.net/problem/5676

세그먼트트리 문제다.

풀이

단순히 구간 곱 구하기 문제처럼 구하게 된다면 100¹⁰⁰⁰⁰⁰의 수를 담아야 하기에 오버플로우가 발생한다. 즉 해당 문제는 음수, 양수, 0인지 구하면 되는 문제이기에 입력되는 수를 1,0,-1 만으로 트리를 구성하여 결과를 출력하면 된다. 처음 문제를 읽었을 때 입력되는 수를 100 * 10⁵으로 판단하여 일반적인 구간 곱 형태의 트리로 접근하였다가 오답판정을 받았다. 

정답 코드

https://www.acmicpc.net/problem/18436

세그먼트트리 문제다. 값을 갱신하는 함수에 재귀호출을 해주지 않아 "틀렸습니다"를 연달아 받는 실수를 해버렸다. 항상 그렇듯이 사소한 실수를 해버리면 허탈하다.

풀이

(Int, Int) 튜플의 형태로 트리를 생성한다. 0번째에는 짝수의 개수, 1번째에는 홀수의 개수를 담아내는 트리다. 입력된 수열을 기준으로 세그먼트 트리를 생성한다. 이후 쿼리에 맞춰서 동작을 수행하면 된다.

수열을 수정하는 쿼리의 경우, 새로 갱신될 값이 기존의 값과 홀짝 유무가 같다면, 수열의 값만 바꾸어 주고 트리는 갱신할 필요가 없다. 반대로 짝수 -> 홀수 혹은 그 반대의 경우가 입력된다면 갱신을 해주면 된다. 이때 루트 노드에서 리프 노드까지 범위 안의 값들을 입력된 조건에 맞게 (+1,-1) 혹은 (-1,+1) 연산을 수행하면 된다.

출력 쿼리의 경우 범위에 해당하는 노드의 값을 통째로 반환받은 뒤, 조건에 맞게 짝수, 홀수의 개수를 출력해 주었다.

정답 코드

https://www.acmicpc.net/problem/14438

세그먼트트리 문제다.

풀이

구간의 최솟값이 담기는 세그먼트트리를 구현, 출력과 갱신을 담당하는 함수를 구현하여 접근하였다. 

예제를 기준으로 만든 세그먼트 트리다. 리프노드부터 더 작은 값을 부모노드로 결정하여 만들면 된다. 트리의 갱신을 하게 된다면 가장 먼저 리프노드 값의 갱신이 이루어지고, 해당 노드부터 루트노드까지의 대소비교를 진행하면서 새로운 값으로 갱신을 해주면 된다.

재귀호출을 통해 갱신이 이루어지는데, 해당 호출 범위가 갱신인덱스가 포함되지 않는 구간이라면, 바로 해당 노드의 값을 반환하여 반대편 구간과의 대소비교를 진행하면 된다.

정답 코드

https://www.acmicpc.net/problem/1306

세그먼트 트리 + 슬라이딩 윈도우 문제다.

풀이

세그먼트트리를 이용하여 구간별 최대값을 계산한다. 이후 홍준이의 위치를 포함한 앞 뒤 시야거리만큼의 범위로 구간별 최갯값을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/14428

세그먼트 트리 문제다.

풀이

기본적인 세그먼트 트리 문제다. 단, 이번에는 인덱스를 반환하는 것이 목적이므로, 각 노드에는 인덱스가 담기고, 노드의 값은 수열의 값을 비교하여 담아주면 된다. 

트리의 값을 읽어올 때, 인덱스가 1부터 시작하므로 수열의 맨 앞에 입력 가능한 범위 밖의 값인 1,000,000,001을 담는다. 이후 범위 밖의 값을 조회하게 될 때 0번 인덱스를 반환하여 대소비교에 영향을 주지 않게 한다.

트리의 갱신은 지난번 구간 곱 구하기 문제와 동일하게 수열의 값을 먼저 갱신한 뒤 정해진 구간 내의 리프노드부터 루트노드까지 트리의 갱신을 시도하면 된다.

정답 코드