dp
(C++) 백준 1915번 [가장 큰 정사각형]
백준 1915번 문제 [가장 큰 정사각형] 알고리즘 포스팅을 시작해보겠습니다. 다이나믹 프로그래밍 문제인데, 처음에 다른 방식으로 풀었다가 시간초과가 나서 그제서야 DP로 방향을 잡고 풀었으나, 추상화와 해결방법을 쉽게 찾지 못하다가 겨우 푼 문제입니다. 1. 문제 해결 방법 구상하기 - 입력값부터 받는 데 문제가 생깁니다. 그냥 cin 으로 해서 int값으로 입력받을 수는 없습니다. - 그렇다면 scanf를 이용하여 %1d 로 받을 수도 있고, 문자열 형태로 입력을 받은 후, -'0'을 해주어 int 값으로 다시 변환해줄 수도 있습니다. - 입력받은 후에 문제 해결은 어떻게 해야 할까요? - 다이내믹 프로그래밍이란 추상화, 즉 점화식이 굉장히 중요합니다. 위의 그림에서 가장 중앙에 있는 정사각형을 기준..
(C++) 백준 1149번 [RGB거리]
안녕하세요 평범한 컴공생입니다! 백준 1149번 문제 [RGB거리] 알고리즘 포스팅을 시작해보겠습니다. 전형적인 DP 문제인데, 처음에 DFS로 접근을 하려했다가 시간초과가 나서 DP로 방법을 바꾸니 해결할 수 있었습니다. 1. 문제 해결 방법 구상하기 - 빨간색으로 집을 칠하면 그 다음집은 파란색 또는 초록색으로밖에 칠할 수 없다. - 초록, 파랑의 경우도 마찬가지이다. - 두 번째 집에서 예를 들어 RED로 칠한다고 하면 첫 번째 집에서의 GREEN, BLUE를 선택한 값 중 더 작은 값에 RED를 칠했을 때의 값을 더한 것이다. - 세 번째 집에서 예를 들어 RED로 칠한다고 하면 두 번째 집을 BLUE로 했을 때 소요되는 최솟값과 GREEN로 했을 때의 최솟값 중에 더 작은 값에 RED로 칠했을 ..