팬윅트리 (2) 썸네일형 리스트형 [백준] 2243번 : 사탕상자 2243번: 사탕상자 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 🤔 문제분석 세그먼트 트리와 팬윅트리를 활용하여 문제를 해결하였습니다. 팬윅 트리 팬윅 트리로 문제를 해결 할때에는 이분탐색과 팬윅트리를 사용하여 문제를 해결하였습니다. 사탕의 순위를 누적합으로 계산시키고, 이분탐색으로 사탕을 찾아 나아 갑니다. 쿼리함수의 인자는 사탕의 가치가 되고 사탕의 가치를 입력하면 현재 그 사탕의 가치의 순위가 리턴 됩니다. 업데이트 함수는 사탕의 정보를 업데이트 합니다. 쿼리함수로 리턴받.. [백준] 5676번 : 음주코딩 5676번: 음주 코딩 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 📄 문제개요 구간곱을 구하는 문제로 쿼리의 개수가 10^5개로 N의 개수가 매우 크다면, 일반적인 쿼리로 문제를 해결 할 수 없습니다. “팬윅트리” 혹은 **“세그먼트 트리”**를 이용하여 문제를 해결 할 수 있습니다. 수열이 주어졌을때, 해당 곱이 “양수”인지 “음수”인지 “0”인지 판별해야합니다. 🤔 문제분석 세그먼트 트리로 문제 풀기. 세그먼트 트리로 문제를 풀경우 메모리는 최소 2^(log(N)+1), 최대 4N의 배열이 필요합.. 이전 1 다음
