prefix sum만이 누적합이 아니다1 - value 누적합

1. 문제 28449번: 누가 이길까 (acmicpc.net) 28449번: 누가 이길까 HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다. HI팀엔 $N$명 ARC팀엔 $M$명이 속해있다. 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 $N \times M$개 www.acmicpc.net 2. 풀이 n명의 리스트 A를 오름차순 정렬, m명의 리스트 B를 오름차순 정렬하고 A의 모든 원소 A[i]에 대하여, 리스트 B에서 lower bound와 upper bound를 찾아서 lower bound 밑으로는 A[i]보다 작은 수들이니까 A의 승리이고, upper bound 위로는 A[i]보다 큰 수니까 B의 승리 lower bound와 upper boun..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 4. 10.
• textsms

binary indexed tree(BIT, fenwick tree) 간단하게 배우기

1. 구조 binary indexed tree는 이름에서부터 2진법 인덱스 구조를 이용해서 구간 합 문제를 효과적으로 처리하기 위한 자료구조 point update, range sum을 효과적으로 처리하기 위한 자료구조 다음 그림이 binary indexed tree의 구조를 잘 보여주고 있다. 1) zero index가 아니라 binary indexed tree에서는 편의상 one index로 바꿔서 생각함 2) 데이터가 N개면 tree의 크기도 N이다. 3) tree의 각 index에는 어떤 값들이 저장되어 있는가? 1번 index에는 0번째 원소 1이 있고, 2번 index에는 0번 + 1번째 원소의 합 1+3 = 4가 저장 마찬가지로 3번 index에는 2번째 원소 11이 저장 4번 index에는..

• format_list_bulleted 세그먼트 트리
• · 2024. 2. 13.
• textsms

누적합 응용 - prefix/suffix min/max 배열 이용한 테크닉

1. 문제 29726번: 숏코딩의 왕 브실이 (acmicpc.net) 29726번: 숏코딩의 왕 브실이 숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 $A_1, A_2, \cdots, A_N$로 주어진다. 브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열 www.acmicpc.net 2. 풀이 $$\sum_{i = 1}^{L-1} A_{i+1} - A_{i} = A_{L} - A_{1}$$ 을 관찰하는 것은 어렵지 않다. 주어진 합은 배열을 알면 양쪽 끝의 두 원소만을 이용해서 구할 수 있다. 이 의미는, $A_{1}, A_{2}, A_{3}, ... , A_{N}$이 주어질때, 중간의 원소 $A_{2}, A_{3}, ... ,A_{N-1}$는 ..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 2. 12.
• textsms

ABC 337 D번 복기 - 2차원 배열에서 행,열로 연속한 O의 개수를 빠르게 세는 방법(sliding window + prefix sum)

D - Cheating Gomoku Narabe (atcoder.jp) D - Cheating Gomoku Narabe AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp . o x로 이루어진 2차원 배열에서 .을 o로 바꿀 수 있다. 이 때 행이나 열로 연속한 o의 개수가 k개가 되도록 최소로 바꾸는 횟수 처음에 DFS로 o의 좌표에서 시작해서 .을 o로 바꿔서 해보다가 당연히 시간초과났고 그러다가 행이나 열 각각에서 모두 조사해보면 된다는 생각이 들었다 여기까지는 좋았음 행 한줄에서 어떻게 .을 o로 바꿔야 연속한 o의 ..

• format_list_bulleted Atcoder
• · 2024. 1. 21.
• textsms

ABC 334 복기 - 배열에서 원소 하나를 제거해서 두 원소 절댓값 차이의 합을 최소로 만들기(prefix sum, suffix sum)

1. 문제 C - Socks 2 (atcoder.jp) C - Socks 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 N쌍의 양말이 있는데, 이 중 지정된 K개의 양말은 각각 1개를 잃어버린 상태이다. 양말의 색을 1,2,3,...,N으로 표시할때, 현재 상태에서 적절하게 짝을 짓는다. 짝지은 양말이 i번째 색, j번째 색일때 |i-j| 의 value를 가진다. 모든 짝의 value합이 최소가 되도록 만든다면? 양말의 개수 2N-K가 짝수라면 상관없지만 홀수라면 1개를 제외하고 짝을 지어야한다. 직관적으..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 1. 1.
• textsms

고난이도 자료구조 세그먼트 트리 개념 이해하기 1편

1. 특정한 구간에 존재하는 모든 수의 합 어떤 수열이 주어질때, 만약 특정 구간 [a,b]에 존재하는 모든 수의 합을 구하라고 한다면 어떻게 구할 수 있을까? 가장 쉬운 방법은, 그냥 반복문으로 [a,b]까지 돌아서 모든 수의 누적합을 구하면 된다 answer = 0 for i in range(a,b+1): answer += A[i] 만약 배열 A의 크기가 N일때, 최악의 경우 위 코드의 시간 복잡도는 O(N)이다. 1번부터 N번까지 다 더하라하면 O(N)이니까 여기까지는 괜찮은데 만약 이러한 질문을 M번이나 한다면? O(N)의 연산을 M번 수행해야하므로, 시간복잡도는 O(NM)이고 N,M이 매우 크다면, 당연히 매우 느리다 2. Prefix sum 만약 S[0] = 0이고, 1번부터 i번까지의 수열 ..

• format_list_bulleted 세그먼트 트리
• · 2022. 12. 5.
• textsms