본문 바로가기
728x90

DP

[백준알고리즘] 2096번: 내려가기 -Python [백준알고리즘] 2096번: 내려가기 -Python https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 최대와 최소를 동시에 구해주어야 한다. 처음에는 large와 small을 구해주는 리스트를 처음에 주어진 크기와 같은 크기로 이중 리스트를 만들어 주었었다. 메모리 제한이 4MB이기 때문에 메모리 초과가 발생하게 되는데, 그래서 아래처럼 크기가 3인 리스트 두 개를 이용해서 최대 점수와 최소 점수를 구하도록 했다. n = int(input()) table = .. 더보기
[백준알고리즘] 1915번: 가장 큰 정사각형 -Python [백준알고리즘] 1915번: 가장 큰 정사각형 -Python https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이게 왜이리 오래 걸렸는지 모르겠다. 엄청 많이 틀렸다.. 틀린 이유는 시간초과였는데, 결국 다른 풀이들을 찾아봤다. 처음에 시간 초과가 걸리게 푼 방법은 재귀 방식을 사용했다. 현재 위치를 정사각형의 왼쪽 위 꼭짓점이라고 생각을 하고 만들어지는 최대 정사각형의 변을 구했다. 다음 세개의 길이의 최솟값+1을 해줌으로써 현재 구할 수 있는 정사각형의 가장 큰 길이를 구했다. 가로로 이어지는 길이 세로로 이어지.. 더보기
[백준알고리즘] 1965번: 상자넣기 -Python [백준알고리즘] 1965번: 상자넣기 -Python https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 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 재귀를 사용한 동적계획법으로 문제를 풀었다. 동적 계획법으로 풀 수 있는 문제이다 보니 여러 .. 더보기
[백준알고리즘] 2294번: 동전 2 -Python [백준알고리즘] 2294번: 동전 2 -Python https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 동적 계획법을 사용해서 문제를 풀었다. 주어진 코인으로 1부터 k까지 차례대로 만들 때 사용하는 코인의 최소 개수를 저장하도록 했다. 각 금액을 만들 때 모든 코인들을 사용해본다. 현재 만들려는 금액이 t라면, 각 코인을 사용해서 t가 되었다고 생각을 하면 된다. 주어진 예제입력을 예시로 들어보겠다... 더보기
[백준알고리즘] 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, .. 더보기
728x90

티스토리툴바