펜윅 트리
펜윅 트리(Fenwick Tree)가 뭘까요? 펜윅트리는 가장 낮은 비트(LSB)를 기반으로 트리를 만들어 동적배열에서 구간합을 효율적으로 구할 수 있는 자료구조입니다.또한 이진 인덱스 트리(Binary Indexed Tree, BIT)라고도 불립니다. 동적 배열이 뭘까요? 정적 배열은 배열의 요소들이 한번 선언되면, 바뀌지 않는 배열을 의미합니다.동적 배열은 동적으로 배열의 요소들이 바뀌는 배열을 의미합니다. 정적 배열과 동적 배열의 예시는 아래와 같습니다.정적 배열 : [10,20,30,40,50] 동적 배열 : [10,20,30,40,50] → [10,30,60,20,50] 백준에서는 아래와 같은 표현으로 동적 배열의 구간합을 구하라고 합니다."다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 ..
2025. 2. 23.
최대 증가 부분 수열
최대 증가 부분 수열(LIS)이 뭘까요? 최대 증가 부분 수열(Longest Increasing Sequence)은 오름 차순으로 증가하는 부분 수열 중 가장 긴 부분 수열을 의미합니다.하나의 예시를 통해서 알아보겠습니다.10 20 30 10 40 50 오름 차순으로 증가 하는 부분 수열 중 가장 긴 부분 수열은 어떻게 될까요? 10 20 30 20 40 50 [10,20,30,40,50]이 됩니다. 중간에 20이 있는데 오름 차순으로 증가하는 부분 수열이 아니지 않나요?10 20 30 20 40 50 [10,20]도 오름 차순으로 증가하는 부분 수열입니다. 어떤 부분 수열 배열이 최대 증가 부분 수열일까요? [10,20,30,40,50]은 길이가 5인 부분 수열이고, [10,20]은 길이가 2인 부분..
2025. 2. 22.
