💕
후원
본문 바로가기

Algorithm/Algorithm8

[알고리즘] 모스 알고리즘 모스 알고리즘(Mo's algorithm)은 오프라인(쿼리의 순서가 상관 없는) 구간 쿼리를 처리할 때 유용한 알고리즘으로, 간단히 소개하면 길이 N인 구간을 √N개 구간으로 쪼개고, 미리 쿼리들을 정렬해서 O(n√n)의 시간복잡도로 쿼리를 처리하는 알고리즘입니다. 우선 길이 N인 구간을 각 √N개의 원소를 가진 버킷(bucket)으로 쪼갭니다. 각 쿼리들은 시작점이 더 앞쪽의 버킷에 속하고, 끝점이 더 앞쪽에 있는 쿼리부터 처리해주면 됩니다. 간단히 쿼리의 정렬 함수를 수도코드로 표기하면 이렇게 될 것입니다. bool cmp(query a, query b) { if (a.start/sqrt(n) < b.start/sqrt(n)) return true; else if (a.start/sqrt(n) == .. 2023. 5. 18.
[알고리즘] 허프만 코딩 허프만 코딩 원본 데이터에서 자주 출현하는 문자를 적은 비트, 출현 빈도가 낮은 문자를 많은 비트로 부호화해 데이터를 효과적으로 압축하는 방법입니다. $C$를 $n$개의 문자로 이루어진 집합으로 두고 $c\in C$, $c.freq=c$의 빈도 수라고 둡니다. $Q$라는 $freq$가 key인 최소 우선순위 큐도 둡니다. HUFFMAN(C) n = |C| // n은 C의 크기 Q = C // Q를 C에 대해 초기화 for i=1 to n-1 let z = new node; // 새로운 노드 z 할당 z.left = x = EXTRACT_MIN(Q) // Q에서 최소 노드를 뽑아 x, z.left에 할당 z.right = y = EXTRACT_MIN(Q) // Q에서 최소 노드를 뽑아 y, z.right에.. 2021. 12. 16.
[알고리즘] 좌표 압축 치토스 선배 강의 듣고 씀. 좌표 압축 좌표의 범위가 막 ≤ 1,000,000,000으로 큰 경우가 있다. 이런 경우에 arr[1000000000] 같은 배열을 선언하면 당연히 터져버린다. [BOJ] 가로 블록 쌓기 문제 같은 경우 0 ≤ Wi + Di ≤ 2,000,000,000로 좌표 자체의 범위는 크지만, 들어오는 블록의 개수는 100,000개다. 즉 좌표로서 들어오는 수의 종류는 최대 200,000개 라는 뜻이다. 200,000개는 배열로 만들 수 있다. 만약 들어오는 좌표의 종류가 {1, 23434, 9495444, 124, 8, 249833876, 23434}이라면 이를 순서대로 정렬하고 {1, 8, 124, 23434, 23434, 9495444, 249833876}, 중복을 제거해 {1, .. 2020. 10. 9.
[알고리즘] Lazy Propagation 선배 강의 듣고 씀. 세그먼트 트리에서 업데이트는 O(logN)의 시간 복잡도를 가진다. 그런데 업데이트가 노드 하나하나가 아니라 구간으로 주어질 때, 그걸 일일이 업데이트를 해주면 느릴 수 있다. 그래서 구간 업데이트가 들어올 때마다 그걸 바로 적용해주지 않고, 업데이트가 있다는 내용을 따로 저장해놓고 나중에(lazy) 해당 노드를 방문할 때 처리한 후 자식 노드로 업데이트를 전파(propagation)해주는 방식이 lazy propagation이다. 이런 세그먼트 트리가 있을 때, 2~7 구간에 업데이트를 준다고 가정해보자. 일반적으로는 8, 9, 10, 23, 24, 12번 노드에 접근해서 위 부모 노드들까지 값을 업데이트시켜줄 것이다. 이런 식으로 하면 만약 업데이트되는 구간이 더 길어질 경우 시.. 2020. 10. 6.
[C++] max_element(), min_element() algorithm 헤더에 있는, 배열이나 벡터 구간 안에서 최대, 최솟값을 찾는 함수이다. max_element(arr, arr+size) 혹은 max_element(vec.begin(), arr.end()) 처럼 시작 주소 혹은 이터레이터, 끝 주소 혹은 이터레이터를 넣어주면 된다. return 형식도 주소 혹은 이터레이터이기 때문에, 값을 알고 싶다면 *max_element(arr, arr+size) 처럼 써준다. #include #include #include using namespace std; int arr[10] = {1, 2, 10, 4, 9, 3, 7, 5, 6, 8}; vector vec; int main() { vec.push_back('c'); vec.push_back('a'); ve.. 2020. 4. 29.
[알고리즘] 카데인 알고리즘(Kadane's algorithm) 카데인 알고리즘(Kadane's algorithm)은 배열의 최대 부분 합을 O(n)의 시간복잡도로 구하는 알고리즘이다. i번째 인덱스를 오른쪽 끝으로 하는 부분배열들의 최대 부분 합을 M[i]라고 하면, M[i+1]은 M[i]+arr[i+1]이거나 arr[i+1]중 더 큰 값이다. M[0]은 arr[0]인 1이다. M[1]은 arr[1] = -6과 M[0] + arr[1] = -5 중 더 큰 -5이다. M[2]는 arr[2] = 4와 M[1] + arr[2] = -1 중 더 큰 4이다. 왜 M[i+1]이 max(M[i] + array[i+1], array[i+1]) 인지 이해하면 쉽다. i를 오른쪽 끝으로 하는 부분배열 중 최대 부분 합이 음수이면 굳이 더하지 않고 그냥 i+1번째 인덱스부터 새로 더하.. 2020. 4. 25.
[알고리즘] 비트마스크(Bit Mask) 비트마스크(Bit Mask)는 알고리즘이라기보다는 기법인데, 한 비트가 0 또는 1의 두 가지 값을 갖는다는 사실을 이용해 2진수 배열을 십진수로 변환하여 사용하는 테크닉이다. 예를 들어 {true, false, true, false}인 배열을 2진수로 1010으로 표현하고, 다시 십진수로 변환하면 10이 된다. 비트마스크 기법을 이용하면 bool 배열간의 연산을 간단하게 할 수 있다. {true, false, true, false} 배열과 {true, false, false, true} 배열을 각각 & 연산으로 비교할 때, 일반적으로는 반복문을 이용해 배열의 각 인덱스마다 비교해줘야 할 것이다. 그런데 비트마스크 기법을 이용해 {true, false, true, false} 배열을 10으로, {true.. 2020. 4. 16.
[알고리즘] 강한 연결 요소(Strongly Connected Component) 강한 연결 요소(Strongly Connected Component, SCC)는 어떤 양방향 그래프 내에서 다음 조건을 만족하는 부분집합이다. 임의의 강한 연결 요소 내부의 모든 정점끼리는 서로 이어진 경로가 존재한다. 임의의 강한 연결 요소 내부의 정점과 외부의 정점끼리는 서로 이어진 경로가 존재하지 않는다. 즉 이는 어떤 한 정점에 대해 첫번째 조건을 만족하는 최대의 부분집합이라고 할 수 있다. 위 그래프에서 {A, B, C, E}, {D, G, H}, {F}, {I}가 강한 연결 요소이다. 어떤 그래프에서의 SCC를 찾는 알고리즘으로는 코사라주 알고리즘이 있다. 코사라주 알고리즘 | 코사라주 알고리즘은 DFS를 이용한 위상 정렬을 토대로 SCC를 찾는 알고리즘이다. 그래프와 역방향 그래프를 준비한다.. 2020. 4. 13.

티스토리툴바