Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 이진 리프팅(Binary Lifting)으로 접두사 합에서 X보다 크거나 같은 첫 번째 요소 찾기

문제 개요

N개의 숫자로 이루어진 배열 arr[]과 정수 값 X가 주어졌을 때, 이진 리프팅(Binary Lifting) 기법을 활용하여 배열의 접두사 합에서 X보다 크거나 같은 첫 번째 요소를 찾는 프로그램을 작성하는 것이 이번 문제의 목표입니다.

접두사 합(Prefix Sum)이란 원본 배열에서 각 인덱스까지의 모든 요소를 누적해서 더한 값을 요소로 갖는 배열을 의미합니다.

예시

array[] = {5, 2, 9, 4, 1}
prefixSumArray[] = {5, 7, 16, 20, 21}

문제 이해하기

예제를 통해 문제를 자세히 살펴보겠습니다.

입력: arr[] = {5, 2, 9, 4, 1}, X = 19
출력: 3

위 예제에서 접두사 합 배열은 {5, 7, 16, 20, 21}입니다. 값 19보다 크거나 같은 첫 번째 요소는 인덱스 3에 위치한 20이므로, 정답은 3이 됩니다.

해결 접근 방식

이 문제는 이진 리프팅(Binary Lifting) 개념을 활용해 해결할 수 있습니다. 이진 리프팅이란 주어진 숫자의 값을 2의 거듭제곱(비트를 뒤집는 방식으로 구현)만큼씩 증가시켜 나가는 기법으로, 0부터 log₂(N) 범위의 지수를 활용합니다.

이진 트리 리프팅과 유사한 아이디어를 적용하여, 먼저 인덱스 'P'의 초기값을 구합니다. 이때 비트를 하나씩 뒤집어 가되, 합이 X를 초과하지 않는 경우에만 값을 증가시킵니다. 이후 위치 'P'를 기준으로 리프팅을 진행합니다.

구체적으로는, i번째 비트를 뒤집었을 때 합이 X보다 커지지 않는 경우에만 해당 비트를 반영하며 탐색을 이어갑니다. 이 과정에서 'P'의 값에 따라 두 가지 경우로 나눌 수 있습니다.

  • i번째 리프팅으로 값이 증가했다면, 목표 위치는 'position + 2^i'와 'position + 2^(i+1)' 사이에 존재합니다.
  • 그렇지 않다면, 목표 위치는 'position'과 'position + 2^i' 사이에 존재합니다.

이 원리를 반복 적용하면 최종 인덱스 위치를 효율적으로 결정할 수 있습니다. 참고로 이 방법은 접두사 합 배열이 단조 증가한다는 전제(즉, 배열 요소가 음수가 아닌 경우)에서 올바르게 동작합니다.

알고리즘 단계

  1. 배열의 접두사 합 배열 prefSum[]을 생성합니다.
  2. 현재 위치 P를 0으로 초기화하고, LOGN을 log₂(n)으로 설정합니다.
  3. X ≤ prefSum[0]이라면 첫 번째 요소가 이미 조건을 만족하므로 0을 반환합니다.
  4. i를 LOGN부터 0까지 감소시키면서, P + 2^i < n이고 prefSum[P + 2^i] < X인 경우 P를 P + 2^i로 갱신합니다.
  5. 반복이 종료되면 P + 1을 반환합니다. 이 값이 조건을 만족하는 첫 번째 요소의 인덱스입니다.

구현 예제

아래 프로그램은 위에서 설명한 솔루션의 동작 과정을 보여줍니다.

#include <iostream>
#include <math.h>
using namespace std;

// 접두사 합 배열을 생성하는 함수
void generatePrefixSum(int arr[], int prefSum[], int n){
   prefSum[0] = arr[0];
   for (int i = 1; i < n; i++)
      prefSum[i] = prefSum[i - 1] + arr[i];
}

// 이진 리프팅으로 조건을 만족하는 첫 번째 인덱스를 찾는 함수
int findPreSumIndexBL(int prefSum[], int n, int x){
   int P = 0;
   int LOGN = log2(n);
   if (x <= prefSum[0])
      return 0;
   for (int i = LOGN; i >= 0; i--) {
      if (P + (1 << i) < n &&
         prefSum[P + (1 << i)] < x) {
         P += (1 << i);
      }
   }
   return P + 1;
}

int main(){
   int arr[] = { 5, 2, 9, 4, 1 };
   int X = 19;
   int n = sizeof(arr) / sizeof(arr[0]);
   int prefSum[n] = { 0 };
   generatePrefixSum(arr, prefSum, n);
   cout<<"주어진 숫자보다 크거나 같은 배열의 첫 번째 요소의 인덱스는 ";
   cout<<findPreSumIndexBL(prefSum, n, X);
   return 0;
}

출력 결과

주어진 숫자보다 크거나 같은 배열의 첫 번째 요소의 인덱스는 3

시간 복잡도 분석

이진 리프팅을 활용하면 탐색 단계마다 후보 범위가 절반씩 좁혀지므로, 처음부터 끝까지 순회하는 선형 탐색(O(N))보다 훨씬 효율적인 O(log N) 시간 복잡도로 답을 구할 수 있습니다. 접두사 합 배열을 생성하는 데에는 O(N)의 시간이 추가로 소요됩니다. 따라서 대규모 데이터에서 특정 임계값을 넘는 지점을 빠르게 찾아야 하는 상황에 이 기법이 특히 유용합니다.