소파와 바보개의 블로그

펜윅 트리 (Fenwick tree)?펜윅 트리 또는 Binary indexed tree는 prefix sum array의 변형으로 볼 수 있습니다. 이 자료구조는 구간의 합을 구하는 연산과 배열의 값을 변경하는 연산을 각각 O(logN)에 처리할 수 있습니다. 펜윅 트리의 이점은 구간의 합을 구하는 쿼리 중에도 효과적으로 배열의 값을 변경할 수 있다는 것이고 이 것은 일반적인 prefix sum array로는 처리하지 못합니다.구조tree라는 이름에서 알 수 있듯이 1차원 배열로 쉽게 표현할 수 있습니다. 구현의 용이성을 위해 펜윅 트리에서는 배열의 인덱스를 0이 아닌 1부터 시작합니다. k는 배열의 인덱스입니다. p(k)를 k를 나누는 가장 큰 2의 거듭제곱으로 정의합니다. 이진수에서 가장 우측에 존..

희소 배열 (Sparse table)?앞서 구간에 대한 합계를 Prefix Sum을 이용해 계산을 했다면, 구간에 대해 최소값 또는 최대값을 계산하는 것은 조금 더 복잡한 문제입니다. Sparse table 을 이용하면 O(nlogn)의 전처리 이후 구간에 대한 최소값과 최대값을 구하는 것을 O(1) 시간복잡도로 수행할 수 있습니다. Sparse 라는 단어는 가능한 모든 구간을 저장하는 것이 아니라, 2의 거듭제곱 길이의 구간만 저장하기 때문에 붙여진 이름입니다. 모든 정수는 2의 거듭제곱을 한번씩 사용해서 표현할 수 있습니다.  당연하게도 모든 정수들은 이진수로 표현할 수 있고 7은 111, 9는 1001 이기 때문입니다.  예를 들면, 7은 4+2+1 이고 9는 8+1 과 같은 형태입니다. 이러한 원..

[백준/BOJ] 2532 먹이사슬 (c++) 2532번: 먹이사슬 2025.03.04 - [Competitive Programming] - 14. Longest Increasing Subsequence (LIS, c++) 14. Longest Increasing Subsequence (LIS, c++)Longest Increasing Subsequence(LIS)? 가장 긴 증가하는 부분수열 혹은 가장 긴 감소하는 부분 수열을 찾는 것을 응용한 문제들이 있습니다. 이 문제는 최대 길이의 증가 또는 감소하는 부분 수열을 찾아dnsldprp.tistory.comN마리의 동물이 있고 동물들의 활동 영역이 주어집니다. 만약 A라는 동물의 활동영역에  B라는 동물의 활동영역이 포함된다면 A는 B보다 먹이사슬에서 ..

[백준/BOJ] 2167 2차원 배열의 합 (c++) 2167번: 2차원 배열의 합 2025.03.19 - [Competitive Programming] - 18. 구간 쿼리, 구간 합 (Range queries, Prefix sum, c++) 18. 구간 쿼리, 구간 합 (Range queries, Prefix sum, c++)구간 쿼리 (Range queries)?구간에 대한 쿼리에서는 배열의 부분 배열들을 기반으로 어떠한 값들을 계산합니다. 예를 들면 [a, b] 구간의 합계를 구한다던지, [a, b] 구간에서의 최솟값을 구하는 경우dnsldprp.tistory.com2차원 배열에서의 구간합을 구하는 문제입니다. a[i][j] 를(1,1) 에서부터 (i, j) 까지의 사각형 범위의 합계라고 정의한다..

구간 쿼리 (Range queries)?구간에 대한 쿼리에서는 배열의 부분 배열들을 기반으로 어떠한 값들을 계산합니다. 예를 들면 [a, b] 구간의 합계를 구한다던지, [a, b] 구간에서의 최솟값을 구하는 경우들이 있고, 이러한 종류의 연산들을 효과적으로 처리할 수 있는 자료구조들이 있습니다.Prefix Sum구간에 대한 합계를 구하는 연산은 미리 계산된 prefix sum array를 통해 쉽계 계산할 수 있습니다. prefix sum array의 각각의 요소들은 원본 배열에서의 해당 위치까지의 합계입니다. 따라서, prefix sum array를 만드는 과정은 단순히 이전까지의 값에 현재 값을 더하는 것으로  O(N)에 수행됩니다. 예를 들어 { 1, 3, 4, 8, 6, 1, 4, 2 } 라는 ..

[백준/BOJ] 1306 달려라 홍준 (c++) 1306번: 달려라 홍준 2025.03.10 - [Competitive Programming] - 17. 슬라이딩 윈도우 (Sliding window, c++) 17. 슬라이딩 윈도우 (Sliding window, c++)슬라이딩 윈도우 (Sliding window)?슬라이딩 윈도우는 고정 크기의 부분배열을 배열의 왼쪽에서 오른쪽으로 이동시키는 방법입니다. 슬라이딩 윈도우의 각 위치에서 부분 배열에 대한 정보들을 계dnsldprp.tistory.com총 칸 수 N과 시야의 범위 M 이 주어질 때 시야 범위 내에서 가장 강력한 빛의 크기를 구하는 문제입니다. M 크기의 슬라이딩 윈도우를 사용해 O(N)에 문제를 해결할 수 있습니다. 왼쪽에서 오른쪽으로 배열을..

슬라이딩 윈도우 (Sliding window)?슬라이딩 윈도우는 고정 크기의 부분배열을 배열의 왼쪽에서 오른쪽으로 이동시키는 방법입니다. 슬라이딩 윈도우의 각 위치에서 부분 배열에 대한 정보들을 계산할 수 있습니다. 특정 길이(슬라이딩 윈도우의 크기)가 주어지고  배열의 모든 특정 길이의 부분배열에 대해 그 배열에서의 가장 작은 값을 구하는 문제가 있습니다. 예를 들어 { 2, 1, 4, 5, 3, 4 } 라는 배열이 있고 슬라이딩 윈도우의 크기가 3라면 { 2, 1, 4 } 의 최소값, { 1, 4, 5 }의 최소값...을 계산해야 합니다. 이 문제는 Nearest smaller elements와 유사한 접근방식을 사용해 해결할 수 있습니다. 이번에도 왼쪽에서 오른쪽으로 탐색을 하고 Deque를 사용해..

가장 가까운 작은 값 (Nearest smaller elements)? 배열의 모든 요소에 대해서 앞에 있는 값들 중 가장 가까이에 위치한 작은 값을 찾는 문제입니다. Stack을 이용해서 이러한 문제들을 효과적으로(O(N)) 해결할 수 있습니다. 왼쪽에서 오른쪽으로 배열을 탐색할 것인데, Stack을 이용해 특정 요소들을 관리할 것입니다. 배열의 각 인덱스에 대해서, Stack의 값과 비교해 자신보다 큰 값들을 모두 제거합니다. Stack이 비어있게 되거나 Stack의 top 요소가 자신보다 작다면 제거하는 작업을 중단합니다. 그렇다면 Stack의 top 요소가 nearest smaller element 입니다. 이후 자신의 값을 Stack에 추가하고 이 작업을 반복합니다. { 1, 3, 4, 2, 5..

투 포인터 (Two pointers method)?개별적인 연산에 중점을 두지 않고 알고리즘이 실행되는 전체 시간을 측정하는 방식 중의 하나입니다. 두개의 포인터로 배열의 값들을 순회하는 방법으로, 두 포인터는 한방향으로 움직일 수도 있고 서로 반대방향으로 움직일 수도 있습니다.Subarray sum n개의 양의 정수로 이루어진 배열이 있고 x 라는 값을 만들 수 있는 부분 배열을 찾는 문제가 있습니다. 예를 들면, { 1, 3, 2, 5, 1, 1, 2, 3 } 이라는 배열이 있고 여기서 8을 만들 수 있는 subarray를 찾아야합니다. 이러한 문제는 모든 부분 배열을 검사하지 않아도, 투 포인터로 O(N)에 해결할 수 있습니다. 이 문제에서 두개의 포인터(left, right)는 각각 부분배열의 시..

[백준/BOJ] 12846 무서운 아르바이트 (c++) 12846번: 무서운 아르바이트 2025.03.10 - [Competitive Programming] - 16. 가장 가까운 작은 값 (Nearest smaller elements, c++) 16. 가장 가까운 작은 값 (Nearest smaller elements, c++)가장 가까운 작은 값 (Nearest smaller elements)? 배열의 모든 요소에 대해서 앞에 있는 값들 중 가장 가까이에 위치한 작은 값을 찾는 문제입니다. Stack을 이용해서 이러한 문제들을 효과적으로 해결dnsldprp.tistory.com10만개의 일급 정보가 주어져 있을 때 몇일을 연속으로 일했든 가장 작은 일급*일한 날짜로 급여가 지급됩니다. 이 때, 최대로..