본문 바로가기

전체 글

 (662)
081 - 가방문제(Knapsack 알고리즘) 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있 다는 뜻입니다. ▣ 입력설명 첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다. 두 번째 줄부터 각 보석의 무게와 가치가 주어진다. 가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다. ▣ 출력설명 첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다...
080 - 알리바바와 40인의 도둑(Top-Down) 이번에는 079 문제를 다이나믹 방식인 Top-Down 과 Bottom-Up 을 비교하고 속도 차이를 알아보겠습니다. import time import sys name = 'in5.txt' sys.stdin = open(name, 'rt') def DFS(x, y): if dy[x][y] > 0: return dy[x][y] if x == 0 and y == 0: return a[0][0] else: if x == 0: dy[x][y] = DFS(x, y-1)+a[x][y] elif y == 0: dy[x][y] = DFS(x-1, y)+a[x][y] else: dy[x][y] = min(DFS(x, y-1), DFS(x-1, y))+a[x][y] # print(x, y, dy[x][y]) return ..
079 - 알리바바와 40인의 도둑(Bottom-Up) 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다. 해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다. 즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하세요. 만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. ▣ 입력설명 첫 번째 줄에는 자연수..
078 - 가장 높은 탑 쌓기 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. ▣ 입력설명 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의..
077 - 최대 선 연결하기 왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 합니다. 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있습니다. 오른쪽의 번호 정보가 위부터 아래 순서로 주어지만 서로 선이 겹치지 않고 최대 몇 개의 선 을 연결할 수 있는 지 구하는 프로그램을 작성하세요. 위의 그림은 오른쪽 번호 정보가 4 1 2 3 9 7 5 6 10 8 로 입력되었을 때 선이 서로 겹치지 않고 연결할 수 있는 최대 선을 개수 6을 구한 경우입니다. ▣ 입력설명 첫 줄에 자연수 N(1
076 - 최대 부분 증가수열 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다. ▣ 입력설명 첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다. ▣ 출력설명 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. ▣ 입력예제 1 8 5 3 7 8 6 2 9 4 ▣ 출력예제 1 4 #import sys #sys.stdin = open('in5.txt', 'rt') if __..
075 - 돌다리 건너기(Bottom-Up) 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요? ▣ 입력설명 첫째 줄은 돌의 개수인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다. ▣ 입력예제 1 7 ▣ 출력예제 1 34 #import sys #sys.stdin = open('in.txt', 'rt') if __name__ == '__main__': n = int(input()) print(f'n:{n}') # 돌 개수가 n개 이지만, 개울을 건널러면 n+1 까지 도달해야 한다 res = [0]*(n+1) res[0..
074 - 계단오르기(Top-Down : 메모이제이션) 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? ▣ 입력설명 첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 첫 번째 줄에 올라가는 방법의 수를 출력합니다. ▣ 입력예제 1 7 ▣ 출력예제 1 21 #import sys #sys.stdin = open('in.txt', 'rt') def DFS(L): if a[L] > 0: return a[L] if L == 1 or L == 2: a[L] = L return a[L] else: a[L] = DFS(L-1)+DFS(..

티스토리툴바