OSgood의 개발일기

문제 링크 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 전형적인 탐색 문제다. bfs를 해도 되고 dfs를 해도 상관 없다. 필자 같은 경우는 dfs가 좀 더 편하기 때문에 dfs로 코드를 작성..

이번 포스팅에서는 Dynamic Programming의 개념적인 내용을 살펴보겠다. 자세한 적용 예는 좀 더 공부한 후에 더 자세히 포스팅하도록 하겠다. Dynamic Programming는 간단히 말해 부분 문제의 해를 결합해 문제를 해결하는 것을 의미한다. 부분 문제가 서로 중복될 때,즉 부분 문제가 다시 자기 자신의 부분 문제를 공유할 때 적용할 수 있다. 부분문제를 푸는 것은 분할정복 기법(재귀방법)과 비슷하지만 다른 점이 있다. 분할 정복 기법 VS Dynamic Programming 분할 정복 기법(재귀적 방법) Dynamic Programming 부분 문제를 단순히 반복적으로 계산하여서 해결한다. 필요 이상의 계산이 필요하기 때문에 시간이 오래걸릴 수 있다. 부분 문제를 해결한다는 점은 분할..