1. 강한 연결 요소(strongly connected component) 방향그래프에서 임의의 정점 v1,v2를 골랐을때, 항상 v1과 v2를 서로 오갈 수 있는 경로가 존재한다면, 그러한 방향 그래프를 강한 연결 요소(SCC)라고 부른다. 이 정의에 의하면 무방향 그래프에서는 전체 그래프가 반드시 강한 연결 요소가 되므로 의미가 없다. 즉, 방향 그래프에서만 의미있는 정의가 된다. 아무튼 예를 들어 다음 그래프는 모든 정점 쌍 (v1,v2)에 대하여 서로 오가는 경로가 존재하는 강한 연결 요소이다. 하지만 다음 그래프는.. 2번에서 5번으로는 갈 수 있어도 5번에서 2번으로 올 수는 없다. 그러므로 강한 연결 요소가 아니다. 하지만 그래프를 다음과 같이 적당히 분할하면, 분할된 그룹들 [1,2,3,4..
1. counting inversion problem inversion이란 배열 A에 대하여 자기보다 뒤(index가 큰 쪽)에 있으면서 자기보다 값이 작은 A[j]를 뜻한다. 수학적으로 i A[j]를 만족하는 (i,j)의 개수를 세는 문제이다. 단순하게 세면 $O(N^{2})$이지만 실제 위치보다 전후 관계만 본다는 점을 관찰한다면, 2,X,X,X,X,X,X,X,X,1이더라도 2와 1은 inversion이고, 2,1,X,X,X,X,X,X,X,X,...더라도 2와 1은 inversion이다. 또한 다음 그림과 같이 화살표들의 교점의 개수와 동일하다. 두 수가 서로 inversion이면 교점이 하나 생기기 때문이다. 2. 해법 위 그림에서 볼 수 있는대로, 병합정렬을 하면 자연스럽게..
1. 분할 정복(divide and conquer) 분할 = 큰 문제를 여러 개의 작은 문제로 쪼갠 다음 정복 = 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법 충분히 크기가 큰 문제를 쉽게 해결할 수 있는 부분 문제로 분할해 나가고, 분할된 하위 문제를 해결하여 이 결과를 조합하여 윗단계 문제에 대한 답으로 낸다 2. 방법 정답을 쉽게 도출할 수 있을 때까지 재귀적으로 분할된 단위로 자신을 호출하면서 범위를 조금씩 줄여나감(분할단계) 답을 쉽게 도출하는 단계까지 도달한다면 재귀함수는 정답을 return하고 이렇게 return하면서 이를 이용해 재귀 stack에 쌓인 윗단계 재귀함수의 값을 return해나가는 것이 정복단계 def f(x): if (f(x)가 간단함): return f(x) el..
1. 반복되는 부분 문자열 찾기 전체 문자열에서 적어도 두번 이상 나타나는 부분문자열 보통 "가장 긴 반복 부분 문자열"을 찾는 것에 관심 있다 예를 들어 "abcefgabc"에서 "abc"가 두번 나타나면서, 가장 긴 반복 부분 문자열이다. 찾는 방법은 생각보다 간단한데, https://en.wikipedia.org/wiki/Substring Substring - Wikipedia From Wikipedia, the free encyclopedia Not to be confused with subsequence, a generalization of substring. "string" is a substring of "substring" In formal language theory and compute..
https://justicehui.github.io/hard-algorithm/2018/12/21/BipartiteMatch/ [그래프] Bipartite Matching 이분 매칭이란? 이전 글에서 Max-Flow를 구하는 방법에 대해 알아보았고, 마지막 부분에서는 문제 하나를 풀어보았습니다. icpc.me/11375 문제를 풀어보았고, 문제를 그래프로 모델링하면 아래 사진처 justicehui.github.io 29. 이분 매칭(Bipartite Match.. : 네이버블로그 (naver.com) 29. 이분 매칭(Bipartite Matching) 지난 번에 네트워크 플로우(Network Flow) 알고리즘에 대해 공부하는 시간을 가졌습니다. 이... blog.naver.com Kuhn's Algo..
https://cp-algorithms.com/data_structures/sparse-table.html Sparse Table - Algorithms for Competitive Programming Sparse Table Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its true power is answering range minimum queries (or equivalent range maximum queries). For those queries it can compu cp-algorithms.com infossm.g..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
