본문 바로가기
728x90

동적 프로그래밍

[백준][파이썬] 2579 계단 오르기
백준 문제풀이 2023. 2. 15. [백준][파이썬] 2579 계단 오르기 1.문제 분석 동적 프로그래밍을 활용하는 문제 계단에 쓰인 숫자의 합을 최대로 하는 문제 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 2. 기본 아이디어 1,2,3 번째 계단까지 미리 합을 구해 score에 넣어둔다. 이후 맨 마지막 계단을 밟아야 한다라는 조건에 맞춰 max함수를 통해 2가지 경우 중 최대 값을 고른다. 3.문제 풀이 앞서 말했듯 마지막 계단을 밟는다는 조건에는 2가지 경우가 있다. 첫째, 맨 위에서 두번째 계단을 밟는 경우 둘째, 맨위에서 세번째 계단을 밟는 경..
[백준][파이썬] 1932 정수 삼각형
백준 문제풀이 2023. 2. 15. [백준][파이썬] 1932 정수 삼각형 1.문제 분석 정수 삼각형을 내려오면서 최대 합을 구하는 문제 동적 프로그래밍을 활용하는 문제 2. 기본 아이디어 정수 삼각형의 각 층에서 max함수를 활용해 최대값을 구한다. 2차원 리스트로 정수 삼각형을 구현한다. 3.문제 풀이 이 문제의 경우 정수 삼각형이 주어지기 때문에 숫자의 위치에 따라 위에서 받아올 수 있는 숫자가 달라진다. 예를 들어 이 삼각형의 경우 위에서부터 3층에 8, 1, 0 이 있는데 8로 내려올 경우 자신과 같은 tri[i - 1][0] 위치의 3을 더할 수 밖에 없고 0의 경우도 tri[i - 1][j - 1] 위치의 8만 더할 수 있다. 하지만 1의 경우 tri[i - 1][j - 1], tri[i - 1][j] 중 더 큰 값을 고르게 할 수 있다. 이후 맨 아래까지 내려왔을..
백준 문제풀이 2023. 2. 2. [백준][파이썬] 1149 RGB거리 1.문제 분석 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 똑같은 색이 연속되지 않도록 R, G, B 색깔로, 비용을 최소로 집을 칠하는 문제 2. 기본 아이디어 첫 집의 색깔이 R, G, B 중 어느 것이냐에 따라 각각의 답을 구한 후 최솟값을 찾는다. 3.문제 풀이 입력을 2차원 리스트로 받은 후 첫 집의 색깔을 R로 지정했다면 G, B 중 더 적은 비용인 색을 두번째 집에 칠한다. 그 두번째 집을 다시 리스트에 저장한 후 반복한다. 코드만 두고 해석하면 (i - 1)까지의 누적 비용중 자신과 같은 색깔을 제외한 나머지 두 개의 비용합 중 작은 값을..
백준 문제풀이 2023. 2. 2. [백준][파이썬] 1912 연속합 1.문제 분석 인접한 숫자의 합의 최댓값을 만드는 문제 2. 기본 아이디어 파이썬의 max함수를 활용한다. 순차적으로 연속된 합을 비교한다. 3.문제 풀이 i번째 수와 i번째 + i - 1번째 수의 합을 비교하여 큰 쪽을 dp[i]에 저장하는 방식이다. 코드로 구현 n = int(input()) dp = list(map(int, input().split())) def partSum(): for i in range(1, n): dp[i] = max(dp[i] + dp[i - 1], dp[i]) return max(dp) print(partSum()) return할 때에도 max함수를 통해 최대 연속합을 찾았다.
[백준][파이썬] 9461 파도반 수열
백준 문제풀이 2023. 2. 1. [백준][파이썬] 9461 파도반 수열 1.문제 분석 수열의 규칙을 발견해야 한다. 동적 프로그래밍으로 구현한다. 2. 기본 아이디어 파도반 수열의 규칙: P(N) = P(N - 2) + P(N - 3), P(0) = P(1) = P(2) = 1 두번째 규칙: P(N) = P(N - 1) + P(N - 5) 3.문제 풀이 처음 수열을 봤을 때, 먼저 떠오른 규칙은 두번째 규칙이었다. 한 변의 길이가 3인 삼각형부터 보면, 바로 이전 삼각형과 맨 처음 삼각형의 변으로 만들어졌다. 한 변의 길이가 4인 삼각형은 바로 이전 삼각형과 두번째 삼각형의 변으로 만들어졌다. 이 느낌을 살려서 P(N) = P(N - 1) + P(N - 5) 라는 규칙을 발견했다. 코드로 구현 n = int(input()) def padovan(t): dp = [0] * 1..
백준 문제풀이 2023. 1. 29. [백준][파이썬] 1904 01타일 1.문제 분석 00타일과 1 타일만으로 길이가 n인 이진수를 만드는 문제 문제를 잘 정리하는 것이 중요한 문제 동적 프로그래밍을 사용하는 문제 2. 기본 아이디어 문제를 자신의 방법으로 잘 정리해본다. 메모리 초과를 막기 위해, 문제에 제시된 15746으로 잘 나눠준다. 재귀가 아닌 리스트를 통해 값을 저장해나간다. 3.문제 풀이 문제를 자세히 들여다보자. 이 문제가 동적 프로그래밍 문제라는 것 자체가 힌트다. 어디선가 분명 규칙과 반복계산을 찾을 수 있을 것이다. 따라서 문제에서 주어진 n과 이진수열의 개수를 확인해보기로 했다. n = 1 >>> 1 1개 n = 2 >>> 00, 11 2개 n = 3 >>> 100, 001, 111 3개 n = 4 >>> 1111, 1001, 0011, 1100, 00..
백준 문제풀이 2023. 1. 28. [백준][파이썬] 9184 신나는 함수 실행 1.문제 분석 제시된 의사코드를 동적 프로그래밍을 사용하여 구현하는 문제 2. 기본 아이디어 계속해서 값을 계산하는 것이 아닌, 값을 저장하는 구조로 만든다. (메모이제이션) 3.문제 풀이 문제에 제시된 재귀함수 의사코드 if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 코드로 구현 def w(a, b, c): if(a 20): return w(20, 20..
백준 문제풀이 2023. 1. 28. [백준][파이썬] 24416 알고리즘 수업 - 피보나치 수 1 1.문제 분석 재귀함수와 동적프로그래밍을 비교하는 문제 2. 기본 아이디어 의사코드를 코드로 구현한다. 3.문제 풀이 cnt1, cnt2 = 0, 0 def fib(n): global cnt1 if(n == 1 or n == 2): cnt1 += 1 return 1 #코드 1 else: return (fib(n - 1) + fib(n - 2)) def fibonacci(n): global cnt2 f = [1, 1] for i in range(3, n + 1): f.append(f[i - 2] + f[i - 3]) # 코드 2 cnt2 += 1 return f[n - 1] n = int(input()) fib(n) fibonacci(n) print(cnt1, cnt2) 위 코드의 코드 1과 코드 2 부분..
728x90

티스토리툴바