[백준] 2042: 구간 합 구하기 - JS (펜윅트리(BIT))

목 차 문제 접근 방식 풀이 문제 접근 방식 펜윅 트리는 구간 합을 구하는 것에 특화되어 있는 자료구조 이다. 펜윅 트리를 구성하는 메서드는 update 와 sum 메서드 이다. update // x: 업데이트 하는 인덱스, diff: 원래 값과 바뀐 값의 차이 인자: x, diff 조건: x 0 동작: 인자로 들어온 x 에서 x & -x 를 빼주고 반복하면 1 부터 x 까지의 합을 구할 수 있다. 구간 합은 sum(b) - sum(a - 1) 을 해주면 구할 수 있다. 세그먼트 트리 보다는 구현이 쉬웠는데 범용성이 아쉽다. 구간 합 문제에서 편하게 사용할 수 있을 것 같다. 펜윅 트리를 구현하며 배운 것들 펜윅 트리를 위한 글에서 캡쳐하였다. 풀이 class FenwickTree { // N: 요소 개..

Algorithm 2023.12.07

[백준] 2042: 구간 합 구하기 - JS (세그먼트 트리)

목 차 문제 접근 방식 풀이 문제 접근 방식 세그먼트 트리를 구성하는 3가지 메서드는 initTree, update, sum 메서드이다. initTree 메서드: for문을 사용해서 구현했다. 아직 재귀를 사용하기보다는 for 반복문이 더 편하기 때문이다. 트리를 처음에 초기화 하는 메서드이다. 원본 배열을 가져와서 마지막 레벨 트리에 붙여 넣고, 그리고 하나씩 내려가며 자식들을 더한 값을 저장한다. update 메서드: 변경 된 리프노드를 시작으로 부모를 타고 올라가며 전체적인 트리를 업데이트한다. 세그먼트 트리에서 가장 간단하게 구현할 수 있는 메서드라고 생각한다. sum 메서드: 구간 합을 구하는 메서드이다. 재귀를 이용해서 구현한다. sum 메서드를 구현할 때 참고하면 좋은 3가지가 있다. 구해야..

Algorithm 2023.12.07