복습노트 복습노트

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..

문제 12895번: 화려한 마을 첫 번째 줄에 N, T, Q (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 30, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 개수, 사용할 색의 개수, 작업의 개수를 의미한다. 두 번째 줄부터 작 www.acmicpc.net n, m, k가 주어지면 n은 집의 개수, m은 사용할 색의 개수, k는 작업의 개수를 의미합니다. 작업은 C와 Q가 있는데 C는 C a b c 의 형태로 주어지면 [a, b]구간에 있는 모든 집을 c로 색칠한다는 의미입니다. Q는 Q a b 의 형태로 주어지면 [a, b] 구간에 있는 모든 집의 색의 가짓수를 출력한다는 의미입니다. 작업이 Q a b 일때 [a, b]에 있는 모든 집에 존재하는 색의 가짓수..

문제 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 저번에 풀었던 구간합 구하기 1 와 유사한 문제입니다. 차이점이라면 구간을 update하는 부분이 구간 모두에 정수 d를 더해준다는 것입니다. 이번에는 신촌 겨울캠프에서 배운 Lazy Segment Tree를 이용해서 풀었습니다. const ll n_ = 4 * 1e6 + 100; ll tree[n_], lazy[n_], A[n_]; 주어진 수를 받을 배열 A A를 Segment tree로 바..

문제 3033번: 가장 긴 문자열 첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다. www.acmicpc.net 길이가 L인 문자열이 주어지면 해당 문자열 안에서 2번이상 등장하는부분문자열 중에서 가장 긴 문자열의 길이를 출력하는 문제입니다. 예를 들어 길이가 11인 문자열 "sabcabcfabc" 이 주어지면 2번이상 등장하는 부분문자열 중에서 가장 긴문자열은 "abc" 이므로 부분문자열 중에서 가장 긴 문자열의 길이는 3입니다. 단순히 naive한 풀이를 생각해보면 한 문자씩 반복문을 돌아보며 확인하므로 최대 O(N^2)의 시간복잡도를 가질 수 있습니다. 길이가 k인 문자열이 2번이상 등장했다면, k-1 인 문자열도 2..

문제 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문자열이 s가 주어지면 해당 문자열을 최소 k번 부분문자열로 들어가게 이름을 정하고 이름의 길이를 출력하면 되는 문제입니다. 예를 들어 s = ada 이고 k = 3 일때 이름의 최소길이는 adadada 총 7 입니다. KMP알고리즘의 fail 배열을 이용하여 해결하였습니다. 접두사와 접미사가 같으면 중복으로 처리해서 이름을 최소로 할 수 있기 때문입니다. 위의 예시를 보면 ada가 총 3번 부분문자열로 들어가야합니다. ada의 fail 배열은 {0, 0, 1} 입니다. 즉 맨 마지막..

문제 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 처음에 문제를 이해하지 못해 함참을 고민한 문제입니다. 광고판의 길이 L이 주어지면 광고판에는 어떤 광고가 무한히 반복적으로 나타납니다. 그때 광고판에 표시된 문자열에서 최소길이의 광고의 길이를 구하는 문제입니다. 예를 들어 광고판 L의 길이가 5이고 주어진 문자열이 babba라면 여기서 연속적으로 광고가 될 수 있는 문자열의 최소길이를 구하는 것입니다. babba (bab가 연속적으로 나타나기 때문에 광고가 가능한 최소 문자열의 길이는 3입니다. 다른 예시로 광고판 L의 ..

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

문제 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문자열이 주어지면 다음에 입력받은 문자열이 첫번째로 주어진 문자열에 있는지 구하는 문제입니다. 문자열 매칭 알고리즘인 KMP 알고리즘을 활용하였습니다. 먼저 fail 함수를 만드는 코드입니다. HTML 삽입 미리보기할 수 없는 소스 전체 문자열이 s이고 우리가 찾고자 하는 패턴 문자열이 t 입니다. 문제에서 공백도 포함해서 문자열을 입력받으므로 C++ 문법인 getline 함수로 입력을 받아주었습니다. 4번째 줄을 보면 변수 i와 j가 함께 있습니다...