소파와 바보개의 블로그

펜윅 트리 (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 과 같은 형태입니다. 이러한 원..

구간 쿼리 (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 } 라는 ..

슬라이딩 윈도우 (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)는 각각 부분배열의 시..

Longest Increasing Subsequence(LIS)? 가장 긴 증가하는 부분수열 혹은 가장 긴 감소하는 부분 수열을 찾는 것을 응용한 문제들이 있습니다. 이 문제는 최대 길이의 증가 또는 감소하는 부분 수열을 찾아야 합니다. 예를 들어 { 6, 2, 5, 1, 7, 4, 8, 3 } 과 같은 수열이 있다면, 이 수열의 LIS는 2 -> 5 -> 7 -> 8 이 됩니다. 감소하는 부분 수열을 구하는 방식은 증가하는 부분 수열과 동일한데, 구할 때 값만 음수로 처리해주면 됩니다. 예를 들어 위 수열을 { -6, -2, -5, -1, -7, -4, -8, -3 } 이라고 생각하고 LIS를 구하면 -6 -> -5 -> -1이 구해질테니 가장 긴 감소하는 부분 수열(LDS)은 6 -> 5 -> 1 입..

다이나믹 프로그래밍(Dynamic Programming)?다이나믹 프로그래밍(DP)는 완전 탐색의 정확성과 그리디 알고리즘의 효율성을 결합한 기법입니다. 다음 2가지 종류를 문제를 해결할 때 사용할 수 있습니다. - 최적의 답을 찾는 문제 : 가능한 최대값 혹은 최소값을 찾는 문제- 답의 갯수를 세는 문제 : 가능한 답의 총 갯수를 계산하는 문제 다이나믹 프로그래밍의 기본 아이디어는 간단하지만 다양한 문제에 응용될 수 있습니다.동전 문제 (Coin Problem)그리디 알고리즘을 사용하면 동전의 단위들이 주어지고 K원을 만들기 위한 최소 동전을 갯수를 세는 문제에서, 특정한 경우에만 문제를 해결할 수 있었습니다. 다이나믹 프로그래밍(DP)을 이용해 이 문제를 해결할 수 있습니다. 기본적으로 DP는 재귀함..

정규 허프만 코딩 (Canonical Huffman Coding)?허프만 코딩은 그리디 알고리즘을 이용해 자주 이용되는 문자는 짧은 코드를 가지고, 덜 이용되는 문자는 긴 코드를 가지는 효율적인 압축 알고리즘입니다. 2025.02.21 - [Competitive Programming] - 11. 허프만 코딩 (Huffman Coding, c++) - Greedy Algorithms 11. 허프만 코딩 (Huffman Coding, c++) - Greedy, Compression허프만 코딩 (Huffman Coding)?Huffman Coding은 무손실 데이터 압축 알고리즘으로, 주어진 string을 압축하기 위한 최적의 codeword를 그리디 알고리즘을 이용해서 만들어 냅니다. 자주 사용되는 문자가 ..

허프만 코딩 (Huffman Coding)?Huffman Coding은 무손실 데이터 압축 알고리즘으로, 주어진 string을 압축하기 위한 최적의 codeword를 그리디 알고리즘을 이용해서 만들어 냅니다. 자주 사용되는 문자가 더 짧은 codeword를 갖도록 구현됩니다. 이렇게 생성된 binary codeword는 다음 특징을 갖습니다. 1) 문자에 대한 binary codeword는 다른 문자의 prefix가 될 수 없습니다. 이를 통해 구분자(seperator)없이도 encoding, decoding을 수행할 수 있습니다. 2) 주어진 string에서의 문자 등장빈도 기반으로 구성하기 때문에 encoding 문자열의 길이가 최적화 됩니다. 자주 등장하는 문자가 짧은 codeword를 갖습니다.I..