복습노트 복습노트

segment tree는 구간 쿼리 + 원소 업데이트 쿼리 혹은 구간 업데이트 쿼리 + 원소 쿼리 등을 각각 O(log N)에 처리할 수 있는 자료구조이다. Lazy Propagation이란 테크닉을 이용하면, 구간 업데이트+구간 쿼리를 각각 O(log N)에 처리할 수 있다. Lazy Propagation은 보통 top down방식의 segment tree를 이용한다. Lazy Propagation이라는 단어는 직역하면 느리게 전파한다 라는 뜻을 가지고있다. 핵심 아이디어는 업데이트를 굳이 지금 할 필요가 없으면 나중에 한다는 아이디어에서 시작한다. 위의 트리는 구간을 나타내는 segment tree입니다. [1, 11] 여기서 구간 [3, 6]을 update해보자 파란색으로 칠해진 노드들을 updat..

어떤 문자열 S에서 부분 문자열 t의 존재 여부를 판정하는 문제를 생각해 보자. 가장 단순하게 brute force를 하는 풀이를 우선 떠올릴 수 있다. 모든 s의 index에 대해서, 그 위치에서 시작한 부분 문자열이 t인지를 판정해주면 된다. s의 길이가 n, t의 길이가 m일때, 시간복잡도가 O(nm)이 걸린다. KMP를 이용하면 동일한 문제를 O(n+m)에 풀 수 있다. 우리가 문자열 2개가 같은 문자열인지를 비교하는 방법을 생각해보자 앞에서 부터 하나씩 살펴보면서 모두 같은면 같은 문자열이다. 우리는 모든 시작점에 대해서 같은 문자열인지 판정해야한다. 문자열 "abaabac"에서 "baab"이라는 문자열이 존재하는지를 확인해보자. 아까도 말했듯이 brute forcing 방법에서는 모든 inde..

그래프 이론에서 network flow 라는 개념은 매우 중요 여러가지 개념에 대해서 알아보고, maximum flow를 구하는 알고리즘을 알아보자 물을 흐르게 하는 상수도 처럼 생각해 보면 쉬울 수 있다. 용량(capacity) : 어떤 간선에 대해 존재하는 개념 flow를 흐르게 할 수 있는 한계. 유량(flow) : 정점 u와 v를 잇는 간선이 있을 때, 그 간선에 존재하는 용량 이하 만큼의 유량을 흘릴 수 있다. 소스(source) : 소스는 정점에 존재하는 개념인데, 소스에서만 유량을 발생시킬 수 있다. 싱크(sink) : 싱크도 정점에 존재하는 개념인데, 소스에서 발생한 유량이 흘러온다. 그래프의 간선들의 용량을 표현한 그림이다. 예를 들어 1 -> 2 의 유량이 6까지만 흐를 수 있다. 소스..

SCC는 방향 그래프에서 등장하는 개념 SCC는 그래프의 정점의 부분집합들인데, 하나의 SCC안에 있는 어떤 두 정점 u, v를 골라도 u -> v 로 가는 직간접적인 경로가 존재한다. SCC는 maximal 한 성질을 가지므로, 크기가 가능한 커야 한다. 초록색 부분(1, 2, 3) , 노란색 부분 (4, 5) 그리고 파란색 부분 (6, 7, 8)은 각각 SCC이다. SCC를 구한다 = 방향 그래프를 SCC로 분리한다. 사이클이 없는 방향 그래프는 DAG(Directed Acyclic Graph) 라고 한다. 어떤 방향 그래프에서 SCC로 정점들을 묶어주게 되면, 그래프는 반드시 DAG가 된다. 따라서 사이클이 존재한다면 풀 수 없었던 문제들도, 그래프 자체를 DAG로 바꾸면서 문제를 풀 수 있게된다...

Sparse table이란 행렬 중에서 행렬의 값의 대부분이 0인 경우를 나타내는 행렬 우리가 그래프를 표현하는 방식 중에 인접 행렬 방식을 활용할 때에 있어서 특수한 경우에는. 그래프의 모든 정보를 표현할 필요 없을 때가 있다. 예시 문제 백준 17435 (합성함수와 쿼리) c++ 문제 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(.. riveroilstone.tistory.com LCA는 트리에서 사용되는 개념이다.(최소공통조상) 트리에 존재하는 어떤 두 정점에..

실전문제 풀이! 자료구조나 알고리즘의 활용

구간에 대한 여러 정보를 효율적으로 관리하는 자료구조 ex) prefix sum(특정한 구간의 합) 예시문제 백준 2042 (구간 합 구하기) c++ 문제 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그.. riveroilstone.tistory.com

스프라그-그런디 정리 애드혹/그리디 1) 같은 행동조건 2) 승리 조건이 동일 (상대가 승리하면 내가 패배, 상대가 패배하면 내가 승리) 1) dp로 푸는 유형(시간복잡도와 공간복잡도를 고려하지 않는다면 모든 문제에 적용 가능) dp[x] : x라는 상태에서 선공이 이긴다면 true, 아니라면 false x에서 갈 수 있는 행동집합들을 모두 살펴보면서, 선공이 지는 상태(즉 상대를 패배하게 만드는 상태) 로 만들 수 있다면 x는 선공이 이길 수 있는 상태인 것이다. 예시 문제 백준 9655 (돌 게임) c++ 문제 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 상근이와 창영이가 주어진 n개의 돌을 서로 번갈아 돌아가면 1개 또는..