본문 바로가기
728x90

코딩테스트/다이나믹 프로그래밍6

[python] 백준 13904번: 과제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net # 참고블로그 https://whitehairhan.tistory.com/337 https://velog.io/@heyksw/Python-%EB%B0%B1%EC%A4%80-gold-13904-%EA%B3%BC%EC%A0%9C 문제가 처음 읽었을 때 쉽게 이해가 되지 않았다. 그래서 블로그를 참고하면서 풀었다. 결론적으로 뒤에서 부터 가능한 과제를 그리디 방법으로 풀면 되는 문제였다. 이 문제의 경우 푸는 방법이 그리디말고도 우선순위 큐로 푸.. 2023. 1. 8.
<PART 3> Q33. 백준 14501번: 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 # 백준 14501번 n = int(input()) t = [] p = [] dp = [0] * (n+1) #dp를 위한 빈테이블 max_value = 0 for i in range(n): x,y = map(int,input().split()) t.append(x) p.append(y) #리스트를 거꾸로 확인 for i in range(n-1,-1,-1): time = t[i] + i #상담이 기간안에 끝날 경우 if time 2022. 11. 17.
<PART 3> Q32. 백준 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net - bfs푼 경우 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #Q32.triangle n = int(input()) graphs = [[0]*n for _ in range(n)] # nxn크기로 만들기 for i in range(n): graphs[i] = list(map(int.. 2022. 11. 17.
<PART 3> Q31.금광 - Q31. 금광 n x m 크기의 금광이 있습니다. 금광은 1x1크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. 만약 다음과 같이 3x4 크기의 금광이 존재한다고 가정합시다. 1 3 3 2 2 1 4 1 0 6 4 7 가장 왼쪽 위의 이치를 (1,1) 가장 오른쪽 아래의 위치를 (n,m)이라고 할 때, 위 예시에서는 (2,1)->(3,2)->(3,3)->(3,4) 위치로 .. 2022. 11. 17.
<PART 2> 다이나믹 프로그래밍 예제 1로 만들기 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지입니다. A. X가 5로 나누어떨어지면, 5로 나눈다. B. X가 3으로 나누어떨어지면, 3으로 나눈다. C. X가 2로 나누어떨어지면, 2로 나눈다. D. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 합니다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어 정수가 26이면 1. 26-1=25 2. 25/ 5 = 5 3. 5/ 5 =1 으로 3번의 연산이 최솟값입니다. (1 2022. 11. 7.
<PART 2> 다이나믹 프로그래밍 다이나믹 프로그래밍, 동적 계획법: 연산속도와 메모리공간 최대한 활용하는 방법 이는 중복되는 연산을 줄일 수 있습니다. 다이나믹 프로그래밍의 기본적인 아이디어를 먼저 소개한 후에 2가지 방식인 탑다운, 바텀업을 설명할 것입니다. 여기서의 다이나믹의 뜻은 '프로그램이 실행되는 도중에'라는 의미입니다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있습니다. 우선 피보나치 수열을 코드로 간단한게 표현하면 다음과 같습니다. 이처럼 단순히 재귀함수를 사용하여서 해결할 수 있습니다. 그러나 여기서 n이 기하급수적으로 커지면 시간 표기법이 O(2^N)정도로 올라가서 심각한 문제가 생길 수 있습니다. 항상 다이나믹 프로그래밍을 사용할 수 없으며, 다음 조건을 만족할 때 사용할 수 있습니다. .. 2022. 11. 7.
728x90

티스토리툴바