noj.am/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 어떤 분이 열심히 백금광에서 백금을 캐고 계시길래 구경해볼겸 백금광에 놀러갔다. 근데 백금광 안에 웬 다이아몬드 광산이 있어서 좀 놀랐다. 아무튼 풀어봤다. 아쉽게도 2트를 했고 40분 정도가 걸렸다. 아이디어는 처음부터 맞은 것 같다. 처음에는 크기 제한을 보고 누적합을 써서 풀어야겠다는 생각이 들었고, 길이를 변수로 누적합을 만들었다. 이를 DP를 활용해서 모든 점에 대한 길이들을 다 담았고, 모든 점에서 길이들이 맞는지 확인하는 방식으로 답을 구했다. 처음 틀린 이유는 예외 처리를 ..
이번엔 DP를 최적화하는 심화 기법에 대해서 알아보겠다. CHT, Convex Hull Optimization이라고도 불린다. 번역하면 볼록 껍질을 이용한 최적화 정도가 되겠다. 이름에서 볼록 껍질이 나오다시피 볼록 껍질을 응용해서 하나의 쿼리의 시간복잡도를 줄이는 것이다. 대표적으로 \(O(N)\)의 쿼리를 \(O(\log N)\)으로 줄이는 최솟값/최댓값 쿼리가 있다. 하지만 항상 사용할 수 있는 최적화 기법은 아니고, 최솟값/최댓값을 구하고자 하는 배열의 일부가 단조감소 혹은 단조증가할 때만 사용할 수 있다. 이렇게 말하면 너무 어려우니 예시를 보자. 아 그리고 이제 글에 \(\LaTeX\)이 적용이 돼서 기분이 너무 좋다. 이제 N^2나 a_1같은 표기 안봐도된다. 화살표도 \(\Rightarro..
요즘 새로운 DP 방법들 찾아보면서 뭔가 알아야 되는거도 많아지고 해서 정리도 할겸 DP문제 푸는걸 정리해서 올려보고 싶었다. 겨울에 열심히 DP 파면서 어려운 문제도 4~5시간씩 써가며 풀었는데 3월되서는 3개는 풀었나? 싶어서 DP 푸는걸 기록해볼거다. 난이도 있는 백준(또는 정올)문제랑 내가 생각했던 간단한 풀이를 같이 남겨 나중에 보기도 편하게 하고, 아이디어랑 이런건 따로 더 쓸거다. 난이도는 한 골드 상위에서 플래, 다이아까지 공부할거다. DP말고도 그리디나 자료구조 일지도 쓰고싶은데 그건 시간될때.. 일단 겨울에 푼 어려웠던 문제 하나 noj.am/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점..