Hyun's_Devlog

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번 인덱스를 반환하여 대소비교에 영향을 주지 않게 한다.

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

정답 코드

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

세그먼트 트리 문제다.

풀이

구간 합 구하기 문제와 다른 점은 세그먼트 트리의 갱신 부분에 주의할 부분이 있다는 점이다. 처음에는 단순히 기존값으로 나누고, 새로운 값으로 다시 곱해주면서 리프노드까지 도달하는 방법으로 접근했지만, 예제에서 알 수 있듯이 트리의 값이 0으로 바뀌게 되면 다음 갱신에 문제가 발생한다. 따라서 리프노드부터 먼저 갱신이 이루어지고, 루트노드까지 새로운 값으로 계산을 해주어야 한다. 

정답 코드

재귀호출 시에 범위를 반대로 적어 "틀렸습니다"를 연발했다.. 아는 유형의 문제라 방심했던 탓이다. 항상 집중해서 문제를 풀 것.

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

세그먼트 트리 문제다.

풀이

각 노드에 (Int, Int) 자료형을 통해 최솟값과 최댓값을 담는 세그먼트 트리를 생성하여, 각 구간별 최솟값과 최댓값이 담기는 세그먼트 트리를 생성하여 조건에 맞게 출력하면 된다.

[1,2,3,4,5] 배열을 기준으로 만든 세그먼트 트리다. 리프노드에는 동일한 값을 넣었다. 

트리를 읽어야 할 때는 구간에 해당하는 노드를 탐색, 각각의 최댓값과 최솟값을 비교하여 반환하면 된다.

해당 그림은 1 ~ 4번 인덱스 구간의 최솟값, 최댓값을 읽어올 때 참고하게 될 노드다.

범위 밖의 노드라면 입력 범위의 최댓값과 최솟값을 바꾸어 출력하게 하였다. ((1,000,000,000, 1) 리턴)

정답 코드

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

세그먼트 트리 기본문제다. 

풀이

세그먼트 트리란 구간합을 이진트리의 형태로 구현한 자료구조이다. 부모노드에는 두 자식노드의 총합이 담기며, 두 자식노드는 중간을 기준으로 좌측 범위의 총합, 우측 범위의 총합의 형태로 나뉜다. 그림으로 보는 것이 이해하기 더 쉬울 것이다.

크기 5인 배열의 세그먼트 트리의 구조다. 각 배열의 값이 리프노드에 담기며, 부모 노드로 구간 합을 계산하여 루트에는 배열의 총합이 담기게 된다.

예제 [1,2,3,4,5] 배열의 세그먼트 트리를 그려보면 다음과 같이 만들어진다. 세그먼트 트리의 경우 구간합의 변경에 굉장히 용이하다. 그 이유는 바로 트리구조에서 오는 접근성 때문인데, 부모 노드를 기준으로 두 배를 하면 좌측 자식 노드, 거기에 1을 더하면 우측 자식 노드에 접근이 가능하기 때문이다. 따라서 루트 노드는 0이 아닌 1부터 시작하며 기본적으로 해당 구조의 재귀호출을 통해 구간합의 변경과 조회가 이루어진다.

1번 ~ 4번 인덱스까지의 구간합을 구하게 된다면 좌측 그림과 같이 해당 구간에 접근하여 계산이 이루어진다. 사실 누적합을 이용해서 푼다면 O(1)만에 계산이 가능하지만, 자료의 변경이 일어난다면 처음부터 누적합을 다시 구해야 하기에, 결국 자료의 크기가 N일 때 O(N)시간이 걸리게 된다. 세그먼트 트리의 경우 우측 그림과 같이 조회뿐만 아니라 루트에서 해당 구간 만의 접근을 통해 변경이 가능하기에 O(logN)시간만에 해결이 가능하게 된다. 해당 문제의 경우 구간의 변경이 빈번하게 이루어지기에 세그먼트 트리의 구현을 요구하는 문제인 것이다.

정답 코드