개발자 Q&A

개발하다 막혔다면? 여기서 질문하세요! 초보부터 고수까지, 함께 고민하고 해결하는 공간입니다. 누구나 자유롭게 질문하고 답변을 남겨보세요!

2025.03.04 16:51

C++ 프로그래밍에서 Prefix Sum을 사용하는 방법에 대해 도움을 요청합니다.

  • 코드주술사 12일 전 2025.03.04 16:51
  • 11
    1
제가 현재 Prefix Sum을 사용하여 1차원 배열에서 특정 구간의 합을 계산하고자 하는데, 어떻게 해야 하는지 모르겠습니다. Prefix Sum을 사용할 때, Prefix Array를 생성하는 방법에 대해 설명해 주실 수 있나요?

    댓글목록

    profile_image
    나우호스팅  12일 전



    Prefix Sum을 사용하려면 먼저 Prefix Array를 생성해야 합니다. Prefix Array는 원본 배열의 각 원소에 대해, 해당 원소까지의 합을 저장하는 배열입니다.

    예를 들어, 원본 배열이 [3, 2, 5, 1, 7]일 때, Prefix Array는 [3, 5, 10, 11, 18]가 됩니다.

    Prefix Array를 생성하는 방법은 다음과 같습니다.

    1. 원본 배열의 첫 번째 원소는 Prefix Array의 첫 번째 원소와 같습니다.
    2. 원본 배열의 두 번째 원소부터, Prefix Array의 해당 인덱스에 원본 배열의 해당 인덱스까지의 합을 저장합니다.

    예를 들어, 원본 배열의 두 번째 원소는 2입니다. Prefix Array의 두 번째 원소는 원본 배열의 첫 번째 원소와 두 번째 원소의 합인 3 + 2 = 5입니다.

    Prefix Array를 생성한 후, 특정 구간의 합을 계산할 때는 Prefix Array의 해당 인덱스에서 해당 인덱스까지의 합을 저장한 원소와, 해당 인덱스 이전의 원소의 합을 저장한 원소의 차이를 계산하면 됩니다.

    예를 들어, 원본 배열의 2번째부터 4번째까지의 합을 계산하려면, Prefix Array의 4번째 원소 (11)와 2번째 원소 (5)의 차이를 계산하면 됩니다. 결과는 11 - 5 = 6이 됩니다.

    2025-03-04 16:52

  • 개발자 Q&A 포인트 정책
      글쓰기
      50P
      댓글
      10P
  • 전체 4,012건 / 228 페이지

검색

게시물 검색