다이나믹프로그래밍 BOJ_2206_G4_벽 부수고 이동하기 문제 링크: 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 ... boj알고리즘다이나믹프로그래밍메모이제이션다익스트라boj [백준] 2748번 피보나치2 백준DP다이나믹프로그래밍DP 백준 - 피보나치 함수 [1003] 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴... Java알고리즘다이나믹프로그래밍Java [백준/파이썬] 1149 RGB거리 알고리즘 분류 다이나믹 프로그래밍 문제풀이 처음에 0번 집에서 최소값을 가지는 색깔을 선택해서 풀었는데 다음과 같은 반례 때문에 실패했다. ex) 999 1 999 -> 101이 나와야함 1번 집에서 R를 선택했을 경우 0번 집은 G,B중에서 최소값을 선택했을 것이다. 그 값과 원래 값을 계속해서 합산해나간다. 1번 집에서 G를 선택했을 경우 0번 집은 R,B중에서 최소값 선택... ex) ... 알고리즘다이나믹프로그래밍다이나믹프로그래밍 백준 - 파도반 수열 [9461] 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, ... Java알고리즘다이나믹프로그래밍Java [다이나믹 프로그래밍]N으로 표현-파이썬 다이나믹 프로그래밍 📌최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 📌작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 다이나믹 프로그래밍을 생각해보자 문제 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어... algorithm다이나믹프로그래밍algorithm 백준 11052 / 카드 구매하기 설명 조건 : 카드 N개를 구매해야 한다. 카드팩은 총 N가지 종류가 존재하고 i번째 카드팩은 i개의 카드를 담고 있으며, 가격은 P[i]원 이다. 카드 N개를 구매하는 비용의 최대값을 구하는 문제 여기서 카드 N개를 구매하는 비용의 최대값을 D[N]이라고 하자. 카드팩 하나씩을 구매하면서 마지막 카드팩을 샀을 때 카드 N개를 딱 맞게 사야하는 조건을 충족해야 한다. 따라서 마지막 구매 카드... 백준다이나믹프로그래밍다이나믹프로그래밍 [PART2] 8-4(DP): 효율적인 화폐 구성 ❗ 난이도🖤🖤🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB 📌2021/02/03 작성 코드 💭 아이디어 솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다. 혼자 정리해 본 아이디어는 이렇다. 🤓 문제 해설 이 문제는 그리디에서 다루었던 거스름돈 문제와 거의 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다. 그렇기 때문에 그... 이코테다이나믹프로그래밍다이나믹프로그래밍 [프로그래머스/파이썬] 다이나믹프로그래밍 등굣길 알고리즘 분류 다이나믹프로그래밍 문제풀이 bfs두번 돌리다가 시간초과로 실패했다. 0으로 초기화한 가로, 세로를 한 줄씩 추가해주고 출발 지점인 집의 위치의 값은 1로 해준다. 각각의 좌표에서 왼쪽과 위 값을 더해나가면 된다. graph=[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 1, 2, 4]] 소스코드... 알고리즘다이나믹프로그래밍다이나믹프로그래밍 백준 :: 동전1 <2293번> 출처: n = 동전의 개수, k = 목표 동전 가치 합 (단위: 원) 각 동전 가치의 경우 하나씩 돌려가면서 최종 합 k를 충족하는 경우의 수 갱신하기 dp = [ index = 합, value = 주어진 동전들로 합을 만들 수 있는 경우의 수 ] ex. dp[4] : 합이 4가 되는 경우의 수 코드 中 예시) i == 5 & j == 6 인 경우, j-i (1) >= 0 조건을 통과하므로 ... 백준2293DP다이나믹프로그래밍python파이썬알고리즘동전12293 [PART2] 8-3(DP): 바닥 공사 ❗ 난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 20분 | 제한시간 1초 | 메모리제한 128MB 📌2021/02/01 작성 코드 💭 아이디어 솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다. 혼자 정리해 본 아이디어는 이렇다. 🔴 백준 11727 문제와 유사하다 🤓 문제 해설 결과값이 굉장히 커질 수 있기 때문에 값을 계산할 때마다 796796으로 나눈 나머지만 취하도록 한다. 왼쪽부터... 이코테다이나믹프로그래밍다이나믹프로그래밍 [백준 2156] 포도주 시식 ❗ 다이나믹프로그래밍다이나믹프로그래밍 [BOJ] 2839 - 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로... 다이나믹프로그래밍공부노트코딩공부bojDPDP 백준 - 피보나치 수 5 [10870] 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 첫째 줄에 n이 주어진다. n은 20... 알고리즘Java다이나믹프로그래밍재귀Java
BOJ_2206_G4_벽 부수고 이동하기 문제 링크: 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 ... boj알고리즘다이나믹프로그래밍메모이제이션다익스트라boj [백준] 2748번 피보나치2 백준DP다이나믹프로그래밍DP 백준 - 피보나치 함수 [1003] 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴... Java알고리즘다이나믹프로그래밍Java [백준/파이썬] 1149 RGB거리 알고리즘 분류 다이나믹 프로그래밍 문제풀이 처음에 0번 집에서 최소값을 가지는 색깔을 선택해서 풀었는데 다음과 같은 반례 때문에 실패했다. ex) 999 1 999 -> 101이 나와야함 1번 집에서 R를 선택했을 경우 0번 집은 G,B중에서 최소값을 선택했을 것이다. 그 값과 원래 값을 계속해서 합산해나간다. 1번 집에서 G를 선택했을 경우 0번 집은 R,B중에서 최소값 선택... ex) ... 알고리즘다이나믹프로그래밍다이나믹프로그래밍 백준 - 파도반 수열 [9461] 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, ... Java알고리즘다이나믹프로그래밍Java [다이나믹 프로그래밍]N으로 표현-파이썬 다이나믹 프로그래밍 📌최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 📌작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 다이나믹 프로그래밍을 생각해보자 문제 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어... algorithm다이나믹프로그래밍algorithm 백준 11052 / 카드 구매하기 설명 조건 : 카드 N개를 구매해야 한다. 카드팩은 총 N가지 종류가 존재하고 i번째 카드팩은 i개의 카드를 담고 있으며, 가격은 P[i]원 이다. 카드 N개를 구매하는 비용의 최대값을 구하는 문제 여기서 카드 N개를 구매하는 비용의 최대값을 D[N]이라고 하자. 카드팩 하나씩을 구매하면서 마지막 카드팩을 샀을 때 카드 N개를 딱 맞게 사야하는 조건을 충족해야 한다. 따라서 마지막 구매 카드... 백준다이나믹프로그래밍다이나믹프로그래밍 [PART2] 8-4(DP): 효율적인 화폐 구성 ❗ 난이도🖤🖤🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB 📌2021/02/03 작성 코드 💭 아이디어 솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다. 혼자 정리해 본 아이디어는 이렇다. 🤓 문제 해설 이 문제는 그리디에서 다루었던 거스름돈 문제와 거의 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다. 그렇기 때문에 그... 이코테다이나믹프로그래밍다이나믹프로그래밍 [프로그래머스/파이썬] 다이나믹프로그래밍 등굣길 알고리즘 분류 다이나믹프로그래밍 문제풀이 bfs두번 돌리다가 시간초과로 실패했다. 0으로 초기화한 가로, 세로를 한 줄씩 추가해주고 출발 지점인 집의 위치의 값은 1로 해준다. 각각의 좌표에서 왼쪽과 위 값을 더해나가면 된다. graph=[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 1, 2, 4]] 소스코드... 알고리즘다이나믹프로그래밍다이나믹프로그래밍 백준 :: 동전1 <2293번> 출처: n = 동전의 개수, k = 목표 동전 가치 합 (단위: 원) 각 동전 가치의 경우 하나씩 돌려가면서 최종 합 k를 충족하는 경우의 수 갱신하기 dp = [ index = 합, value = 주어진 동전들로 합을 만들 수 있는 경우의 수 ] ex. dp[4] : 합이 4가 되는 경우의 수 코드 中 예시) i == 5 & j == 6 인 경우, j-i (1) >= 0 조건을 통과하므로 ... 백준2293DP다이나믹프로그래밍python파이썬알고리즘동전12293 [PART2] 8-3(DP): 바닥 공사 ❗ 난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 20분 | 제한시간 1초 | 메모리제한 128MB 📌2021/02/01 작성 코드 💭 아이디어 솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다. 혼자 정리해 본 아이디어는 이렇다. 🔴 백준 11727 문제와 유사하다 🤓 문제 해설 결과값이 굉장히 커질 수 있기 때문에 값을 계산할 때마다 796796으로 나눈 나머지만 취하도록 한다. 왼쪽부터... 이코테다이나믹프로그래밍다이나믹프로그래밍 [백준 2156] 포도주 시식 ❗ 다이나믹프로그래밍다이나믹프로그래밍 [BOJ] 2839 - 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로... 다이나믹프로그래밍공부노트코딩공부bojDPDP 백준 - 피보나치 수 5 [10870] 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 첫째 줄에 n이 주어진다. n은 20... 알고리즘Java다이나믹프로그래밍재귀Java