동적계획법 [Python] 백준 1149: RGB 거리 문제를 보자마자 이코테에 나온 개미 전사 문제가 떠올랐다. 개미전사는 1차원이고 이건 2차원이라는 점이 조금 다르다. 현재 집에서 R(0)을 선택했을 경우 다음 집은 G(1), B(2)를 선택 할 수 있다. 현재 집에서 G(1)을 선택했을 경우 다음 집은 R(0), B(2)를 선택 할 수 있다. 현재 집에서 B(2)을 선택했을 경우 다음 집은 R(0), G(1)를 선택 할 수 있다. 현재 집... 백준코딩테스트 연습파이썬동적계획법동적계획법 [Python] 백준 1932번: 정수 삼각형 1부터 n번째 줄까지 정삼각형 형태의 배열이므로 j의 범위를 i+1로 해서 순회 한줄씩 내려오면서 이전값과 현재값을 더했을 때의 최대값을 선택하면서 내려오면 된다. 이전 값은 현재값을 기준으로 바로 위에서 내려올 경우와 왼쪽 위에서 내려올 경우를 생각할 수 있다. 바로 위에서 내려올 경우는 i==j 라고 할 수 있고, 이 경우 오른쪽에서 내려올 수 있는 숫자가 없으므로 right=0이 된다.... 코딩테스트 연습파이썬동적계획법동적계획법 [알고리즘][BOJ]11049_행렬 곱셈 순서 💡 생각하자 [Dynamic Programming(동적 계획법)의 개발절차] 1. 재귀 관계식(recursive property) 세우기 2. 상향식 방법(bottom-up)으로 답 구하기 재귀 관계식 A[i][j] : M(i)부터 M(j)까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 A[i][j] = minimum(A[i][k] + A[k+1][j] + d(i-1)d(k)d(j)) (i ... C동적계획법boj알고리즘C [알고리즘][BOJ]2315_가로등 끄기 1. 재귀 관계식(recursive property) 세우기 주어진 예시 상황에 대해서 생각해보자. 마징가는 5번 가로등에서 출발한다. 다음으로는 4번 또는 6번으로 갈 수 있다. 4번으로 간 경우를 생각해보자. 그렇다면 예를 들어 5->4->3->2->1->6 인 경우를 살펴보자. 3->2 : 1초 => 2⨯1 + 10⨯1 + 19⨯1 = 31 2->1 : 8초 => 2⨯8 + 19⨯8 =... C동적계획법boj알고리즘C [Algorithm] 📐프로그래머스 정수 삼각형 0. 문제 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 ... 프로그래머스동적계획법동적계획법 [알고리즘] 프로그래머스 - 2 x n 타일링 프로그래머스알고리즘DP동적계획법DP [Algorithm] 🦘외발 뛰기 0. 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗... 종만북algospot동적계획법algospot [알고리즘][BOJ]11057_오르막 수 💡 생각하자 [Dynamic Programming(동적 계획법)의 개발절차] 1. 재귀 관계식(recursive property) 세우기 2. 상향식 방법(bottom-up)으로 답 구하기 N=1일 때 0, 1, ⋯, 9까지 총 10개가 존재한다. N=2일 때 오르막 수를 AB라고 두면, A는 0부터 9까지 가능하다. (0으로 시작할 수 있다는 조건에 의해) 그러면 A=0이고 B는 0~9, ... 알고리즘동적계획법CbojC [Algorithm] 🚡백준 2579 계단오르기 <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 1.계단은 한 번에 한 계단씩 또는 두 계단씩 오를... 백준동적계획법동적계획법 [Algorithm] 🛣️백준 1520 내리막 길 0. 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능... 백준동적계획법동적계획법 [Algorithm] 🍷백준 2156 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 1.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을... 백준동적계획법동적계획법 210115 | 백준 동적계획법 1003 | C++ 전체 문제를 작은 문제로 단순화한다. -> 부분 문제를 정의한다. 재귀적인 구조를 활용할 수 있는 점화식을 만든다. -> 점화식을 만든다. 작은 문제를 해결한 방법으로 전체 문제를 해결한다. -> 문제를 해결한다. 전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식 🎈 배열 초기화 0과 1 인덱스에 각각 피보나치 수열함수를 불러올때마다... 백준피보나치수열동적계획법동적계획법 [백준] 2156: 포도주 시식 문제 문제 풀이 코드 효주만 최댓값으로 와인을 마신다라.. 오늘 나도 와인이 마시고 싶은 날이었다 후. 그래도 패턴을 찾기까지 근접했다..!!... 동적계획법백준동적계획법 [백준] 1912: 연속합 문제 문제 풀이 문제에서 주어진 조건에 따라 두가지 경우를 생각할 수 있다. i번째 해당하는 수만 더하는 경우 i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우 bottom-up방식을 이용하여 i번째 해당하는 수만 더하는 경우와 i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우 중 어떤 것이 더 큰지를 나타낸다. dp[i] = Math.max(dp[i-1] +... 동적계획법백준동적계획법 백준 1932 - 정수 삼각형 분할해서 정복하는 방법으로 해줬더니 해결할 수 있었다. else 부분이 코드의 핵심 부분이다.... 동적계획법pythonpython
[Python] 백준 1149: RGB 거리 문제를 보자마자 이코테에 나온 개미 전사 문제가 떠올랐다. 개미전사는 1차원이고 이건 2차원이라는 점이 조금 다르다. 현재 집에서 R(0)을 선택했을 경우 다음 집은 G(1), B(2)를 선택 할 수 있다. 현재 집에서 G(1)을 선택했을 경우 다음 집은 R(0), B(2)를 선택 할 수 있다. 현재 집에서 B(2)을 선택했을 경우 다음 집은 R(0), G(1)를 선택 할 수 있다. 현재 집... 백준코딩테스트 연습파이썬동적계획법동적계획법 [Python] 백준 1932번: 정수 삼각형 1부터 n번째 줄까지 정삼각형 형태의 배열이므로 j의 범위를 i+1로 해서 순회 한줄씩 내려오면서 이전값과 현재값을 더했을 때의 최대값을 선택하면서 내려오면 된다. 이전 값은 현재값을 기준으로 바로 위에서 내려올 경우와 왼쪽 위에서 내려올 경우를 생각할 수 있다. 바로 위에서 내려올 경우는 i==j 라고 할 수 있고, 이 경우 오른쪽에서 내려올 수 있는 숫자가 없으므로 right=0이 된다.... 코딩테스트 연습파이썬동적계획법동적계획법 [알고리즘][BOJ]11049_행렬 곱셈 순서 💡 생각하자 [Dynamic Programming(동적 계획법)의 개발절차] 1. 재귀 관계식(recursive property) 세우기 2. 상향식 방법(bottom-up)으로 답 구하기 재귀 관계식 A[i][j] : M(i)부터 M(j)까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 A[i][j] = minimum(A[i][k] + A[k+1][j] + d(i-1)d(k)d(j)) (i ... C동적계획법boj알고리즘C [알고리즘][BOJ]2315_가로등 끄기 1. 재귀 관계식(recursive property) 세우기 주어진 예시 상황에 대해서 생각해보자. 마징가는 5번 가로등에서 출발한다. 다음으로는 4번 또는 6번으로 갈 수 있다. 4번으로 간 경우를 생각해보자. 그렇다면 예를 들어 5->4->3->2->1->6 인 경우를 살펴보자. 3->2 : 1초 => 2⨯1 + 10⨯1 + 19⨯1 = 31 2->1 : 8초 => 2⨯8 + 19⨯8 =... C동적계획법boj알고리즘C [Algorithm] 📐프로그래머스 정수 삼각형 0. 문제 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 ... 프로그래머스동적계획법동적계획법 [알고리즘] 프로그래머스 - 2 x n 타일링 프로그래머스알고리즘DP동적계획법DP [Algorithm] 🦘외발 뛰기 0. 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗... 종만북algospot동적계획법algospot [알고리즘][BOJ]11057_오르막 수 💡 생각하자 [Dynamic Programming(동적 계획법)의 개발절차] 1. 재귀 관계식(recursive property) 세우기 2. 상향식 방법(bottom-up)으로 답 구하기 N=1일 때 0, 1, ⋯, 9까지 총 10개가 존재한다. N=2일 때 오르막 수를 AB라고 두면, A는 0부터 9까지 가능하다. (0으로 시작할 수 있다는 조건에 의해) 그러면 A=0이고 B는 0~9, ... 알고리즘동적계획법CbojC [Algorithm] 🚡백준 2579 계단오르기 <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 1.계단은 한 번에 한 계단씩 또는 두 계단씩 오를... 백준동적계획법동적계획법 [Algorithm] 🛣️백준 1520 내리막 길 0. 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능... 백준동적계획법동적계획법 [Algorithm] 🍷백준 2156 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 1.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을... 백준동적계획법동적계획법 210115 | 백준 동적계획법 1003 | C++ 전체 문제를 작은 문제로 단순화한다. -> 부분 문제를 정의한다. 재귀적인 구조를 활용할 수 있는 점화식을 만든다. -> 점화식을 만든다. 작은 문제를 해결한 방법으로 전체 문제를 해결한다. -> 문제를 해결한다. 전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식 🎈 배열 초기화 0과 1 인덱스에 각각 피보나치 수열함수를 불러올때마다... 백준피보나치수열동적계획법동적계획법 [백준] 2156: 포도주 시식 문제 문제 풀이 코드 효주만 최댓값으로 와인을 마신다라.. 오늘 나도 와인이 마시고 싶은 날이었다 후. 그래도 패턴을 찾기까지 근접했다..!!... 동적계획법백준동적계획법 [백준] 1912: 연속합 문제 문제 풀이 문제에서 주어진 조건에 따라 두가지 경우를 생각할 수 있다. i번째 해당하는 수만 더하는 경우 i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우 bottom-up방식을 이용하여 i번째 해당하는 수만 더하는 경우와 i-1번째 해당하는 수에 연이어 i번째 해당하는 수를 더하는 경우 중 어떤 것이 더 큰지를 나타낸다. dp[i] = Math.max(dp[i-1] +... 동적계획법백준동적계획법 백준 1932 - 정수 삼각형 분할해서 정복하는 방법으로 해줬더니 해결할 수 있었다. else 부분이 코드의 핵심 부분이다.... 동적계획법pythonpython