기술 블로그

https://dyngina.tistory.com/16 을 참고하여 작성하였습니다. 이 글은 저만의 공부를 위하여 간단 요약한 것입니다. 위의 원글을 보시길 바랍니다. ※ lower_bound를 활용한 LIS 풀이법 단점은 답 밖에 모른다.경로 역추적은 다른 방법을 쓰자. 배열(또는 벡터) 내에서 증가 수열을 유지할 수 있는 최적의 장소를 lower bound를 이용하여 찾아준다. vector v = {10, 20, 40, 30, 70, 50, 60}; 1. 10을 넣는다. 이 때의 v.size() = 1현재 : v = {10} 2. 20을 넣는다. 이 때의 v.size() = 2현재 : v = {10, 20} 3. 40을 넣는다. 이 때의 v.size() = 3현재 : v = {10, 20, 40} 4..

heavy-light decomposition 공부할 것.(+ 세그먼트 트리 lazy propagation)

https://www.acmicpc.net/blog/view/26 https://hsdevelopment.tistory.com/600

https://www.acmicpc.net/blog/view/29 https://jason9319.tistory.com/169 https://lifeignite.tistory.com/43 참고 문제 https://www.acmicpc.net/problem/11401

참고 : https://youtu.be/6Z6L4TgjPk8 해쉬 알고리즘 & 충돌 O(1)(최대 : O(n)) 1. Different Keys → Same Code 해쉬 알고리즘은 때론 서로 다른 key 값들로 동일한 해쉬 코드를 만들 때가 있다. key 값은 문자열이고, 가지수는 무한하지만 해쉬 코드는 유한하다. 즉, 중복될 수 밖에 없다. 2. Different Code → Same Index 또한, 다른 해쉬 코드를 얻었지만 '배열 방'은 한정되어 있으므로, 같은 방에 배정될 수 있다. → 위의 2가지 다 Collision 발생. 아래의 코드는 한 가지 예시일 뿐 이고, 좋지 못 한 해쉬 알고리즘이다. 12345678910111213141516171819202122232425262728293031..

https://youtu.be/611B-9zk2o4 https://blog.naver.com/ndb796/221234424646 주의할 점은 first에는 거리(비용, 가중치 등)를second에는 정점이 들어가야 한다. 우선순위 큐 pair에서는 first를 우선 비교하는데, first에 정점이 들어가면 아무 소용없는 정점이 큰 것부터 위에 온다. 물론 애초에 pair 자체가 first를 우선순위로 한다.(비교 등등 부분에서) 12345678출발점 : 1 [1] → [1] 최소 비용 : 0[1] → [2] 최소 비용 : 2[1] → [3] 최소 비용 : 3[1] → [4] 최소 비용 : 1[1] → [5] 최소 비용 : 2[1] → [6] 최소 비용 : 4cs 123456789101112131415161..

선분 교차 판별https://jason9319.tistory.com/358 CCWhttps://hsdevelopment.tistory.com/123

https://www.acmicpc.net/blog/view/9 https://www.crocus.co.kr/648 세그먼트 트리(Segment Tree) 세그먼트 트리의 루트 노드는 0이 아닌 1부터 시작한다.(1, ...)배열, vector의 인덱스 번호는 1이 아닌 0부터 시작한다. 함수의 인자들 중에서 node를 제외한 모든 것들은 vector 또는 배열과 관련된 값들(인덱스, 값 자체 등)이라고 생각하면 된다. 초기 세그먼트 트리 설정하기123456long long init_segment_tree(int node, int start, int end){ if (start == end) return tree[node] = v[start]; return tree[node] = init_segment_..