Informatics

1. Number thinking 문제요약: Up and Down 을 Interactive 로 옮겨 놓은 문제이다. 풀이: 숫자 범위를 L 이라고 할때, 항상 현재 범위의 중간을 확인하는 방식으로 [log2 (L)] + 1 번 만에 정답을 맞출 수 있다. Interactive probolem 이기 때문에, 출력 시 buffer flush 를 해주지 않으면 TLE 로 판정된다. 2. Mural 문제요약: 길이 N 개의 벽이 있고, 각 벽에 해당되는 점수가 있다. 하루 마다 길이 1 에 해당되는 벽을 색칠 할 수 있고, 하루마다 좌우측 벽 중 색칠되지 않은 놈들중 하나가 무너진다. 첫번째 날에는 아무 벽에서 색칠을 시작 할 수 있고, 시작한 이후에는 이미 색칠된 벽의 좌우만 칠 할 수 있다. 이러한 상황에서..

Problem https://www.acmicpc.net/problem/2466 Summary N 개의 책이 주어진다.각 책 마다 너비 W 와 높이 H 가 주어지고, 주어진 순서대로 책장에 꽂으려 한다. 모든 책을 꽂기 위한 책장의 너비와 높이중 최대값을 최소로 하려고 할 때, 그 최소값은 얼마일까? Solution 너비와 높이 중 최대값을 최소로 하는 문제이다.모든 책을 꽂아야 하는 책장의 특성상 너비가 증가함에 따라 높이가 단조감소하고, 너비가 줄어들면 높이가 단조증가하게 된다.따라서 책장의 너비(폭) 을 고정시키고, 그 때의 최소 높이를 구한 다음 그 높이를 기준으로 책장의 너비를 늘릴지 줄일지 결정할 수 있고 따라서 이 문제는 파라메트릭 서치로 접근 가능하다. 그렇다면 책장의 너비를 고정 시켰을 ..

오일러 파이 함수란 = 1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수를 나타내는 함수이다로 정의되는 함수이다. 이러한 파이 함수에는 여러가지 성질이 발견되는데우선 곱의 함수라는 점이다.이에 대한 증명은 에라토스테네스의 채와 비슷하게 정수들을 쭉 나열한 다음, 서로소가 아닌 수들을 지워나가면 규칙을 찾을 수 있다. 이러한 파이 함수의 값을 구하는 방법에는 여려가지가 있겠지만,우선 특정 N에 대해 구한다고 생각하면N의 소인수들을 다 구한 다음 이 공식을 사용하면 된다. 1~ 까지 파이 함수의 값을 구하기 위해서는,소수판별을 할때 에라토스테네스의 채 기법을 사용한다. pi[i] = i;for (int i=2;i

트리에서 사용하는 분할정복 기법을 Centroid Decomposition이라고 한다.트리에 존재하는 모든 경로에 대해서 어떤 연산을 수행하려 할때트리를 분할에 서브 트리에 대해 연산을 수행하고, 그러한 서브트리를 merge해 전체 트리에서의 결과값을 얻어 낼 수 있다. 여기서 중요한 것은 주어진 트리르 어떻게 쪼개는지 이다.쪼개는 방법에 따라 시간복잡도가 달라지는데, 분할정복 처럼 트리의 크기를 계속해서 반 씩 쪼깨고 각 서브트리를 처음 트리사이즈 시간만에 merge 할 수 있다면 시간복잡도는 마스터 정리에 의해 O(N lg N)이 된다. 이 문제를 푸는 데 있어 중요한 것은1. Subtree 로 분할할 cutting edge를 어떻게 잡을것인가? 2. 서로다른 Subtree들의 결과값을 어떻게 리니어..

D[t][i] = min (D[t-1][j] + C[j][i]) (j D[t-1][k] + C[k][i]D[t][i+1] = D[t-1][k] + C[k][i+1] > D[t-1][j] ..

우선 K=1일때에는 트리의 지름에 설치하는것이 가장최적이라는 결론을 내릴수 있는데 그에 대한 증명을 위해서 지름길을 설치했을때의 경로길이를 수식으로 표현해보자 일단 지름길을 설치하지 않았을때에는 모든간선을 2번씩 지나야함으로 경로이길이는 2(N-1)이 된다. 지름길을 하나 설치하면 트리에 간선을 하나 추가하는 행위임으로 반드시 하나의 사이클이 생기게된다.이때 사이클 위에 존재하는 간선은 한번씩만 사이클위에 속하지 않는 간선은 2번씩지나야함으로경로의 길이는 2(N-1) - L + 1이 되는데 L은 (사이클 위에 포함된 정점의 갯수-1)개 이다. 따라서 K=1일때는 간선을 추가하여 만드는 사이클의 길이(즉, 정점갯수-1) 가 최대가 되게 하면 됨으로 트리에 지름에 설치하는것이 가장 최적이라는 결과가 나온다...

그래프 에서매칭 = 변집합 로, 상호 끝점을 공유하지 않는다.변 덮개 = 변집합 로, 의 어떤 정점도 적어도 1개의 에 포함된 변에 접속 하고 있다.안정집합 = 점집합 로, 의 어떤 두점도 에 대해 인접하고 있지 않다.점 덮개 = 점집합 로, 의 어떤 변도 적어도 1개의 에 포함된 정점에 접속하고 있다.일때 몇가지 법칙이 성립한다. 1. 고립점이 없는 그래프에서 대해서, |최대매칭| + |최소 변 덮개| = |V|2. |최대 안정 집합| + |최소 점 덮개| = |V| 특히 이분그래프에서는|최대 매칭| = |최소 변 덮개| 가 된다. http://prague.algospot.com/judge/problem/read/TRAPCARD위 문제가 위의 성질을 이용하여 풀수있는 대표적인 문제이다이문제는 갯수만 출..

dynamic programming 문제들중 와 같은 점화식을 가진 문제들에 대해 생각해보자. 실제로 최근 KOI에서도 위와 같은 점화식을 가진 문제가 몇몇 나왔는데2011 전국 중등부3 번이라던가2011 지역 고등부5 번을 예로 들 수 있다. 위와 같은 점화식을 가진 문제는 특수한 경우에 따라 시간복잡도를 에서 으로 바꿔 풀 수 있다. 1. commando (APIO 2010)위 문제의 점화식을 나타내보면여기서 bX항은 그룹을 어떻게 나누는지에는 상관없이 항상 그 값은 과 같게 된다.따라서 위 점화식을 로 두고 마지막에 b*(x1+x2..+xn) 을 더해주면 위와같은 점화식이 된다는것을 확인할 수 있다. 그리고 c는 j값에 상관없이 항상 일정한 값을 가지기 때문에우리는 고정된 i 에 대하여 의 값을만에..

링크 : http://211.228.163.31/pool/coci_traka/coci_traka.php?pname=coci_traka Solution 1) O(NM) D(j) = j번째 사람이 첫번째 작업을 시작할 최소시간 이라 정의하자. 그러면 모든 i에 대하여 D(j) + {T(1)+T(2)+T(3)...+T(i)}*F(j) = D(j) + {T(1)+T(2)+T(3)...+T(i-1)}{F(j)-F(j+1)} + T(i)*F(j) 가 성립해야한다. 즉 D(j+1) = D(j) + max( {T(1)+T(2)+T(3)...+T(i-1)}{F(j)-F(j+1)} + T(i)*F(j) ) 라는 식을 얻어낼수 있다. 따라서 모든j에 대해서 모든 i를 훑으면, O(NM)솔루션을 얻어낼수 있다. 2) O(Nl..

http://211.228.163.31/30stair/hanoi1/hanoi1.php?pname=hanoi1 문제를 요약하자면 현재상태의 하노이 탑이 주어졌을때 1,2,3번 기둥중 어떤기둥으로 옮기는지는 상관없고, 최소의 이동으로 모든 조각을 한곳에 모을때 최소이동과 어디로 모으는 것이 최적인지 구하는것이다. 일단 이문제는 linear 하게 풀릴수 있다. 가장 쉽게 떠올릴수 있는 방법이 모든 경우를 다해보는 backtracking 기법인데. 이문제의 실제 N범위가 100,000인걸 감안한다면 으론 해결할수 없다. 그렇다면 어떻게 접근해야 풀수 있을까? 1) 우선 우리는 N개의 하노이를 한 기둥에서 다른기둥으로 옮기기 위해 이동해야하는 최소횟수는 임이 자명하다. 2) 그리고 우리가 최종적으로 옮겨야할 목적..