본문 바로가기

알고리즘/메모44

KMP 문자열 매칭 알고리즘. O(N+M) string parent, pattern; KMP(parent,pattern) : pattern의 위치를 반환하는 함수 parent 문자열의 idx i, pattern 문자열의 idx j에 대해 i를 0부터 1씩 증가시키며 pattern을 찾는 상황에서 현재 i에서 pattern 찾는 것에 실패했을 때, i를 한 칸 옮기고 j를 fail[j]칸 옮기며 문자열을 찾는 알고리즘이다. 실패함수를 이용해서 푸는 문제가 많다. 실패함수를 만드는 로직과 kmp에서 pattern의 위치를 뽑는 로직이 같은 점을 눈여겨 보자. #include #include #include using namespace std; vector makeTable(string pattern) { int p.. 2019. 9. 18.
lazy propagation - 세그먼트 트리 확장 코드의 상당부분은 kks227(라이)님의 코드를 참고했음을 밝힙니다. 기본문제 https://www.acmicpc.net/problem/10999 https://www.acmicpc.net/problem/12844 https://www.acmicpc.net/problem/1395 구간 합을 빠르게 구하기 위해서 prefix 배열을 이용 -> update 등의 다수의 쿼리가 발생했을 때도 구간 합을 빠르게 구하기 위해서 segment tree 사용 -> 구간 update 등 다수의 쿼리가 발생했을 때 구간 합을 빠르게 구하기 위해 lazy배열과 propagation 사용 필요한 것: segment tree, lazy 배열 propagate(node, ns, ne) : add나 val 함수에서의 node에 .. 2019. 9. 18.
냅색, knapsack https://www.acmicpc.net/problem/10265 10265번: MT 문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 www.acmicpc.net 이 문제의 기본 아이디어 작은 상자 n개에 사탕이 최소 mn개 최대 mx개 들어있을 때, 용량이 K인 큰 바구니에 최대 몇개의 사탕을 넣을.. 2019. 8. 19.
기하 - 두 선분 사이의 거리 라이님 블로그에서 공부했음을 밝힙니다 https://blog.naver.com/kks227/220794097589 https://www.acmicpc.net/problem/11563 11563번: 연돌이와 고잠녀 첫 줄에는 신촌에 연결된 도로의 숫자 n과 안암에 연결된 도로의 숫자 m(1 0) { long double s = triangle(A, B, C); h = min(h, s / distBetweenPoint(A, B) ); } if (innerProduct({ D.first - A.first, D.second - A.second }, { B.first - A.first, B.second - A.second })>0 && innerProduct({ D.first - B.first, D.second .. 2019. 8. 19.

티스토리툴바