Sean :: Dev

Network/Maximum Flow 유량그래프 : 간선의 weight가 정점에서 정점으로 보낼수있는 최대유량을 의미하는 그래프 최대유량 : 해당 간선을 통해 동시에 흘려보낼수있는 물의 최대치 이러한 유량그래프에서, Source정점에서 Sink정점까지 최대 얼마만큼의 유량이 지나갈수있는지에 관한 문제를 Network/Maximum Flow라고 한다. 아래와 같이, 수로(간선)에 1초마다 지날수있는 물의 최대치가 정의되어있다면, 수로는 자신의 용량이상의 물은 통과 시킬수없다. 따라서 결과적으로 통과할수있는 물의 최대량은 왼쪽은 2, 오른쪽은 4이다. 따라서 위의 그래프를 Maximum Flow(최대유량)으로 보내면 그 값은 7이다. 좌측값은 실제로 해당 간선에 흐른 유량(flow), 우측값은 해당 간선의 ..

Plane Sweeping 직각도형의 넓이를 구할때 쓰이는 알고리즘 곂친 부분이 있기때문에 단순한 공식을 넓이를 구하기 쉽지 않다. 각 직사각형은 4개의 꼭짓점을 가진다. 따라서 n개의 직사각형이라면, 최대 2n개의 x좌표와 2n개의 y좌표가 사용된다. 이렇게 각 꼭짓점으로 나누면, 각 영역의 넓이를 구한뒤 그 합으로 정답을 구할수있다. 먼저 사용되는 x,y좌표를 모두 구한뒤 정렬시킨다. (원소들이 꼭 유일할 필요는 없다) 이후 x,y좌표로 잘려진 영역들을 순회하며, 사각형이 포함되었으면 넓이를 더해준다. 이때, 원소들이 유일하지않다면 정렬될때 같은값이 붙어있으므로 그 영역의 넓이가 0이 되어 무시해도 되게 된다. 이 과정에서 Segment Tree를 사용해 구간갱신속도를 줄여 시간복잡도를 줄일수있다. ..

KMP (Knuth–Morris–Pratt, 문자열 탐색 알고리즘) 기본적인 문자열 완전탐색 알고리즘에 비해, 약간의 메모리공간을 이용해 불필요한 비교횟수를 줄여 시간복잡도를 줄인다. 예를 들어, samsamsung 문자열에서 samsamsong 문자열을 찾는다면 원래는 0번째 인덱스 s부터 시작하여 쭉 같은지 비교하다가 u가 다르므로 실패하고 이후 1번째 인덱스 a부터 다시 비교하기 시작해, 이땐 처음부터 다르므로 바로 실패, 이후 2번째 인덱스 m부터 ~... 방식으로 비교한다. => 이때 KMP를 사용하면, 맨처음 u가 달라서 실패한 상태에서 samsamsung의 sams와 samsamsong의 sams가 같다는 정보를 기억하고 있다. (물론 결과적으론 비교가 실패하게 되겠지만) 위의 정보를 이용해..

Permutation, Combination (순열, 조합) 확률, 경우의수, 곱의법칙 Permutation 순열 : 서로다른 n개의 원소들중 r개를 중복없이 선택하여 순서있게 배열하는 경우 nPr = n * (n-1) * ... * (n-r+1) = n! / (n-r)! Combination 조합 : 서로다른 n개의 원소들중 r개를 중복없이 선택하는 경우. (순서없음) nCr = nPr / r! = n! / r!(n-r)! 성질1 : nCr = nCn-r 성질2 : nCr = n-1Cr-1 + n-1Cr from 파스칼의 삼각형 파스칼의 삼각형 (n, r = 0부터 시작) => 이를 이용해 동적계획법으로 풀기도 한다. Debugging) DP_bottom up & 파스칼의 삼각형 이용 큰수에서의 100..

※ 귀찮아도 직접 손으로 쓰고 그리며 생각해야 이해가 빠르다 Example 1 : Knapsack (배낭 문제) Dynamic Programming 무게와 가치가 정해진 N개의 물건이 있을때, 가치의 총합이 max가 되도록 배낭을 싸는 문제. 이때, 배낭의 무게 제한은 K이다. (각 물건은 1개씩만 존재하며, 배낭에 넣거나/안넣거나) 동전교환문제와 마찬가지로 Greedy한 방법으로 해결되지않음. ex) V[N] = {13,8,6,12} W[N] = {6,4,3,5} D[i][j] = i번째 물건까지 넣을지/안넣을지 정했을때, 무게 j이하를 채우는 가치의 합중 최대값 => 점화식 : D[i][j] = Max(D[i-1][j], D[i-1][j-W[i]]+V[i]) Max에서 비교하는 두 값중, 전자는 이전..

Dynamic Programming (동적계획법) 복잡한 문제를 여러개의 작은부분문제(sub-problem)으로 나누어 해결하는 기법. 이미 계산된 부분 문제가 다시 발생하면, 새롭게 계산하지않고 이전의 계산값을 참조해 이용할 수 있다. DP를 통해 부분문제를 다시 해결하는 시간을 절약할 수 있지만, 이전 계산값을 저장할 공간이 필요하므로 Time - Space간의 trade off라고 할 수 있다. ex. 피보나치 단순탐색으로 구현시, 위와 같이 여러번 계산된다. => Memorization : 한번 계산된 값을 기록해두고 이후 중복호출 되었을때 새롭게 계산하는게 아닌 저장해둔값을 가져와 사용한다. fibonacci_topdown Top-Down / Bottom-Up Top-down 방식은 큰 문제에서..

Disjoint-set Algorithm (서로소 집합 알고리즘) 집합, 그룹을 관리하는 알고리즘 각 그룹을 트리구조로 관리 크게 2가지의 연산으로 구성된다. find(x) : x번 노드의 root를 찾는 함수 link(x, y) : x 노드가 속한 그룹과 y 노드가 속한 그룹을 합치는(연결하는) 함수 또한 위 연산을 위해, parent[i] : i번 노드의 부모로 정의되는 배열이 사용된다. 아래의 내용은 codeground 사이트에서 가져온 내용 Disjoint-Set 서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다. 각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는 함수 ..

Dijkstra Algorithm 그래프의 한 노드에서 다른 노드로 가는 최단거리를 구하는 알고리즘 (만약 모든 노드 쌍간의 최단거리를 구할땐, n개의 각 정점에 대해 Dijkstra Alg를 여러번 수행해야하므로, 이때는 Floyd-Warshall Alg이 더 유리하다) 동작과정은 BFS와 비슷하지만, Queue가 아닌 Priority Queue를 이용한다. 시간복잡도=O(ElogE) 해당노드까지의 최단거리를 저장할 distance[] 배열 준비후, 미방문을 의미하는 -1로 초기화한다. 노드1에서 시작한다면, 이때까지 자기자신 1까지의 거리는 0이므로 distance[1]에 0을, pq에 (1,0)을 넣는다. 2의10보다 가깝다. distance[2]=8로 갱신, pq에도 (2,8) 넣는다. pq엔 (..