kthng

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