Table of Contents 개요프림 알고리즘O(V^2) 알고리즘O(V^2) 코드O(E log V) 알고리즘O(E log V) 코드문제프림 알고리즘의 정당성 1. 개요 프림 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘과 같은 용도이지만, 응용 상황에서 두 알고리즘의 효율성이 달라질 수 있기 때문에 둘 모두 알아두는 것이 좋습니다. 최소 스패닝 트리에 대한 개념을 모른다면 크루스칼 알고리즘을 먼저 보고 오시는 걸 추천합니다. 2. 프림 알고리즘 프림 알고리즘은 MST를 찾기 위한 그리디 패러다임의 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다. step 0) 임의의 정점을 선택하여 비어있..
Table of Contents 개요방법 1 - 동적계획법방법 1 코드방법 2 - 탐욕법방법 2 코드방법 2 의 정당성방법 2 로 far 배열 찾기문제 1. 개요 트리의 지름이란, 트리 내에서 가장 먼 두 정점 사이의 거리를 뜻합니다. 이 글에서는 트리의 지름을 구하는 2가지 방법에 대해 소개합니다. 참고로 이 두 가지 방법은 모두 시간 복잡도를 늘리지 않는 선에서 'far [ v ] = 정점 v와 v에서 가장 먼 정점 사이의 거리'를 모든 정점에 대해 구할 수 있습니다. far 배열을 구하면 지름 = MAX(far [ v ])로 쉽게 구할 수 있으며, 지름만 구할 때 보다 더 다양한 상황에 쓸 수 있게 됩니다. 때문에 이 문서에서는 far [ v ] 을 구하는 방법까지 소개하도록 하겠습니다. 방법 1은..
Table of Contents 개요최소 스패닝 트리 ( minimum spanning tree )크루스칼 알고리즘 ( Kruskal's algorithm )크루스칼 알고리즘의 구현크루스칼 알고리즘 코드문제크루스칼 알고리즘의 정당성 1. 개요 크루스칼 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 사용하므로, 해당 자료구조를 모른다면 유니온 파인드 설명을 보고 오시는 걸 추천합니다. 2. 최소 스패닝 트리 ( minimum spanning tree ) 스패닝 트리란, 해당 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프를 뜻합니다. 왼쪽의 그래프에서 스패닝 트리를 하나 찾아보면 오른쪽의 ..
Table of Contents 개요초기화간단한 방법최적화 단계 1최적화 단계 2 - 유니온 파인드 트리유니온 파인드 트리 - 코드문제 1. 개요 유니온 파인드는 집합을 관리하는 자료구조로서, disjoint set 이라고 부르기도 합니다. 이 자료구조를 활용하면 아래의 두 가지 연산을 사용할 수 있습니다. 연산 1) 요소 A와 요소 B가 같은 집합에 속하는 지 확인.연산 2) 요소 A가 속한 집합과 요소 B가 속한 집합을 병합. 유니온 파인드 연산의 이해를 위해 일단, 위와 같이 4개의 요소가 있다고 해보겠습니다. 초기 상태는 아직 병합을 한 번도 안 한 상태이기 때문에 각자 다른 집합에 속합니다. 이 상태에서 1번 연산, 예를 들어 요소 1과 요소 2가 같은 집합 인지에 대한 질의가 들어오면 이 자료..
Table of Contents 개요 O(n^2) 풀이 더 알아보기 : O(n log n) 풀이 1 더 알아보기 : O(n log n) 풀이 2 1. 개요 최장 증가 부분 수열 (longest increasing subsequence) 문제는 유명한 동적 계획법 활용 예시입니다. LIS 문제는 말 그대로 수열이 주어졌을 때, 수가 점점 증가하는 가장 긴 부분 수열을 찾는 문제입니다. 정확한 문제는 아래의 링크를 통해 확인할 수 있습니다. [BOJ 11053] 가장 긴 증가하는 부분 수열 2. O(n^2) 풀이 dp [ i ] = A [ i ] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이 간단하게 위와 같이 dp 문제를 정의하면 해결할 수 있습니다. 이 dp의 정의는 A[1] ~ A[i] 수열의 L..
Table of Contents 개요 풀이 구현 더 알아보기 : 공간 복잡도 최적화 1. 개요 냅색 문제 ( 배낭 문제 ) 는 프로그래밍계에서 유명한 문제로서 요약하면, 담을 수 있는 무게의 최댓값이 있는 배낭, 그리고 무게와 가치를 가진 짐들이 있을 때 배낭에 넣을 짐들의 가치가 최대가 되도록 배낭에 넣을 짐들을 고르는 문제입니다. 이 문제는 짐을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우로 나뉩니다. 이 중 쪼갤 수 없는 경우는 0/1 배낭 문제 ( 0/1 knapsack problem ) 이라고 불리며 동적 계획법으로 해결이 가능합니다. 아래의 링크를 통해 0/1 배낭 문제의 예시를 보고 코딩한 후, 채점해 볼 수 있습니다. 아래의 풀이와 구현은 이 문제를 기준으로 설명하므로 반드시 읽어보시길 바랍니..
Table of Contents 개요변환1차 함수 집합 관리최소값 찾기문제 1. 개요 컨벡스 헐 트릭 ( Convex hull trick, Convex hull optimization)은 동적 계획법에서 특정 형태의 점화식이 사용되었을 시 시간복잡도를 획기적으로 줄여주는 기법입니다. DP 관계식을 아래와 같이 정리 가능할 때 사용할 수 있습니다. D[i] 는 어차피 j와 상관이 없기 때문에 상수처럼 취급하고, (i에 대한 함수) * (j에 대한 함수) + (j에 대한 함수) 으로 생각하면 쉽게 컨벡스 헐 트릭의 모양이란 걸 알 수 있습니다. 2. 변환 우선 각각의 j 에 대해 다음과 같은 함수를 생각해봐야 합니다. 여기에서 j 는 정해진 상수이므로 B[j], C[j] 또한 상수입니다. 그러므로 위의 함수..
Table of Contents 개요 DP 기본 예제 – 피보나치 수열 DP 구현하기 DP 문제 - 1 DP로 문제에 접근하기 DP 문제 - 2 유명한 DP 응용 주의할 점 DP 문제 - 3 1. 개요 동적 계획법, 영어로 Dynamic programming 다이나믹 프로그래밍, 줄여서 DP. 문제를 여러 개의 하위 문제들로 나누어 먼저 처리한 후, 그 하위 문제들의 답을 이용해 원래 문제를 처리하는 방법을 뜻합니다. 하위 문제를 처리하는 과정에서 같은 문제를 여러 번 처리하게 되는데, 한 번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도를 비약적으로 빨라지게 할 수 있습니다. 2. DP 기본 예제 – 피보나치 수열 피보나치 수열을 DP로 구하는 과정을 통해서 DP에 ..
풀이는 http://weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%97%90%EC%84%9C%EC%9D%98-%EB%AA%A8%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%99%9C%EC%9A%A9-Mos-algorithm-on-tree 이 곳에 서술 되어 있으므로, 상세한 사항은 아래의 소스로 대신한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979..
Table of Contents 개요 트리 펼치기 Mo's algorithm 의 적용 문제 1. 개요 https://www.acmicpc.net/problem/13518 위 문제와 같이 트리에서의 쿼리를 처리할 때, 쿼리의 처리 순서를 마음대로 조작할 수 있다면, DFS로 트리 펼치기 + Mo's algorithm 의 조합으로 시간 복잡도 O( (N+Q) * sqrt N * f(x) ) 을 맞춰 줄 수 있는 경우들이 있습니다. ( * f(x) = 모스 알고리즘에서 노드의 추가 / 삭제 시 필요한 시간복잡도 ) 2. 트리 펼치기 트리에서 DFS를 돌면서, 각각의 DFS 함수가 '시작 했을 때', 그리고 '끝날 때' 해당하는 노드를 배열에 추가해서 트리를 펼치는 스킬입니다. 아래 예시를 통해 알아보겠습니다...
Table of Contents 개요 1D sparse table 쿼리를 O(1)으로 처리하기 2D sparse table 문제 1. 개요 스파스 테이블은 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산을 빠르게 하기 위한 자료구조입니다. 간단하게 예를 들면, 'A[3] ~ A[7] 사이의 최소값을 구하라.'같은 식입니다. 여기에서 함수는 최소값 찾기, L = 3, R = 7이 되겠지요. 스파스 테이블은 아래의 두 조건이 성립할 때 사용할 수 있습니다. 조건 1) Array에 저장된 값이 변하지 않야야 한다. 조건 2) Function은 결합 법칙이 성립해야 한다. (즉, F(a,..
Table of Contents 개요 쿼리 처리 쿼리 정렬 문제 1. 개요 https://www.acmicpc.net/problem/13547 먼저 위의 문제를 읽어주시길 바랍니다. 범위 쿼리를 처리하는 상황에서 가끔 이런 상황들이 있습니다. 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산하는데, 배열에 저장된 값을 고치는 update 연산은 없는 상황입니다. 위의 문제가 그 예시이지요. 이런 상황을 만나면 Segment tree 나 Sparse table 로 접근하는 경우가 많습니다. 하지만 이 두 자료구조를 활용한 접근은 대체로, 온라인 처리가 아닌 배치 처리가 가능하다는 점을..
Table of Contents 개요 오일러 피 함수 구현 오일러의 정리 문제 1. 개요 오일러 피 함수는 정수론에 등장하는 함수로서 n 이하의 자연수 중 n과 서로소인 수의 개수를 구하는 함수입니다. 오일러의 정리와 함께 쓰이기도 하고, 단독으로 사용되기도 합니다. 이 글은 독자가 소수를 구하는 알고리즘 중 에라토스테네스의 체를 안다고 가정하고 설명하기 때문에 해당 알고리즘을 모르시는 분은 에라토스테네스의 체 설명을 보고 오시는 걸 추천합니다. 2. 오일러 피 함수 구현 오일러 피 함수란, n 이하의 자연수 중 n과 서로소인 수의 개수를 구하는 함수입니다. n의 소인수 p들에 대해서 아래의 식을 계산하면 오일러 피 함수 값을 얻을 수 있습니다. 위의 식을 구현하기 편하게 정리하면 아래와 같이 됩니다. ..
Table of Contents 개요 ( 프로그래밍에서의 페르마의 소정리 ) 페르마의 소정리로 잉여역수 구하기 구현 나눗셈 연산에 적용 문제 1. 개요 ( 프로그래밍에서의 페르마의 소정리 ) modular 연산의 합동 관계) 두 정수 A,B 에 나눗셈을 적용하여 A/B를 계산하면 몫과 나머지가 나옵니다. 이 때, Q는 몫 R은 나머지라고 하겠습니다. A/B = Q...R A = B*Q + R 보통은 Q를 사용하는 경우가 많지만, R만을 필요로 하는 경우들도 있습니다. 그런 경우들을 위해서 정수론에선 mod 로 불리는 연산자를 사용합니다. 위의 경우를 mod로 표현하면 아래와 같이 됩니다. 위의 식은 'A를 B로 나눈 나머지와, R을 B로 나눈 나머지가 같다.'라는 뜻이 됩니다. A와 R이 법 B에 대해 ..
Table of Contents 개요 유클리드 호제법 시간복잡도 최대공약수에 대해 알아둬야 할 것 문제 1. 개요 두 수 n, m 의 최대공약수를 구할 때, 유클리드 호제법을 이용하면 시간복잡도 O(log(n+m))만에 구할 수 있습니다. 2. 유클리드 호제법 gcd(n,m) = gcd(n-m,m), 그리고 더 나아가 gcd(n,m) = gcd(n%m,m) 임을 이용해 최대공약수를 빠르게 찾는 방법입니다. (n,m 은 자연수) (편의상 n, m 의 최대공약수 = gcd(n,m) 으로 표현하겠습니다.) n,m 은 자연수이고 n%m!=0 일 때, gcd(n,m) = gcd(n%m,m)이다. 증명 g = gcd(n,m), k = gcd(n%m,m), x = n을 m으로 나누었을 때 몫이라고 하겠습니다. (n ..
Table of Contents 개요 단순한 방법 최적화 문제 1. 개요 프로그래밍 문제를 해결하다 보면 소수를 활용해야 하는 경우가 종종 발생하는데, 그 중에서도 특정한 값 N 이하의 소수를 모두 찾아야 하는 경우가 꽤 많습니다. 그럴 때 초,중학교 수학 시절 노가다 취급했던 에라토스테네스의 체가 꽤 좋은 방법이 되어줍니다. (여기에서의 소수는 양의 약수가 1과 자기 자신뿐인, 1보다 큰 자연수를 의미합니다.) 2. 단순한 방법 에라토스테네스의 체를 잊으신 분들을 위해, 그 방법을 그대로 적용한 알고리즘을 소개해 드리면 다음과 같이 됩니다. -------------------------------------------------------------------------------------------..
1. DP[i][j] = (i, j)가 오른쪽 밑 모서리인 정사각형의 최대 크기 1-(1). (i,j) 가 0인 경우 -> DP[i][j]=0; 1-(2). (i,j) 가 1인 경우 -> min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 2. parametric search 3. 쿼리의 정답이 특정 값 mid 이상인지 여부는 DP 배열을 소스로 만든 sparse table을 통해 바로 알 수 있음. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384..
DP[i] = 1 ~ i 병사들로 얻을 수 있는 조정된 전투력의 최댓값 위와 같은 간단한 DP를 구하면 된다. SUM[i] = X[1]+X[2]+...+X[i] 로 미리 sum 배열을 구해 놓으면 SUM[i] - SUM[j] = X[j+1]+X[j+2]+...+X[i] 가 성립하므로 아래와 같이 DP[i]를 구할 수 있다. 이 식을 전개하여 컨벡스 헐 트릭을 사용할 수 있게 i 와 관련된 함수( = SUM[i]가 곱해진 항) , j와 관련된 함수, 상수를 나누면 위와 같이 된다. 이제 A[i] = SUM[i], B[j] = -2*a*sum[j]+b, C[j] = DP[j]-b*sum[j]+a*sum[j]^2, D[i] = a*sum[i]^2+c 로 대응시킬 수 있다. min 함수가 아닌 max 함수이지만..
m^2 = m+m+m+...+m (총 m개) 이므로 m 개의 O가 연속되어 있을 때, 한번에 m^2을 획득한 게 아니라 m 번의 클릭(O) 이 각각 m 점을 획득한 것이라고 바꿔 생각할 수 있다. 이러면, 정답 = ∑ ( i 번째 클릭이 얻은 점수의 기댓값) = ∑ ( i 번째 클릭이 속한 O 그룹의 길이의 기댓값) 이 된다. 이제 쉽게 DP를 설정해보면, DP[i] = i 번째가 클릭이 속한 O 그룹의 길이의 기댓값. 그런데 이 DP[i] 를 구하려고 해보면 (i-1) 번째 클릭의 성공률이 DP[i] 에 영항을 끼치고, i 번째 클릭의 성공률이 DP[i-1]에 영향을 끼쳐서 결국 상호 간에 영향을 끼치기 때문에 까다로워짐을 알 수 있다. DP[i] 의 부분 문제로 DP[i-1]을 설정해놓고, DP[i-..
일단 입력으로 트리가 주어지고 있으므로 가장 흔하고 쉽게 생각할 수 있는 DP설정을 사용하면 DP( i ) = i 를 root로 하는 subtree 의 최소 얼리 어답터 수,하위문제 = DP( i 의 자식들 ) 이와 같이 설정해 볼 수 있다. 이 상태에서 하위 문제들로 DP(i) 를 구하려고 해보면 일단, i가 얼리어답터인지 여부에 따라 경우가 달라지므로 i 가 얼리어답터인 경우와 아닌 경우의 답을 구한 후 종합해야 문제가 쉬워짐을 알 수 있다. 우선 i가 얼리어답터인 경우엔 자식 노드들에 대한 아무런 제약이 걸리지 않으므로 ‘ DP(i 의 자식들 )의 총합 + 1 ‘ 임을 쉽게 알 수 있다. 이제 문제는 i가 얼리어답터가 아닌 경우인데, 이 때는 문제 조건에 따라 자식 노드가 무조건 얼리어답터 여야만 ..
문제의 특성을 파악하기 위해 우선, 어떤 위치 i를 저장했다고 가정하자. 그러면 i를 기준으로 왼쪽과 오른쪽이 갈리게 된다. 왼쪽인 0 ~ i 번지의 오차를 계산할 때를 생각해 보면, 이미 i 가 저장되어 있기 때문에 i+1 ~ n-1 번지 중 어떤 위치가 저장되었는지는 상관이 없어진다. 다시 말해서 0 ~ i 번지와 i ~ n-1 번지 사이의 연결 고리는 ‘저장한 집이 몇 개인가’ 가 유일하게 된다. 이 것만 확정되면 나머지 요소들은 모두 독립적으로 작용한다. 그리고 이 정도 정보는 충분히 저장할 수 있기 때문에 다음과 같이 DP 문제를 정의해 볼 수 있다. DP( i, j ) = 0 ~ i 번지의 집 중에 j 개를 저장했을 때 오차의 합의 최솟값( 단, 0 과 i 번지는 반드시 저장 해야 함. ) 이..
일단 마지막 계단까지 올라가는 최댓값을 구해야 하고 계단은 한번에 1개 혹은 2개를 올라갈 수 있으니 아래와 같이 설정해 볼 수 있다. DP( i ) = i번째 계단까지 올라가는 최댓값하위 문제 : DP( i-1 ), DP( i-2 ) 이 때, 아래에 있는 계단으로 갈 수가 없으니 사이클이 생길 일에 대해선 걱정할 것이 없다. 하지만 ‘연속된 세 개의 계단을 모두 밟아서는 안 된다. ’는 조건이 있는데 이를 DP( i-1 ), DP( i-2 )의 정보만 가지고는 처리를 할 수 없으므로 DP 설정에 정보를 추가해야 한다. DP( i, j ) = 마지막 점프가 j 개를 올라가는 점프일 경우, i 번째 계단까지 올라가는 최댓값하위 문제 : DP( i-1, 2 ), DP( i-2, 1 ), DP( i-2, 2 ..