두부의 코딩일기

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 🔶 풀이 처음에 완전 탐색으로 풀어보려했지만 n과 m의 범위를 보고 바로 후퇴... 어떻게 풀어야할지 감이 안잡혀서 [알고리즘 분류]를 봤더니 다이나믹 프로그래밍이였다. dp 알고리즘의 기본은 점화식을 찾아야된다. 점화식을 찾는건 정말 힘들다. 소소한 팁을 주자면 공책에 적어보면 규칙이 보인다. 가장 큰 정사각형의 넓이를 구해야한다. 우선, N=1 혹은 M=1인 상황은 무조건 1을 출력한다. (문제에서 배열의 크기는 1부터 1000이라고 명시되어있음) 2x2 이상의 ..

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 풀이 "호텔의 고객을 적어도 C명 늘리기 위해 형택이가 투자해야하는 돈의 최솟값을 구하시오." 문제 요구사항에서 주목해야할 건 "적어도 C명"이다. 만약 목표치가 10명인데 11명, 12명을 모집했을 때가 더 비용이 적게 든다면 그 비용을 출력해야한다. 예제 2번을 보면 쉽게 이해할 수 있다. 3명 모집 -> 1원 6명 모집 -> 2원 9명 모집 -> 3원 10명 모집 -> 6원 11명 모집 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 한 달 후면 국가의 부름으로 잡혀가는 준서가 여행을 간다고 한다. 준서가 견딜 수 있는 무게 내에서 최고의 가치를 찾는 문제이므로 dp 문제이다. dp문제는 점화식만 찾으면 쉽게 해결할 수 있는 알고리즘으로 개인적인 팁을 주자면 필자는 dp 문제를 보면 공책에다가 표를 그려서 완전 탐색을 해본다. 물론 표를 그려본다고 쉽게 발..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 이번 문제는 dp문제로 제목이 정말 맘에 든다. 퇴사까지 N일을 앞두고 있는 백준이에게 상담 시간과 금액이 주어졌다. 퇴사까지 최대한 많은 상담 비용을 찾는 문제이다. 이 문제에는 한 가지 경우의 수가 존재한다. 예제 1번을 살펴보면 다음과 같다. 1일에 예약된 상담의 시간은 3일이다. 즉, 4일차가 되는 날에 상담 비용 10을 얻을 수 있다. 2일에 예약된 상담의 시간은 5일이다. 즉, 7일차가 되는 날에 상담 비용 20을 얻을 수 있다. 3일에 예약된 상담의 시간은 1일이다. 즉, 4일차가 되는 날에 상담 비용 10을 얻을 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 이번 문제는 dp 문제로 설명이 너무 어렵게 되어있다. 간단하게 설명하자면 문제의 조건은 "인접한 집끼리 색이 겹치면 안된다."이다. 모든 dp문제는 점화식만 찾으면 쉽게 해결할 수 있다. 1번 예제를 보면서 점화식을 찾아보겠다. 1번 예제에서 최소값만 찾아서 누적합을 하면 다음과 같다. 최소값만 찾아서 진행했더니 문제의 조건 "인접한 집끼리 색이 겹치면 안된다." 를 ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 최근에 풀어본 포도주 시식 문제(2156번)와 거의 똑같아서 점화식을 바로 찾을 수 있었다. 이 문제에서 제공하는 조건은 총 3가지이다. 1. 한 계단 혹은 두 계단을 오를 수 있다. 2. 연속된 3개의 계단은 밟을 수 없다. 3. 마지막 계단은 반드시 밟아야한다. 쉽게 생각해서 i번째 칸에 대해서 두 칸 전(i-2) + 현재 칸(i) 와 세 칸 전(i-3) + 한 칸 전(i-1) + 현재 칸(i)를 비..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 이번 문제는 다이나믹 프로그래밍(dp) 문제이다. 다이나믹 프로그래밍에는 Bottom-up 방식과 Top-down 방식이 있는데 이 문제에서는 둘 다 사용이 가능하다. 필자는 Bottom-up 방식이 먼저 떠올라서 반복문으로 풀었다. 우선 이 문제에는 "큰 수로 나누는 게 무조건 좋다"의 함정이 있다. 예제 2번을 보면 쉽게 이해할 수 있다. 큰 수(2)로 먼저 나누는 방법은 10 → 5 → 4 → 2 → 1로 4번의 연산을 거치지만, 1을 먼저 빼고 3으로 나누게 되면 10 → 9 → 3 → 1로 3번의..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 이번 문제는 그냥 수학적 사고 테스트 문제이다. 3kg과 5kg 두 가지의 설탕 봉지를 이용해서 배달하려는 무게를 정확하게 맞추어 봉지의 개수를 최소한으로 하는 게 목표이다. 처음엔 문제를 너무 어렵게 생각했었다. 간단하게 생각해서 5kg의 설탕 봉지를 많이 사용하면 그만큼 봉지의 개수를 최소한으로 할 수 있다는 걸 생각하지 못 했다. 이걸 알게 된 후에는 문제가 엄청 쉬워졌다. 그냥 배달하려는 무게가..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 동적 계획법 (dp) = 다이나믹 프로그래밍으로 접근하면 되는 문제이다. dp 관련 알고리즘은 해당 문제가 제시하는 조건에 맞는 점화식만 찾으면 쉽게 해결할 수 있다. 찾기가 어려울뿐... 1. 포도주 잔을 선택하면 무조건 다 마신 후에 제자리에 놓아야 한다. 2. 인접한 포도주를 3잔 연속으로 마실 수 없다. 위 조건에 맞는 점화식을 발견하려면 최소 4번째 포도주까지 진행해봐야한다. 우선 포..