kthng

boj 1799 : 비숍https://www.acmicpc.net/problem/1799  기본적인 DFS + 커팅 방법을 사용하여 해결할 수 있다.백준 9663번 N-Queen와 유사하다. 0. DFS + 커팅방법지정한 y, x에 놓을 수 있는지 판단하기 위해 (y-1,x-1), (y-2,x-2) ... 를 모두 확인하면 판단을 위해 O(N)의 복잡도가 추가로 소모된다. 판단은 O(1)로 끝내야 한다. true나 false를 담은 check배열을 이용하여 한 번의 접근으로 말을 놓을 수 있는지 판단하도록 모델링해야 한다. 이후, DFS + 커팅 방법을 보완하기 위해 크게 2가지 기법을 추가로 사용하였다.1. 좌표변환위와 같이 좌표 변환을 끝내 놓으면, N-Queens문제보다 더 쉬운 N-Rooks 문제..

https://www.acmicpc.net/problem/1214 1214번: 쿨한 물건 구매 첫째 줄에 D, P, Q가 주어진다. 모두 109보다 작거나 같은 자연수이다. www.acmicpc.net D, P, Q가 각각 $10^9$이하의 자연수일 때, D

https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net DP 냄새가 강하게 나는 문제이다. 낮은 탑 높이의 최대값을 f(idx, diff)로 두면. 아래와 같이 점화식을 세울 수 있다. 1. f(-1, 0) = 0 2. f(idx, diff) = max( [1], [2], [3]) 2-1. [1] : f(idx - 1, diff) 2-2. [2] : f(idx - 1, diff + a[idx]) + a[idx] 2-3. [3] : f(..

https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 풀이중.... 대략 이런느낌이다. 예제의 {1, 4, 7, 10, 11, 12} 에서 {1, x} 에서 x를 1과 짝지었을 때 소수가 되는 수라고 할 때, {1, 4, 7, 10, 11, 12} - {1, x} 에서 각 쌍의 합을 소수로 만들 수 있는 모든 x를 출력한다. 각 쌍의 합을 소수로 만들 수 있는지 확인하는 작업은 이분매칭과 유사한 방법등..

Rectangles [SCPC 2016 - 2차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=30 문제는 저 점 (7, 3.5)를 찾는 것이다.R1은 R3을 포함하고, R3는 R4를 포함한다. 그리고 R1,R3,R4는 서로 겹치지 않는다. 점 (7, 3.5)는 겹치지 않고 서로 포함관계에 있는 3개의 Rectangle 안에 포함되고, 위와같은 조건을 만족하면서 더 많은 Rectangle 안에 포함되는 점을 찾을 수 없으므로 답은 3을 출력하면 된다. 그렇다면 답은 어떻게 구할 수 있을까?먼저 R1에 포함되는 최대 집함을 찾아보자.Ri의 집합의 크기를 Si라 두면,R1은 R2,R3,R4를 포함하므로 S1 = max(S2,S3,S4)..

codeground : 프리랜서 [SCPC 2016 - 2차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=31 간단한 DP로 해결할 수 있다.일하는 데 일주일이 걸리는 P사의 각 주당 금액 을 Pi, 이주일이 걸리는 Q사의 각 주당 금액을 Qi라 하고, i번째 주에 받을 수 있는 가장 큰 금액을 Ai라 한다면, Ai = max(Ai-1+ Pi, Ai-2 + Qi) 위와같은 단 하나의 점화식으로 DP를 구성하면 가뿐하게 AC를 받을 수 있다.

codeground : 대피소 [SCPC 2016 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=28 떠올릴 수 있는 가장 간단한 방법은 v번의 다익스트라를 하는 것. 하지만 이 방법은 간단히 시간초과임을 알 수 있다. 그렇다면 다른 해결방법이 있을까? 이 문제는 단 한번의 다익스트라로 해결이 가능하다.heap에 모든 대피소를 넣고 시작하면 된다. 또한, 경로의 길이가 같을 경우 대피소번호가 작은 대피소를 선택하는 것도 동시에 해결해주면 된다. 알고리즘을 간략히 써보면, 1. 새로운 경로가 더 작으면 힙에 push. dist 갱신 위에께 일반적인 다익스트라 알고리즘이라면, 이문제에 해당하는 알고리즘은 다음과 같다. 1. 새..

codeground : 캠퍼스와 도로(1) [SCPC 2015 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=15 SW역량테스트를 맞아 codeground문제들도 써보려고 한다.그 첫번째 문제..이 문제는 v번의 다익스트라 알고리즘으로 떠오르는 아이디어 그대로 해결할 수있다.시간복잡도는 v*(v+e)log(v+e)가 되어 시간안에 충분히 해결할 수 있을 듯 하다.다만, 방문하는 도시까지의 거리가 같을 때가 문제 ㅜㅜ...힙에 push하기 전에 방문노드를 체크해주면 왜안되는지 모르겠다. 아직 밝혀내지 못했음... 해결한 방법은, 코드가 조금 길어지긴하지만 스타팅 지점인 v번째 도시에 대해 다익스트라 알고리즘으로 모든 경로까지..

boj 2381 : 최대거리 https://www.acmicpc.net/problem/2381 n^2만에 해결할 수 있는 방법은 간단히 떠올릴 수 있다. 하지만 n이 최대 50000이기 때문에 시간초과. nlongn 이하의 해결법을 찾아야한다. 답은 (x+y의 최대값) - (x+y의 최소값), (x-y의 최대값) - (x-y의 최소값) 둘 중 큰값이 답이다.응??? 증명을 해보자.1. (x+y의 최대값) - (x+y의 최소값)이 답일 경우1.1 앞 괄호를 (x1,y1), 뒷 괄호를 (x2,y2)라 두면,1.2 x1 > x2이고, y1 > y2의 경우만 가능하다.1.3 그렇다면 만약 x1 < x2이거나 y1 < y2라면? 답에 모순이 생기지 않을까?x1 < x2이거나 y1 < y2라도 상관없다는것을 증명해..

boj 1238 : 파티 https://www.acmicpc.net/problem/1238 시간초과가 나지 않겠나? 라는 의문을 가졌지만, 잘 생각해본다면 단 두번의 다익스트라로 해결이 가능하다.^^.. 우선 파티장소에서 모든마을까지는 단순한 다익스트라의 구현으로 구할 수 있다.그렇다면 각각의 마을에서 파티장소까지의 경로는 어떻게 구할 수 있을까?답은 경로를 거꾸로 저장한 edge를 저장하는 것으로 해결 가능하다.a->z 경로의 최단거리는 반대경로의 최단거리와 같다. 호기심에 floyd로 시간초과인지 테스트해보았지만 역시나 시간초과^^