DP 백준 10844번 쉬운 계단 수 - node.js 문제 설명 계단수: 인접한 모든 자리의 차이가 1인 수 (EX. 로직 설명 N = 2일 때 가능한 계단수를 생각해보자. 해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이 정해진다. 일의 자리 수가 0일 때 1차이가 날 수 있는 자연수는 오직 1뿐이다. 반면 2부터 8까지 자연수는 자기 자신의 +1, -1인 숫자가 올 수 있다. 예시로 일의 자리 ... 백준DPDP [BOJ]11048(python) python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코드 배열을 순회하며 사탕의 갯수를 센다 현재 칸의 사탕 갯수 = 현재 칸에서 주어진 사탕 갯수 + max(세로 축으로 한칸 전 사탕 갯수, 가로 축으로 한칸 전 사탕 갯수, 가로/... DPDP 백준 14501 퇴사 python java cpp 퇴사날부터 역으로 얻을 수 있는 최대의 수익을 dp 테이블에 저장했습니다... cppbojpythonDPJavaDP [5] Longest Palindromic Substring | Leetcode Medium Given a string s, return the longest palindromic substring in s. Example 1 Example 2 제한사항 1 <= s.length <= 1000 s consist of only digits and English letters. 다른풀이... python파이썬leetcodeDPDP 백준 1309 동물원 - node.js [N = 3] 경우의 수 7가지 N-1번째 줄, 즉 1번째 줄이 비어있을 때 가능한 경우의 수 = 3가지 따라서 N-1번째 줄이 비어있을 때 가능한 경우의 수는 1*3 = 3가지이다. N-1번째 줄, 즉 1번째 줄이 비어있지 않을 때 가능한 경우의 수 = 4가지 1번째 줄이 비어있지 않다는 말은 곧 “N-1의 경우의 수 - 위의 줄이 비어있는 경우의 수”에 대해 고려한다는 말이다. N-1의 ... 백준DPDP [백준] 2579번 - 계단 오르기 <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수... 백준DPDP BOJ 14916번 거스름돈 파이썬 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총... 백준DP알고리즘DP [알고리즘/백준] 13398: 연속합 2(python) 기존 연속합과 하나를 제거한 연속합을 비교하면 된다. dp[0][i]는 제거하지 않고 구하는 연속합 dp[1][i]는 제거하고 구하는 연속합 dp[1][i] = max(dp[0][i-1], dp[1][i-1] + a[i]) 현재 숫자를 제거한 수와, 기존 숫자를 제거한 수 중에 큰 수를 고른다.... 백준DP알고리즘python연속합 21339813398 백준 11057 오르막 수 - node.js 해당 포스팅은 백준 11057번 오르막 수 풀이를 다룬다. 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하라. 수는 0으로 시작할 수 있다. 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다. 3자리 수 ___의 경우, 각 ... 백준DPDP [알고리즘/백준] 11054: 가장 긴 바이토닉 부분 수열(python) max를 이용해서 풀면 답 안나온다. 맨 앞에서 LIS를 적용 시키고, 뒤집어서 적용 시켜준다. 그리고 두개를 합쳐주면 되는데... 뒤집어서 계산 했던거는 인덱스가 반대로 들어간다. 따라서 다시 뒤집어서 더해주면 된다.... 백준DP알고리즘가장 긴 바이토닉 부분 수열python1105411054 [알고리즘/백준] 9465: 스티커(python) 1번 인덱스는 왼쪽 대각선의 수를 더해준다. 그 다음 인덱스 부터는 왼쪽 대각선의 두개의 수 중에 더 큰 수를 더해준다. dp[0][i] = max(dp[1][i-1], dp[1][i-2]) dp[1][i] = max(dp[0][i-1], dp[0][i-2])... 백준DP9465알고리즘python스티커9465 [알고리즘/백준] 1699: 제곱수의 합(python) 자기 자신보다 작은 제곱수를 이용하여 푸는 문제이다. 1부터 시작하여 자기 자신에서 제곱수를 빼고 해당하는 dp에 +1 해주면 된다. min(dp[i], dp[i - 제곱수] + 1)... 백준DP알고리즘1699python제곱수의 합1699 [알고리즘/백준] 1912: 연속합(python) 쉬운 문제인데 40분이나 고민했다... 모르겠어서 다 써봤다... -4를 예로 들면 10까지 가장 큰 합은 10이고, -4까지는 두가지 경우가 있다. 즉 자기 자신과 전의 가장 큰 합중에 max값을 구하면 된다. max(dp[i-1]+a[i], a[i])... 백준DP알고리즘python연속합19121912 [알고리즘/백준] 11057: 오르막 수(python) 마지막에 끝나는 수로 생각해서 풀었다. 0으로 끝나려면 이전의 수가 0 1로 끝나려면 이전 수가 1 이하 2로 끝나려면 이전 수가 2 이하 9로 끝나려면 이전 수가 8 이하... 경우의 수를 다 더해주면 답이 나온다. ex) dp[i][9] = dp[i-1][8] + dp[i-1][7] + dp[i-1][6] + dp[i-1][5] + dp[i-1][4] + dp[i-1][3] + dp[i-... 백준DP알고리즘오르막 수python1105711057 [알고리즘/백준] 1309: 동물원(python) 두개의 방법이 있다. 1. 규칙을 찾기 보면 dp[i] = dp[i-1] * 2 + dp[i-2] 이런 규칙이 있다. 하지만 이렇게 풀면 어려운 dp문제 풀기가 불가능하다. 2. 이전 경우 사용하기 이전 경우를 사용해야한다... 현재 내가 선택할 수 있는 경우는 1. 사자를 넣지 않는 경우 2. 왼쪽에 넣는 경우 3. 오른쪽에 넣는 경우 세가지가 있다. 사자를 넣지 않으면 이전 칸에 경우들 ... 백준DP알고리즘1309python동물원1309 [알고리즘/백준] 15988: 1, 2, 3 더하기 3(python) 백준DP알고리즘15988python1, 2, 3 더하기 31, 2, 3 더하기 3 [알고리즘/백준] 2225: 합분해(python) n=1 n=2 n=3 n=4 k=1 k=2 k=3 이 테이블을 보면 dp[k][n] = dp[k-1][n] + dp[k][n-1] 의 규칙을 보이는걸 알 수 있다.... 백준DP알고리즘python2225합분해2225 백준 17485, 진우의 달 여행 (Large) - DP 출발 지점 -> 각 지점으로의 최소 비용 값을 DP 배열에 채워나감 3가지 이동 방향: 왼쪽 아래, 아래, 오른쪽 아래 ex) (3, 5) 지점을 이전 지점으로부터 [왼쪽 아래] 방향으로 이동했을 때, 연료 최소값 1) DP 배열 정의: int[][][] dp dp[i][j][k]: 시작 지점 -> [i][j] 지점까지 이전 윗 행의 지점으로부터 k의 방향으로 이동한 최소 비용 k: 0, 1... DP알고리즘dynamic programming동적 계획법코딩 테스트백준 17485 진우의 달 여행 (Large)DP 백준 1082, 방 번호 - DP, Greedy, 문자열 1) DP 배열 정의: String[] dp dp[cost]: cost원 금액 내로 만들 수 있는 최대 숫자 문자열 출력, 최대 숫자: BigInteger(dp[m]) => dp[] 원소에 Leading-Zero 문자열이 저장될 수 있으므로, BigInteger를 이용하여 Leading-Zero 문자열을 제거 BigInteger 클래스 int, long 범위를 넘어가는 매우 큰 정수를 사용,... DPString백준 1082 방 번호알고리즘그리디greedydynamic programming동적 계획법코딩 테스트DP [백준] 14501번 💻 C++ 기반 퇴사 ✔️ DP로도 풀 수 있지만, 문제가 간단하기 때문에 그냥 DFS로 돌려서 다 확인해도 됨... 코테깊이우선탐색시뮬레이션DFS백준DP코딩테스트DFS [백준 10217 파이썬] KCM Travel (골드 1, DP) 전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이 전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때의 풀이 SOLVE 1) 풀이 요약 (전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이) 전체 문제를 "출발 노... 파이썬ps알고리즘냅색최단 경로백준DP코딩테스트DP [Java] 백준 11726번 [2xn 타일링] 자바 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 첫째 줄에 n이 주어진다. 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 동적계획법에서 이전 문제인 1, 2, 3더하기와 거의 90프로 이상의 싱크로율 문제이다. 동적계획법에 대해... JavaDP백준algorithmDP [Java] 백준 9095번 [1, 2, 3 더하기] 자바 백준 9095번 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 각 테스트 케이스마다, n을 1, 2,... JavaDP백준algorithmDP BJ4485 녹색 옷 입은 애가 젤다지? 각 칸을 이동할 때마다 비용이 필요하고, 목적지로 가는 데에 최소 비용을 구하는 문제이다. DP와 BFS로 각 칸마다 필요한 최소거리를 갱신해주는 방식과 BFS나 DFS를 활용해 연산해 주는 방식이 있다. 두가지 코드를 모두 작성해보고, 어떤 이점이 있는 지 알아볼 수 있는 문제였다. 먼저 첫번째 코드는 DFS를 활용해 연산한 방식이다. 코드는 짧고 작성하기 간단하지만, 매 한칸마다 계속 연... 백준 알고리즘BFSDPBFS [알고리즘] Java / 백준 / 1로 만들기 2 / 12852 [알고리즘] Java / 백준 / 1로 만들기 2 / 12852 문제 접근 방식 3가지 연산을 통해 나온 결과를 k로 가정할 때 N부터 k까지의 거리 최솟값을 구하기 위해 dp를 활용한다. dp에서의 점화식은 다음과 같다 또한 dp에 최소 거리가 갱신될 때 해당 수의 부모를 parent 배열에 저장하여 추후에 1부터 역탐색하여 1로 만드는 방법에 포함된 수를 얻는다. 코드... DPbaekjoonJavaDFSDFS [백준] 2096번: 내려가기 문제 풀이 파이썬 문제 링크 풀이 방식 해당 문제는 DP 문제로 점화식은 다음과 같다. maxDP1[i] = arr[i][0] + max(maxDP1[i-1], maxDP2[i-1]) maxDP2[i] = arr[i][1] + max(maxDP1[i-1], maxDP2[i-1], maxDP3[i-1]) maxDP3[i] = arr[i][2] + max(maxDP2[i-1], maxDP3[i-1]) minDP도... beakjoon백준DP골드4DP BJ1463 1로 만들기 DP 또는 재귀함수를 이용해 해결할 수 있다. 이 문제에서는 재귀함수를 이용했을 때 실행시간이 더 짧았지만, 여러 테스트 케이스를 출력한다면 DP를 활용할 때는 단순히 배열에 접근해 값만 가져오면 되기 때문에 DP가 유리하다.... 재귀함수백준 알고리즘DPDP [BOJ]1699_제곱수의 합 코드 풀이 dp값을 1부터 n까지 하나씩 갱신해가는 방법이다. 즉 작은 방법부터 해결해 나가는 전형적인 DP문제이다. i로 1부터 n까지 돌면서, j는 1부터 i-1까지의 수 중 제곱한 값이 i보다 크지 않아야 한다.... algorithmDPDP [BOJ]11052_카드구매하기 풀이 동적 프로그래밍 문제를 풀 때는 우선 기본 점화 관계를 밝힌 뒤에, 보다 효율성을 높일 수 있는 방안을 생각하도록 해야겠다. 카드 n장을 한번에 구매하는 가격이 price(n)이고, 카드 n장을 구매할 때의 최대 금액을 max_price(n)이라고 하자. 그렇다면 max_price(n)은 price(n) max_price(n - 1) + max_price(1) max_price(n - ... algorithmDPDP 이전 기사 보기
백준 10844번 쉬운 계단 수 - node.js 문제 설명 계단수: 인접한 모든 자리의 차이가 1인 수 (EX. 로직 설명 N = 2일 때 가능한 계단수를 생각해보자. 해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이 정해진다. 일의 자리 수가 0일 때 1차이가 날 수 있는 자연수는 오직 1뿐이다. 반면 2부터 8까지 자연수는 자기 자신의 +1, -1인 숫자가 올 수 있다. 예시로 일의 자리 ... 백준DPDP [BOJ]11048(python) python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코드 배열을 순회하며 사탕의 갯수를 센다 현재 칸의 사탕 갯수 = 현재 칸에서 주어진 사탕 갯수 + max(세로 축으로 한칸 전 사탕 갯수, 가로 축으로 한칸 전 사탕 갯수, 가로/... DPDP 백준 14501 퇴사 python java cpp 퇴사날부터 역으로 얻을 수 있는 최대의 수익을 dp 테이블에 저장했습니다... cppbojpythonDPJavaDP [5] Longest Palindromic Substring | Leetcode Medium Given a string s, return the longest palindromic substring in s. Example 1 Example 2 제한사항 1 <= s.length <= 1000 s consist of only digits and English letters. 다른풀이... python파이썬leetcodeDPDP 백준 1309 동물원 - node.js [N = 3] 경우의 수 7가지 N-1번째 줄, 즉 1번째 줄이 비어있을 때 가능한 경우의 수 = 3가지 따라서 N-1번째 줄이 비어있을 때 가능한 경우의 수는 1*3 = 3가지이다. N-1번째 줄, 즉 1번째 줄이 비어있지 않을 때 가능한 경우의 수 = 4가지 1번째 줄이 비어있지 않다는 말은 곧 “N-1의 경우의 수 - 위의 줄이 비어있는 경우의 수”에 대해 고려한다는 말이다. N-1의 ... 백준DPDP [백준] 2579번 - 계단 오르기 <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수... 백준DPDP BOJ 14916번 거스름돈 파이썬 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총... 백준DP알고리즘DP [알고리즘/백준] 13398: 연속합 2(python) 기존 연속합과 하나를 제거한 연속합을 비교하면 된다. dp[0][i]는 제거하지 않고 구하는 연속합 dp[1][i]는 제거하고 구하는 연속합 dp[1][i] = max(dp[0][i-1], dp[1][i-1] + a[i]) 현재 숫자를 제거한 수와, 기존 숫자를 제거한 수 중에 큰 수를 고른다.... 백준DP알고리즘python연속합 21339813398 백준 11057 오르막 수 - node.js 해당 포스팅은 백준 11057번 오르막 수 풀이를 다룬다. 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하라. 수는 0으로 시작할 수 있다. 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다. 3자리 수 ___의 경우, 각 ... 백준DPDP [알고리즘/백준] 11054: 가장 긴 바이토닉 부분 수열(python) max를 이용해서 풀면 답 안나온다. 맨 앞에서 LIS를 적용 시키고, 뒤집어서 적용 시켜준다. 그리고 두개를 합쳐주면 되는데... 뒤집어서 계산 했던거는 인덱스가 반대로 들어간다. 따라서 다시 뒤집어서 더해주면 된다.... 백준DP알고리즘가장 긴 바이토닉 부분 수열python1105411054 [알고리즘/백준] 9465: 스티커(python) 1번 인덱스는 왼쪽 대각선의 수를 더해준다. 그 다음 인덱스 부터는 왼쪽 대각선의 두개의 수 중에 더 큰 수를 더해준다. dp[0][i] = max(dp[1][i-1], dp[1][i-2]) dp[1][i] = max(dp[0][i-1], dp[0][i-2])... 백준DP9465알고리즘python스티커9465 [알고리즘/백준] 1699: 제곱수의 합(python) 자기 자신보다 작은 제곱수를 이용하여 푸는 문제이다. 1부터 시작하여 자기 자신에서 제곱수를 빼고 해당하는 dp에 +1 해주면 된다. min(dp[i], dp[i - 제곱수] + 1)... 백준DP알고리즘1699python제곱수의 합1699 [알고리즘/백준] 1912: 연속합(python) 쉬운 문제인데 40분이나 고민했다... 모르겠어서 다 써봤다... -4를 예로 들면 10까지 가장 큰 합은 10이고, -4까지는 두가지 경우가 있다. 즉 자기 자신과 전의 가장 큰 합중에 max값을 구하면 된다. max(dp[i-1]+a[i], a[i])... 백준DP알고리즘python연속합19121912 [알고리즘/백준] 11057: 오르막 수(python) 마지막에 끝나는 수로 생각해서 풀었다. 0으로 끝나려면 이전의 수가 0 1로 끝나려면 이전 수가 1 이하 2로 끝나려면 이전 수가 2 이하 9로 끝나려면 이전 수가 8 이하... 경우의 수를 다 더해주면 답이 나온다. ex) dp[i][9] = dp[i-1][8] + dp[i-1][7] + dp[i-1][6] + dp[i-1][5] + dp[i-1][4] + dp[i-1][3] + dp[i-... 백준DP알고리즘오르막 수python1105711057 [알고리즘/백준] 1309: 동물원(python) 두개의 방법이 있다. 1. 규칙을 찾기 보면 dp[i] = dp[i-1] * 2 + dp[i-2] 이런 규칙이 있다. 하지만 이렇게 풀면 어려운 dp문제 풀기가 불가능하다. 2. 이전 경우 사용하기 이전 경우를 사용해야한다... 현재 내가 선택할 수 있는 경우는 1. 사자를 넣지 않는 경우 2. 왼쪽에 넣는 경우 3. 오른쪽에 넣는 경우 세가지가 있다. 사자를 넣지 않으면 이전 칸에 경우들 ... 백준DP알고리즘1309python동물원1309 [알고리즘/백준] 15988: 1, 2, 3 더하기 3(python) 백준DP알고리즘15988python1, 2, 3 더하기 31, 2, 3 더하기 3 [알고리즘/백준] 2225: 합분해(python) n=1 n=2 n=3 n=4 k=1 k=2 k=3 이 테이블을 보면 dp[k][n] = dp[k-1][n] + dp[k][n-1] 의 규칙을 보이는걸 알 수 있다.... 백준DP알고리즘python2225합분해2225 백준 17485, 진우의 달 여행 (Large) - DP 출발 지점 -> 각 지점으로의 최소 비용 값을 DP 배열에 채워나감 3가지 이동 방향: 왼쪽 아래, 아래, 오른쪽 아래 ex) (3, 5) 지점을 이전 지점으로부터 [왼쪽 아래] 방향으로 이동했을 때, 연료 최소값 1) DP 배열 정의: int[][][] dp dp[i][j][k]: 시작 지점 -> [i][j] 지점까지 이전 윗 행의 지점으로부터 k의 방향으로 이동한 최소 비용 k: 0, 1... DP알고리즘dynamic programming동적 계획법코딩 테스트백준 17485 진우의 달 여행 (Large)DP 백준 1082, 방 번호 - DP, Greedy, 문자열 1) DP 배열 정의: String[] dp dp[cost]: cost원 금액 내로 만들 수 있는 최대 숫자 문자열 출력, 최대 숫자: BigInteger(dp[m]) => dp[] 원소에 Leading-Zero 문자열이 저장될 수 있으므로, BigInteger를 이용하여 Leading-Zero 문자열을 제거 BigInteger 클래스 int, long 범위를 넘어가는 매우 큰 정수를 사용,... DPString백준 1082 방 번호알고리즘그리디greedydynamic programming동적 계획법코딩 테스트DP [백준] 14501번 💻 C++ 기반 퇴사 ✔️ DP로도 풀 수 있지만, 문제가 간단하기 때문에 그냥 DFS로 돌려서 다 확인해도 됨... 코테깊이우선탐색시뮬레이션DFS백준DP코딩테스트DFS [백준 10217 파이썬] KCM Travel (골드 1, DP) 전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이 전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때의 풀이 SOLVE 1) 풀이 요약 (전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이) 전체 문제를 "출발 노... 파이썬ps알고리즘냅색최단 경로백준DP코딩테스트DP [Java] 백준 11726번 [2xn 타일링] 자바 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 첫째 줄에 n이 주어진다. 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 동적계획법에서 이전 문제인 1, 2, 3더하기와 거의 90프로 이상의 싱크로율 문제이다. 동적계획법에 대해... JavaDP백준algorithmDP [Java] 백준 9095번 [1, 2, 3 더하기] 자바 백준 9095번 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 각 테스트 케이스마다, n을 1, 2,... JavaDP백준algorithmDP BJ4485 녹색 옷 입은 애가 젤다지? 각 칸을 이동할 때마다 비용이 필요하고, 목적지로 가는 데에 최소 비용을 구하는 문제이다. DP와 BFS로 각 칸마다 필요한 최소거리를 갱신해주는 방식과 BFS나 DFS를 활용해 연산해 주는 방식이 있다. 두가지 코드를 모두 작성해보고, 어떤 이점이 있는 지 알아볼 수 있는 문제였다. 먼저 첫번째 코드는 DFS를 활용해 연산한 방식이다. 코드는 짧고 작성하기 간단하지만, 매 한칸마다 계속 연... 백준 알고리즘BFSDPBFS [알고리즘] Java / 백준 / 1로 만들기 2 / 12852 [알고리즘] Java / 백준 / 1로 만들기 2 / 12852 문제 접근 방식 3가지 연산을 통해 나온 결과를 k로 가정할 때 N부터 k까지의 거리 최솟값을 구하기 위해 dp를 활용한다. dp에서의 점화식은 다음과 같다 또한 dp에 최소 거리가 갱신될 때 해당 수의 부모를 parent 배열에 저장하여 추후에 1부터 역탐색하여 1로 만드는 방법에 포함된 수를 얻는다. 코드... DPbaekjoonJavaDFSDFS [백준] 2096번: 내려가기 문제 풀이 파이썬 문제 링크 풀이 방식 해당 문제는 DP 문제로 점화식은 다음과 같다. maxDP1[i] = arr[i][0] + max(maxDP1[i-1], maxDP2[i-1]) maxDP2[i] = arr[i][1] + max(maxDP1[i-1], maxDP2[i-1], maxDP3[i-1]) maxDP3[i] = arr[i][2] + max(maxDP2[i-1], maxDP3[i-1]) minDP도... beakjoon백준DP골드4DP BJ1463 1로 만들기 DP 또는 재귀함수를 이용해 해결할 수 있다. 이 문제에서는 재귀함수를 이용했을 때 실행시간이 더 짧았지만, 여러 테스트 케이스를 출력한다면 DP를 활용할 때는 단순히 배열에 접근해 값만 가져오면 되기 때문에 DP가 유리하다.... 재귀함수백준 알고리즘DPDP [BOJ]1699_제곱수의 합 코드 풀이 dp값을 1부터 n까지 하나씩 갱신해가는 방법이다. 즉 작은 방법부터 해결해 나가는 전형적인 DP문제이다. i로 1부터 n까지 돌면서, j는 1부터 i-1까지의 수 중 제곱한 값이 i보다 크지 않아야 한다.... algorithmDPDP [BOJ]11052_카드구매하기 풀이 동적 프로그래밍 문제를 풀 때는 우선 기본 점화 관계를 밝힌 뒤에, 보다 효율성을 높일 수 있는 방안을 생각하도록 해야겠다. 카드 n장을 한번에 구매하는 가격이 price(n)이고, 카드 n장을 구매할 때의 최대 금액을 max_price(n)이라고 하자. 그렇다면 max_price(n)은 price(n) max_price(n - 1) + max_price(1) max_price(n - ... algorithmDPDP 이전 기사 보기