kthng

boj 7579 : 앱https://www.acmicpc.net/problem/7579 아래와 같이 점화식을 정의한 DP 배열로 문제 해결 가능하다.DP[i] : i의 비용만큼 들였을 때, 확보할 수 있는 최대 메모리 DP[i] = max(DP[i], DP[i - cj] + Memory[j]) 물건의 개수는 최대 100개이고,  0 ≤ c1, ..., cN ≤ 100 이므로, DP 배열은 DP[100001]과 같이 잡으면 되며,전체 (DP배열 크기) * (물건의 개수) 만큼 시간 소요된다.

boj 2467 : 용액https://www.acmicpc.net/problem/2467 정렬된 정수 배열이 주어진다.주어진 배열에서 2개의 정수를 뽑아 그 합을 0에 가장 가깝게 만들면 된다.기본적으로 2개 모두 뽑아 확인하는 방법은 N^2이고, N이 10만이므로 시간 초과가 난다.two pointer 방법을 이용한다. *L+*R이 0보다 크다면 R을 감소시키며, *L+*R이 0보다 작다면 L을 증가시킨다. Greedy + Two Pointer로 문제를 해결할 수 있다.Greedy Solution으로 문제를 해결하기 위해서는 "순간 최적이 전체 최적이다."라는 것을 증명해야하나,직관적으로만 알고, 증명하진 못하였다. -> Prove By Solving으로 증명했다^^;

boj 1806 : 부분합https://www.acmicpc.net/problem/1806  L~R사이의 sum이 문제에서 주어진 S보다 작다면 R을 증가시킨다,S보다 크다면 "R-L+1"은 정답 후보가 되며, L을 증가시킨다.정답 후보들 중 가장 작은 값을 정답으로 출력하면 된다.

https://www.acmicpc.net/problem/1647 최소 비용의 간선으로 두 마을을 나누는 문제이다.MST(Minimum Spanning Tree)를 약간만 응용하면 가능한 문제이다. MST를 푸는 두 알고리즘 중, 크루스칼 알고리즘으로 MST문제를 해결하다가 말면 성공적으로 도시를 분할할 수 있다.집의 개수가 N개라면 가장 적은 비용의 N-1개의 간선만 연결한다면 모든 집을 최소 비용으로 연결할 수 있다.여기서, 1개만큼 간선을 덜 연결하면, 즉 N-2개만큼의 간선을 연결하면 2그룹의 마을로 나누어지면서 문제가 해결된다. 문제에서는 언급하지 않았지만, 좀더 나아가 3그룹, 4그룹의 마을로 나누기 위해서는 어떻게하면 좋을까?더보기마찬가지로 N-3, N-4개의 간선만 연결하면 3그룹, 4그룹..

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 문제..