구간합2 [백준 2042] 구간 합 구하기 Python 풀이 [백준 2042] 구간 합 구하기 Python 풀이📌 문제 분석이 문제는 구간 합을 구하는 문제로, 주어진 구간에 대한 합을 빠르게 구하고 특정 인덱스의 값을 업데이트하는 작업을 요구합니다.문제에서 제시된 대로, 구간 합을 빠르게 구할 수 있는 방법을 찾아야 하며, 세그먼트 트리를 활용하여 효율적으로 해결할 수 있습니다.🚨 시행착오처음에는 단순히 구간 합을 구하려고 했지만, 모든 구간을 매번 순차적으로 더하는 방식으로 접근했을 때 시간이 너무 오래 걸린다는 문제에 봉착했습니다.이 문제를 해결하려면, 세그먼트 트리를 사용하여 구간 합을 효율적으로 구하고 업데이트할 수 있어야 한다는 것을 깨달았습니다.처음 코드의 문제점구간 합을 계산하는 부분에서 중복 계산이 많아 비효율적이었습니다.세그먼트 트리의 구조를.. 2025. 3. 6. [Python] 세그먼트 트리 segment tree [세그먼트 트리] 세그먼트 트리 알고리즘 정리📌 세그먼트 트리란?세그먼트 트리는 배열의 구간 정보를 저장하여 구간 쿼리와 업데이트를 효율적으로 처리하는 자료구조입니다. 주로 구간 합, 최소값, 최대값 등을 O(log n) 시간 안에 계산할 수 있도록 도와줍니다.🚨 세그먼트 트리의 구조완전 이진 트리: 배열을 기반으로 한 완전 이진 트리 구조로 구현됩니다.노드 역할:리프 노드: 배열의 개별 원소를 저장합니다.내부 노드: 자식 노드의 값을 이용해 해당 구간의 정보를(예, 최소값 또는 합) 계산해 저장합니다.💡 주요 연산구간 쿼리: 특정 구간(예, [L, R])의 합 또는 최소/최대값을 O(log n) 시간 내에 계산할 수 있습니다.업데이트: 배열의 한 원소가 변경되었을 때, O(log n) 시간 안에 .. 2025. 3. 6. 이전 1 다음