# 펜윅트리

2개의 포스트

펜윅트리 문제1 삽입정렬 시간 재기

문제 풀이 > 이 문제에는 세 가지 풀이가 있다. 1. 펜윅 트리 활용 > 펜윅 트리는 구간합을 간단하고 빠르게 구할 수 있는 자료 구조이다. 구간합을 활용해서 이 문제를 푸는 방법은 펜윅 트리의 크기를 문제에서 주어진 정수 범위로 하는 것이다. 모든 정수에 대해여 펜윅 트리를 만들고, 배열의 첫 원소부터 하나씩 갱신하면서 그 원소보다 큰 원소의 개수를 구...

2019년 7월 16일
·
0개의 댓글

펜윅트리

펜윅트리 > 배열의 구간합을 구하는 데는, 구간 트리를 활용할 수 도 있지만 그 구현이 복잡해 조금 더 단순한 형태인 펜윅트리를 사용하는 것이 더 좋다. 펜윅트리란 배열의 첫 몇 개의 원소인 부분합을 활용하면 구간합도 빠르게 계산할 수 있다는 원리에서 출발한 구조이다. image.png 펜윅트리의 구현 > 펜윅트리를 실제로 구현하기 위해서는 이진수를 활...

2019년 7월 16일
·
0개의 댓글