2023.05.17 - [PS] - [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 ※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지 kangmanjoo.tistory.com 지난 포스팅에 이어, 다시 한 번 세그먼트 트리로 돌아왔다. 세그먼트 트리는 특정 구간의 합, 곱, 최솟값, 최댓값을 찾을 때 일반적인 배열에서 찾을 때보다 훨씬 빠른 O(logN)의 시간복잡도를 가진다고 하였다. 그렇다면 세그 트리는 무적이고 나는 신인가? 물론 아니다. 세그트리에도 치명적인 단점이 존재하는데, 바로 값의 ..

※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지나면 기억이 휘발되어 다시 포스팅들을 찾아보고 있는 내 모습이 너무 바보같았다. 그래서 이왕이면 내가 쓴 글을 보고 다시 떠올리자! 하는게 재습득하기도 제일 빠르고 나에게도 도움이 더 될 것같아, 이곳에 정리하기로 결정했다! 오늘 학습한 자료구조는 바로 세그먼트 트리 도대체 세그먼트 트리는 어디에서 활용이 되는 자료구조인가? 가장 대표적으로 활용이 되는 곳은, 바로 구간합을 구할때이다. INDEX 0 1 2 3 4 5 6 7 VALUE 2 1 7 8 5 4 3 1 위와 같은 테이블이 있다고 하자. 이 배열에서 ..

첫 플래티넘 3 솔브다 !! 세그먼트 트리를 활용하는 자료구조 중 재밌는게 없나 찾던 중, 머지 소트 트리라는 이름만 들어도 흥미로운 태그를 찾았다. 심지어 수열과 쿼리 '1' 이라니 안풀 수가 없잖아 ! ❓머지 소트 트리(Merge Sort Tree)란? 일반적인 세그먼트 트리구조란, 해당 구간의 특징 (구간합이든, 최솟값이든.. 등등)을 각 범위를 지칭하는 노드에 저장을 한다. 머지 소트 트리도 마찬가지로, 특정 범위의 value들의 정렬 상태인 배열을 노드에 저장을 하는 구조이다. 사실 세그먼트 트리에 익숙하다면 크게 어렵지 않게 풀 수있다. 이번 문제에서는 개념을 묻는 느낌이라 갱신을 안해서 갱신부분은 고려를 안해보았는데, 이를 다루는 문제들도 풀어보면 좋을 듯싶다. 이 문제에서 한 번 실수했던 ..