알고리즘 스터디 18일차

목차

1. 세그먼트 트리

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

 

1. 세그먼트 트리

1. 트리 초기화하기

2² >= N을 만족하는 k의 최솟값을 구한 후 2² x2를 트리 배열의 크기로 정의 (문제를 풀면 더 쉽게 이해, 처음 리프노드를 해당 조건에 만족하게 만들어 놔야 합하면서 위로 올라갔을 때 노드가 부족하지 않음)

리프노드만 원본 배열이고 그 위는 전부 합배열(자식노드의 두 수를 합한 값 저장)

리프노드 이미지(0은 사용하지 않음)

구간합,최대,최소 3가지 케이스

위의 케이스(타입)별 트리 예제

2. 질의값 구하기

주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경

질의값 구하는 과정

3. 데이터 업데이트 하기

5번 데이터의 값을 7에서 10으로 업데이트 하는 예시, 5번 데이터의 인덱스를 리프노드인덱스로 변경하면 5+7=12이므로 12번 노드의 값이 업데이트

 

 

세그먼트 트리는 강의에서 강조한 것 처럼 코딩 테스트 문제를 풀면 많이 나오던데 이번에 공부를 해서 좋다.

문제를 풀때 트리는 크게 어렵단 생각을 못했지만 시간이 오래 걸렸는데 강의를 들으니 이론이 생각보다 어렵지만 이해하면 트리문제를 쉽게 풀 수 있을 것 같다.

나중에 내가 보기 위해 블로그를 쓰는 것이기 때문에 내가 알아보기 쉽게 적는데 이번엔 너무 학습교안의 내용만 가져온 것 같아서 혹여나 문제가 생긴다면 바로 삭제하겠습니다..