이게 뭐야? 트리 종류 중에 하나이며, 연속된 구간(특정 범위)의 합(최솟값, 최댓값, 곱 등)을 구하는데 많이 쓰인다. 아래에서 선형구현과 비교하며 왜 쓰는지, 어떻게 사용하는지 gif를 준비해 놨으니 자세히 알아보자. 세그먼트 트리 문제 보기 문제 - 1 페이지 www.acmicpc.net 일단 결과부터 보자 입력된 수는 10의 7제곱이다. 10개의 데이터 [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]를 두고 구간 합을 구해본다. 예시 입력 : 1 10 예시 출력 : 55 선형 구현 O(N) 초기화 과정 O(N) ARRAY = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] for i in range(1,len(ARRAY)): ARRAY[i] += ARRAY[i-1] 1 3 6..

문제로 이동 목차 문제 설명 구간합 문제다. 이 게시물에서는 세그먼트 트리를 이용해 해결한다. 충분히 단순 반복문으로 해결할 수 있지만 그런 경우, 구간 합을 구하는데 O(n)이 걸린다. 이런 과정이 M번 반복된다면 O(MN)이 된다. 구간합 뿐만 아니라 특정 위치의 수를 변경시키는 기능도 있다. 해당 위치의 수가 바뀌면 그보다 큰 위치의 합도 모두 변경해야 하므로 TLE가 날 수 밖에 없다. 세그먼트 트리를 이용하면 O(Mlog(N))으로 해결할 수 있다. 소스 코드 소스코드 import sys input = sys.stdin.readline tree = list() nodes = list() #ChangeIdx : 수정할 인덱스, ChangeNum : 수정할 숫자 def update(start, en..

문제로 이동 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 목차 너무도 흔한 세그먼트 트리 문제이다. 하지만, 주의해야 할 부분이 몇 가지 있다. 주의해야 할 점 1. 구간곱 문제이므로 수가 커진다. 하지만, 이 문제에서는 음,양,0만 판별하면 되므로 모든 수를 -1, 0, 1로 바꿔준다. 2. 문제에 TC(테스트 케이스)가 주어지지 않았다. C++에선 while scanf 사용이 가능하지만 Python3에서는 다른 방법을 사용한다. TC가 주어지지 않는 경우 Python3에서는 Try - Except ..