728x90 동적계획법 썸네일형 리스트형 [백준알고리즘] 10164번: 격자상의 경로 -Python [백준알고리즘] 10164번: 격자상의 경로 -Python https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 경우의 수를 구해주는 문제이다. DP를 사용해 모든 경우의 수를 구해주면 된다. O표시가 없는 경우(k=0인 경우)에는 시작점에서 끝점까지 이동할 수 있는 모든 경우의 수를 구해주.. 더보기 [백준알고리즘] 5557번: 1학년 -Python [백준알고리즘] 5557번: 1학년 -Python https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 별생각 없이 딕셔너리를 이용해서 풀었다. 현재까지의 누적 계산량과 인덱스를 쌍으로 하는 튜.. 더보기 [백준알고리즘] 1937번: 욕심쟁이 판다 -Python [백준알고리즘] 1937번: 욕심쟁이 판다 -Python https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 재귀를 사용한 동적 계획법으로 문제를 풀었다. 시작점이 주어지지 않았기 때문.. 더보기 [백준알고리즘] 1890번: 점프 -Python [백준알고리즘] 1890번: 점프 -Python https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 재귀를 사용한 동적계획법으로 문제를 풀었다. 동적 계획법으로 풀 수 있는 문제이다 보니 여러 .. 더보기 [백준알고리즘] 2163번: 초콜릿 자르기 -Python [백준알고리즘] 2163번: 초콜릿 자르기 -Python https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 처음에는 Dynamic Programming 방식으로 풀었다. NxM크기의 .. 더보기 [백준알고리즘] 14501번: 퇴사 -Python [백준알고리즘] 14501번: 퇴사 -Python https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사하기 전까지 가장 많은 돈을 벌 수 있도록 해야 한다. 며칠에 걸리는 상담인지에 따라 며칠간 상담을 추가로 할 수 없을 수도 있다. 나는 dp처럼 문제를 풀었다. 1일 차부터 순서대로 선택을 하면서 각 날짜의 일을 했을 때 최대로 벌 수 있는 금액을 유지한다. 그리고 이 최대로 벌 수 있는 금액에 다음에 할 수 있는 일 들의 금액을 더하면서 유지한다. 음... 코드를 보는 게 설명보다 쉬워 보인다... 배열로 비교를 해보도록 하자. 처음의 값은 다음과 같다. data = [(3, .. 더보기 [백준알고리즘] 2839번: 설탕 배달 -Python, C++ [백준알고리즘] 2839번: 설탕 배달 -Python, C++ https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 www.acmicpc.net 설탕 n만큼을 최소의 묶음을 챙겨서 가져갈 수 있는 방법은 최대한 5의 .. 더보기 [백준알고리즘] 1463번: 1로 만들기 -Python [백준알고리즘] 1463번: 1로 만들기 -Python https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 계획법(DP)문제이다. 이제 이런 거에 연연하면 안 될 것 같은 게.... DP 문제임을 알게 되니까 당연히 케이스를 나눠서 해야지! 재귀를 부르고 Top-Down 형태로 할거야! 이런 식으로 생각이 들게 된다. 그런데 이 문제는 이런 방식으로 풀었더니 안됐다... 그러고 보니 -1이 자꾸 거슬렸다. -1 때문에 결국에는 1부터 N까지 모든 수의 최소 연산 수를 계산하기 때문이다. 그러다 보니 초과가 뜬것이라 생각하고 Bottom-Up 형태로 1부터 .. 더보기 이전 1 2 3 4 다음