DP 백준 / 2491 / 수열 Question Silver 4 Logic 기본 구조 : dp 1. dp 리스트 안에 네 가지 수를 둔다. a.연속증가하는 현재 값 b.연속증가하는 최대값 c.연속감소하는 현재 값 d.연속감소하는 최대값 한 수씩 앞 수와 비교한다(첫 숫자의 경우 같은 수를 둔다.) 앞 수보다 크다면 : a 증가, b 값 최신화, c 초기화(1) 같다면 : a,c 증가, b,d값 최신화 작다면 : a 초기화,... python백준DPDP 백준 1106, 호텔 - DP 적어도 c명 영업 => c명, c+1명, ..., c+100명 (입력: 1개 도시에서 x원으로 영업하는 최대 고객 수 = 100명) => c명, c+1명, ..., c+100명 늘리는 최소 금액에서 최소값 적어도 i명(i <= 입력 c)을 늘리기 위한 최소 금액 => i명, i+1명, ..., c+100명 늘리는 최소 금액에서 최소값 dp[i]: 고객을 i명 만큼 늘릴 때, 최소 비용 출력,... DP알고리즘knapsack problem0-1 Knapsack Problemdynamic programming동적 계획법백준 1106 호텔코딩 테스트0-1 Knapsack Problem 프로그래머스 GPS 먼저 인접리스트 방식으로 그래프를 구현해줬습니다 문제에서 노드는 그 자리에 머무를 수도 있기 때문에 리스트에 자기 자신의 노드도 포함시켜주는 것이 뽀인트입니다. dp테이블을 만들고 무한으로 초기화 시켜줬습니다 dp에는 오류회수가 저장 되는데 처음 시작점은 0으로 초기화 해줍니다 dp테이블을 돌면서 값을 갱신해주는데 현재 값이 INF라면 넘깁니다 무한이 아니라면 현재 노드와 연결된 곳들을 다 ... programmerscppDP카카오 기출DP 프로그래머스 등굣길 cpp python 집의 위치는 (1,1)로 고정되있고 학교의 위치는 (m,n)으로 고정되있을 때 집에서 학교까지 가는 최단경로의 수를 구하는 문제입니다. 개인적으로 n,m위치가 바뀐게 좀 불편했습니다 집에서 출발해서 오른쪽과 아래쪽으로만 움직이면 항상 최단경로이고 물웅덩이 예외처리를 해주면 문제는 어렵지 않게 풀 수 있습니다 코드를 보시면 물웅덩이는 -1로 표시해서 예외처리를 해주고 (0,... pythonprogrammerscppDPDP 백준 14722, 우유 도시 - DP 우유 순서: 딸기(0) -> 초코(1) -> 바나나(2) 최근에 마신 우유 종류에 따라 => "최근 마신 우유 종류를 구분"하여, DP 배열을 채움 1) DP 배열 정의: int[][][] dp dp[i][j][k]: [i][j] 지점까지 가장 최근에 k 우유를 마셨을 때, 마신 최대 우유 개수 (우유 종류 k: 딸기 0, 초코 1, 바나나 2) 출력, 최대 우유 개수 = dp[n-1][n-... DP알고리즘dynamic programming동적 계획법백준 14722 우유 도시코딩 테스트DP 백준 1520, 내리막 길 - DFS, DP, 메모이제이션 dp[y][x]: 시작 지점 [0][0] -> [y][x] 지점으로 내리막 길로 가는 경로 개수 dp[y][x] = 0 이면, 해당 [y][x]로 내리막 길로 갈 수 없음 출력 값 h = dp[m-1][n-1] DFS + DP 현재 지점 [y][x]가 끝 지점이면, DFS 탐색 종료 dp[y][x]: [y][x] 지점 -> 끝 지점으로 내리막 길로 가는 경로 개수 현재 지점 [y][x]에 대... DPDFS알고리즘그래프 탐색depth first search메모이제이션dynamic programming동적 계획법백준 1520 내리막 길깊이 우선 탐색memoization코딩 테스트DFS boj9251 LCS 링크 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째... 백준골드DPDP [백준/python/2579]계단오르기 문제 링크: 처음 dp알고리즘을 배울 때 접했던 유형이 계단오르기였다. dp문제의 기본 문제라고 생각한다. 기본문제와 차이점은 한칸씩 밟는 것은 세 번 연속으로 할 수 없다는 점이다. 처음에는 stair와 dp배열의 크기를 n으로 뒀는데 런타임 에러가 떴다. 그래서 배열의 크기를 조정해서 해결했다. 마지막 계단을 기준으로 생각했을 때, 직전의 계단(i-1)을 밟았다면 그 이전에는 직전계단의 ... python백준DP알고리즘DP [백준] 2780번: 비밀번호 문제 풀이 파이썬 그 기계의 모양은 다음과 같다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다. 석원이의 힌트 종이는 다음과 같다. 비밀번호의 길이는 N이다. 비밀번호는 위 그림에 나온 번호들을 눌러서 만든다. 15 라는 비밀번호는 불가능하다. ) 하지만 1236이라는 비밀번호는 가능하다.) 첫 ... 알고리즘실버1beakjoon파이썬DP백준DP [알고리즘/백준] 2579번 : 계단 오르기(python) python2579알고리즘계단 오르기DP백준2579 [백준-11048] 이동하기 dp[i][j]에는 (i,j)미로방에 가지고들어갈 사탕의 최대 가수이다. 이는 dp[i-1][j]+maze[i-1][j-1] 혹은 dp[i][j-1]+maze[i-1][j-1] 혹은 dp[i-1][j-1]+maze[i-1][j-1] 중 가장 큰 값이다. maze[i-1][j-1]인 이유는 dp의 크기가 n+1,m+1 이기 때문이다.... 파이썬백준DPDP 백준 7576번 - 앱 배낭 문제 알고리즘으로 풀이할 수 있는 문제다. 앱이 차지하는 메모리 용량이 Ai 소요되는 비용이 C_{i} Ci 라고 쳤을 때 확보해야하는 메모리 용량 M 이상을 확보 했을 때 최소 비용을 구하는 문제다. 그러므로 배낭 문제에 대응 해보았을 때 소요되는 비용이 배낭의 사이즈고, 해당 배낭 사이즈로 가져갈 수 있는 가치의 목록들이 각각의 앱의 메모리 용량이라고 생각하면 된다. 즉 dp배열과 ... ps냅색알고리즘DP백준DP [C언어] 백준 2156 : 포도주 시식 생각의 흐름 이거 했었다. 계단오르기 확장이다. 조건은 쉽다. 3잔연속만 안마시면 된다. 4잔을 기준잡고, 점화식을 찾아보자. a,b,c,d가 있다. OOXO, OXOO, XOOX, OXOX, XOXO 이렇게 있다. 2번연속으로 안마시는건 최대값이 절대 안나오기때문에 고려안했다. 근데 위에서도 OOXO랑 XOXO를 비교해보면 OOXO가 항상 이기기에, XOXO를 버리고 OXOX도 같은 논리로... C백준DPC [백준-13398] 연속합 2 수행시간: 208ms 생각해보다가 풀리지 않아 검색을 통해서 풀었다. dp[0][i]는 특정 원소를 제거하지 않은 경우 dp[1][i]는 특정 원소를 제거한 경우 어떠한 원소도 삭제하지않는 경우는 (이전까지의 연속합+i번째원소)와 (i번째 원소)중 큰값을 대입 어떠한 원소를 삭제한 경우는 2가지로 나누어 생각한다. 1. i번째 원소를 삭제한 경우 2. i 이전 원소를 삭제한 경우 1번은 dp... 파이썬백준DPDP [백준/python/6359]만취한 상범 문제: 요즘 백준 알고리즘의 dp문제집을 풀고있다. 이 문제는 내용이 재밌었다. 만든 사람 천재인 것 같다. 이번 문제는 공책에 n=1일때부터 n=4일때까지 시뮬레이션을 해본 후 거의 구현으로 풀었다. 내 코드로도 통과되지만 너무 구현식으로 푼 것 같아서 다 풀고나서 다른 사람의 풀이를 참고해보았다. 이렇게 간단하게 풀다니. 도망나간 사람의 숫자에 초점을 맞춘 코드이다.... python백준DP알고리즘DP [알고리즘/백준] 11053번 : 가장 긴 증가하는 부분 수열(python) 이건 set형으로 중복 없애고 풀어보기도 하고 다 해봤는데 계속 틀렸다고 나와서 답을 봤다... LIS를 사용해야 한다고 한다. 새로 하나 배웠다.... python가장 긴 증가하는 부분 수열알고리즘LIS11053DP백준11053 [알고리즘/백준] 1149번 : RGB거리(python) 풀이 방법이 도저히 안떠올라서 다른 사람들 풀이를 참고했다. 위에서 하나씩 계산해서 내려가면 된다...... 1149python알고리즘DP백준rgb거리1149 [백준/python/1463]1로 만들기 문제: 이 문제는 두 번째로 풀어보는 문제다. 처음 풀 때는 dp의 개념을 제대로 이해하지 못해서 어려웠는데, 두 번째는 훨씬 수월했다. 문제와 입력, 출력은 위에 링크를 통해 확인할 수 있다. 이 문제의 연산하는 방법은 총 세가지이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 그리고 문제에서 원하는 답은 1을 만드... python백준DP알고리즘DP [백준 C++] 2775 부녀회장이 될테야 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조... memoization2775baekjoonCDP부녀회장이 될테야2775 백준 12865 평범한 배낭 (Java) 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아... 백준골드 5DPDP [백준/python/1495]기타리스트 문제링크 : 이 문제는 이중배열을 사용해서 풀었다. 맞왜틀!!만 외쳤던 문제다. 알고보니 쉼표를 괄호로 적었던 것이였다,,,, 노래의 순서와 음 하나씩을 배열로 주었다. 배열에 1이 표시되어 있으면 해당음은 가능하다는 뜻이다. 범위를 잘 측정하여 연주가능한 음에 1을 표시해주고 마지막에 마지막곡의 배열에서 1을 가지고 있는 음을 찾아준다. 이 때, 최댓값을 출력하기위해 가장 높은음부터 내려왔... python백준DP알고리즘DP boj2293 동전1 링크 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는... 백준골드DPDP boj23318 행렬분할 링크 문제 n × m 크기의 행렬이 있다. 이 행렬을 가로로 a번, 세로로 b번 잘라 (a + 1) × (b + 1) 개의 부분으로 분할하려고 한다. 이 때, 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함되지 않은 부분은 존재할 수 없다. 위 그림 1과 같은 6 × 7 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다. 분할의 '점수'... 백준골드DP브루트포스DP [C언어] 백준 1904 : 01타일 생각의 흐름 문제를 보고 이게뭔가 싶었다. 일단 무작정 1부터 6까지 써봤다. 5까지 했을때 설마 피보나치인가 싶었는데 6에서 13이 나온 걸 보고 아 피보나치구나 싶었다. 피보나치를 동적 계획법 활용해서 푸는건 해봤기때문에,출력조건에 15746을 나눈 나머지를 출력한다. 이것만 생각하면 된다. 내가 푼 코드 15746를 위에다 한 이유는 처음에 printf에 해줬다가 오버플로우가 났다. n... C백준DPC [C언어] 백준 1003 : 피보나치 함수 생각의 흐름 이번에는 동적 계획법이라는 파트이다. 당연히 처음 들어보기에 바로 구글링으로 어떤건지 찾아보았다. 여기에서 도움을 받았다. 간단하게 말하자면, 기본적으로 피보나치로 예를 드는데, 중복되는 계산을 피하자! 이거다. 그걸 메모이제이션이라고 하는데, 크게 두가지 방법을 사용하나보다. 이렇게 기억하면서 내려가고, 올라간다. 이 방법을 익혀놓자. 먼저, 위 식을 생각안하고, 내 방식대로 ... C백준DPC [C언어] 백준 9184 : 신나는 함수 실행 생각의 흐름 문제 이해가 안돼서 그냥 무작정 w(1, 1, 1), w(2, 2, 2)를 써봤다. 이 값을 문제에 나와있는 함수에 대입하니 식이 엄청 많이 나왔다. 동적 계획법에 맞게 중복되는 값을 피보나치처럼 지우면 되겠구나 싶었다. 일단 예외처리해야 할 케이스를 정했다. a b c 셋중 하나라도 0이거나 0보다 작을경우 a b c 셋중 하나라도 20보다 클 경우 a < b < c 일 경우 ... C백준DPC [백준-15989] 1,2,3 더하기 4 수행시간: 184ms(pypy3) dp에는 정수i를 1,2,3의 합으로 나타내는 구성을 [1이 가장 큰 구성, 2가 가장 큰 구성,3이 가장 큰 구성] 로 저장한다. dp[i]의 1이 가장 큰 구성은 dp[i-3]의 1이 가장 큰 구성과 같다. dp[i]의 2가 가장 큰 구성은 dp[i-2]의 1이 가장 큰 구성과 2가 가장 큰 구성의 합 과 같다. dp[i]의 3가 가장 큰 구성은 dp[i... 파이썬백준DPDP [백준-11060] 점프 점프 수행시간: 72ms 나는 맨 마지막부터 처음으로 돌아오면서 최소 점프 횟수를 구하는 방식으로 문제를 풀었다. 예를 들어 입력이 n=10 maze=[1 2 0 1 3 2 1 5 4 2] 이렇게 주어지면 dp[9]는 9번방부터 9번방까지 최소 점프 횟수이므로 0이다. dp[8]은 8번방부터 9번방까지 최소 점프 횟수이다.maze[8]은 4이므로 9,10,11,12번 방까지 점프할수있고 점프할수있... 파이썬백준DPDP [C언어] 백준 11053 : 가장 긴 증가하는 부분 수열 생각의 흐름 LIS가 뭔지 몰라서 검색했다. LIS는 코딩테스트에서 자주 나오는 유형이고, 푸는 방법은 크게 두가지가 있다. DP와 이분 탐색이다. 먼저 DP는 n값이 커질수록 시간이 굉장히 오래 걸리는 방법이고, 이분탐색은 시간절약이 잘 되어 결국에는 이분 탐색을 사용한다고 설명이 되어있다. 이분탐색도 검색해보았지만, 아직 너무 어려워 DP로 풀기로 했다. 틀렸던 풀이 수정한 풀이 틀렸던 ... C백준수정필요DPC 이전 기사 보기
백준 / 2491 / 수열 Question Silver 4 Logic 기본 구조 : dp 1. dp 리스트 안에 네 가지 수를 둔다. a.연속증가하는 현재 값 b.연속증가하는 최대값 c.연속감소하는 현재 값 d.연속감소하는 최대값 한 수씩 앞 수와 비교한다(첫 숫자의 경우 같은 수를 둔다.) 앞 수보다 크다면 : a 증가, b 값 최신화, c 초기화(1) 같다면 : a,c 증가, b,d값 최신화 작다면 : a 초기화,... python백준DPDP 백준 1106, 호텔 - DP 적어도 c명 영업 => c명, c+1명, ..., c+100명 (입력: 1개 도시에서 x원으로 영업하는 최대 고객 수 = 100명) => c명, c+1명, ..., c+100명 늘리는 최소 금액에서 최소값 적어도 i명(i <= 입력 c)을 늘리기 위한 최소 금액 => i명, i+1명, ..., c+100명 늘리는 최소 금액에서 최소값 dp[i]: 고객을 i명 만큼 늘릴 때, 최소 비용 출력,... DP알고리즘knapsack problem0-1 Knapsack Problemdynamic programming동적 계획법백준 1106 호텔코딩 테스트0-1 Knapsack Problem 프로그래머스 GPS 먼저 인접리스트 방식으로 그래프를 구현해줬습니다 문제에서 노드는 그 자리에 머무를 수도 있기 때문에 리스트에 자기 자신의 노드도 포함시켜주는 것이 뽀인트입니다. dp테이블을 만들고 무한으로 초기화 시켜줬습니다 dp에는 오류회수가 저장 되는데 처음 시작점은 0으로 초기화 해줍니다 dp테이블을 돌면서 값을 갱신해주는데 현재 값이 INF라면 넘깁니다 무한이 아니라면 현재 노드와 연결된 곳들을 다 ... programmerscppDP카카오 기출DP 프로그래머스 등굣길 cpp python 집의 위치는 (1,1)로 고정되있고 학교의 위치는 (m,n)으로 고정되있을 때 집에서 학교까지 가는 최단경로의 수를 구하는 문제입니다. 개인적으로 n,m위치가 바뀐게 좀 불편했습니다 집에서 출발해서 오른쪽과 아래쪽으로만 움직이면 항상 최단경로이고 물웅덩이 예외처리를 해주면 문제는 어렵지 않게 풀 수 있습니다 코드를 보시면 물웅덩이는 -1로 표시해서 예외처리를 해주고 (0,... pythonprogrammerscppDPDP 백준 14722, 우유 도시 - DP 우유 순서: 딸기(0) -> 초코(1) -> 바나나(2) 최근에 마신 우유 종류에 따라 => "최근 마신 우유 종류를 구분"하여, DP 배열을 채움 1) DP 배열 정의: int[][][] dp dp[i][j][k]: [i][j] 지점까지 가장 최근에 k 우유를 마셨을 때, 마신 최대 우유 개수 (우유 종류 k: 딸기 0, 초코 1, 바나나 2) 출력, 최대 우유 개수 = dp[n-1][n-... DP알고리즘dynamic programming동적 계획법백준 14722 우유 도시코딩 테스트DP 백준 1520, 내리막 길 - DFS, DP, 메모이제이션 dp[y][x]: 시작 지점 [0][0] -> [y][x] 지점으로 내리막 길로 가는 경로 개수 dp[y][x] = 0 이면, 해당 [y][x]로 내리막 길로 갈 수 없음 출력 값 h = dp[m-1][n-1] DFS + DP 현재 지점 [y][x]가 끝 지점이면, DFS 탐색 종료 dp[y][x]: [y][x] 지점 -> 끝 지점으로 내리막 길로 가는 경로 개수 현재 지점 [y][x]에 대... DPDFS알고리즘그래프 탐색depth first search메모이제이션dynamic programming동적 계획법백준 1520 내리막 길깊이 우선 탐색memoization코딩 테스트DFS boj9251 LCS 링크 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째... 백준골드DPDP [백준/python/2579]계단오르기 문제 링크: 처음 dp알고리즘을 배울 때 접했던 유형이 계단오르기였다. dp문제의 기본 문제라고 생각한다. 기본문제와 차이점은 한칸씩 밟는 것은 세 번 연속으로 할 수 없다는 점이다. 처음에는 stair와 dp배열의 크기를 n으로 뒀는데 런타임 에러가 떴다. 그래서 배열의 크기를 조정해서 해결했다. 마지막 계단을 기준으로 생각했을 때, 직전의 계단(i-1)을 밟았다면 그 이전에는 직전계단의 ... python백준DP알고리즘DP [백준] 2780번: 비밀번호 문제 풀이 파이썬 그 기계의 모양은 다음과 같다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다. 석원이의 힌트 종이는 다음과 같다. 비밀번호의 길이는 N이다. 비밀번호는 위 그림에 나온 번호들을 눌러서 만든다. 15 라는 비밀번호는 불가능하다. ) 하지만 1236이라는 비밀번호는 가능하다.) 첫 ... 알고리즘실버1beakjoon파이썬DP백준DP [알고리즘/백준] 2579번 : 계단 오르기(python) python2579알고리즘계단 오르기DP백준2579 [백준-11048] 이동하기 dp[i][j]에는 (i,j)미로방에 가지고들어갈 사탕의 최대 가수이다. 이는 dp[i-1][j]+maze[i-1][j-1] 혹은 dp[i][j-1]+maze[i-1][j-1] 혹은 dp[i-1][j-1]+maze[i-1][j-1] 중 가장 큰 값이다. maze[i-1][j-1]인 이유는 dp의 크기가 n+1,m+1 이기 때문이다.... 파이썬백준DPDP 백준 7576번 - 앱 배낭 문제 알고리즘으로 풀이할 수 있는 문제다. 앱이 차지하는 메모리 용량이 Ai 소요되는 비용이 C_{i} Ci 라고 쳤을 때 확보해야하는 메모리 용량 M 이상을 확보 했을 때 최소 비용을 구하는 문제다. 그러므로 배낭 문제에 대응 해보았을 때 소요되는 비용이 배낭의 사이즈고, 해당 배낭 사이즈로 가져갈 수 있는 가치의 목록들이 각각의 앱의 메모리 용량이라고 생각하면 된다. 즉 dp배열과 ... ps냅색알고리즘DP백준DP [C언어] 백준 2156 : 포도주 시식 생각의 흐름 이거 했었다. 계단오르기 확장이다. 조건은 쉽다. 3잔연속만 안마시면 된다. 4잔을 기준잡고, 점화식을 찾아보자. a,b,c,d가 있다. OOXO, OXOO, XOOX, OXOX, XOXO 이렇게 있다. 2번연속으로 안마시는건 최대값이 절대 안나오기때문에 고려안했다. 근데 위에서도 OOXO랑 XOXO를 비교해보면 OOXO가 항상 이기기에, XOXO를 버리고 OXOX도 같은 논리로... C백준DPC [백준-13398] 연속합 2 수행시간: 208ms 생각해보다가 풀리지 않아 검색을 통해서 풀었다. dp[0][i]는 특정 원소를 제거하지 않은 경우 dp[1][i]는 특정 원소를 제거한 경우 어떠한 원소도 삭제하지않는 경우는 (이전까지의 연속합+i번째원소)와 (i번째 원소)중 큰값을 대입 어떠한 원소를 삭제한 경우는 2가지로 나누어 생각한다. 1. i번째 원소를 삭제한 경우 2. i 이전 원소를 삭제한 경우 1번은 dp... 파이썬백준DPDP [백준/python/6359]만취한 상범 문제: 요즘 백준 알고리즘의 dp문제집을 풀고있다. 이 문제는 내용이 재밌었다. 만든 사람 천재인 것 같다. 이번 문제는 공책에 n=1일때부터 n=4일때까지 시뮬레이션을 해본 후 거의 구현으로 풀었다. 내 코드로도 통과되지만 너무 구현식으로 푼 것 같아서 다 풀고나서 다른 사람의 풀이를 참고해보았다. 이렇게 간단하게 풀다니. 도망나간 사람의 숫자에 초점을 맞춘 코드이다.... python백준DP알고리즘DP [알고리즘/백준] 11053번 : 가장 긴 증가하는 부분 수열(python) 이건 set형으로 중복 없애고 풀어보기도 하고 다 해봤는데 계속 틀렸다고 나와서 답을 봤다... LIS를 사용해야 한다고 한다. 새로 하나 배웠다.... python가장 긴 증가하는 부분 수열알고리즘LIS11053DP백준11053 [알고리즘/백준] 1149번 : RGB거리(python) 풀이 방법이 도저히 안떠올라서 다른 사람들 풀이를 참고했다. 위에서 하나씩 계산해서 내려가면 된다...... 1149python알고리즘DP백준rgb거리1149 [백준/python/1463]1로 만들기 문제: 이 문제는 두 번째로 풀어보는 문제다. 처음 풀 때는 dp의 개념을 제대로 이해하지 못해서 어려웠는데, 두 번째는 훨씬 수월했다. 문제와 입력, 출력은 위에 링크를 통해 확인할 수 있다. 이 문제의 연산하는 방법은 총 세가지이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 그리고 문제에서 원하는 답은 1을 만드... python백준DP알고리즘DP [백준 C++] 2775 부녀회장이 될테야 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조... memoization2775baekjoonCDP부녀회장이 될테야2775 백준 12865 평범한 배낭 (Java) 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아... 백준골드 5DPDP [백준/python/1495]기타리스트 문제링크 : 이 문제는 이중배열을 사용해서 풀었다. 맞왜틀!!만 외쳤던 문제다. 알고보니 쉼표를 괄호로 적었던 것이였다,,,, 노래의 순서와 음 하나씩을 배열로 주었다. 배열에 1이 표시되어 있으면 해당음은 가능하다는 뜻이다. 범위를 잘 측정하여 연주가능한 음에 1을 표시해주고 마지막에 마지막곡의 배열에서 1을 가지고 있는 음을 찾아준다. 이 때, 최댓값을 출력하기위해 가장 높은음부터 내려왔... python백준DP알고리즘DP boj2293 동전1 링크 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는... 백준골드DPDP boj23318 행렬분할 링크 문제 n × m 크기의 행렬이 있다. 이 행렬을 가로로 a번, 세로로 b번 잘라 (a + 1) × (b + 1) 개의 부분으로 분할하려고 한다. 이 때, 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함되지 않은 부분은 존재할 수 없다. 위 그림 1과 같은 6 × 7 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다. 분할의 '점수'... 백준골드DP브루트포스DP [C언어] 백준 1904 : 01타일 생각의 흐름 문제를 보고 이게뭔가 싶었다. 일단 무작정 1부터 6까지 써봤다. 5까지 했을때 설마 피보나치인가 싶었는데 6에서 13이 나온 걸 보고 아 피보나치구나 싶었다. 피보나치를 동적 계획법 활용해서 푸는건 해봤기때문에,출력조건에 15746을 나눈 나머지를 출력한다. 이것만 생각하면 된다. 내가 푼 코드 15746를 위에다 한 이유는 처음에 printf에 해줬다가 오버플로우가 났다. n... C백준DPC [C언어] 백준 1003 : 피보나치 함수 생각의 흐름 이번에는 동적 계획법이라는 파트이다. 당연히 처음 들어보기에 바로 구글링으로 어떤건지 찾아보았다. 여기에서 도움을 받았다. 간단하게 말하자면, 기본적으로 피보나치로 예를 드는데, 중복되는 계산을 피하자! 이거다. 그걸 메모이제이션이라고 하는데, 크게 두가지 방법을 사용하나보다. 이렇게 기억하면서 내려가고, 올라간다. 이 방법을 익혀놓자. 먼저, 위 식을 생각안하고, 내 방식대로 ... C백준DPC [C언어] 백준 9184 : 신나는 함수 실행 생각의 흐름 문제 이해가 안돼서 그냥 무작정 w(1, 1, 1), w(2, 2, 2)를 써봤다. 이 값을 문제에 나와있는 함수에 대입하니 식이 엄청 많이 나왔다. 동적 계획법에 맞게 중복되는 값을 피보나치처럼 지우면 되겠구나 싶었다. 일단 예외처리해야 할 케이스를 정했다. a b c 셋중 하나라도 0이거나 0보다 작을경우 a b c 셋중 하나라도 20보다 클 경우 a < b < c 일 경우 ... C백준DPC [백준-15989] 1,2,3 더하기 4 수행시간: 184ms(pypy3) dp에는 정수i를 1,2,3의 합으로 나타내는 구성을 [1이 가장 큰 구성, 2가 가장 큰 구성,3이 가장 큰 구성] 로 저장한다. dp[i]의 1이 가장 큰 구성은 dp[i-3]의 1이 가장 큰 구성과 같다. dp[i]의 2가 가장 큰 구성은 dp[i-2]의 1이 가장 큰 구성과 2가 가장 큰 구성의 합 과 같다. dp[i]의 3가 가장 큰 구성은 dp[i... 파이썬백준DPDP [백준-11060] 점프 점프 수행시간: 72ms 나는 맨 마지막부터 처음으로 돌아오면서 최소 점프 횟수를 구하는 방식으로 문제를 풀었다. 예를 들어 입력이 n=10 maze=[1 2 0 1 3 2 1 5 4 2] 이렇게 주어지면 dp[9]는 9번방부터 9번방까지 최소 점프 횟수이므로 0이다. dp[8]은 8번방부터 9번방까지 최소 점프 횟수이다.maze[8]은 4이므로 9,10,11,12번 방까지 점프할수있고 점프할수있... 파이썬백준DPDP [C언어] 백준 11053 : 가장 긴 증가하는 부분 수열 생각의 흐름 LIS가 뭔지 몰라서 검색했다. LIS는 코딩테스트에서 자주 나오는 유형이고, 푸는 방법은 크게 두가지가 있다. DP와 이분 탐색이다. 먼저 DP는 n값이 커질수록 시간이 굉장히 오래 걸리는 방법이고, 이분탐색은 시간절약이 잘 되어 결국에는 이분 탐색을 사용한다고 설명이 되어있다. 이분탐색도 검색해보았지만, 아직 너무 어려워 DP로 풀기로 했다. 틀렸던 풀이 수정한 풀이 틀렸던 ... C백준수정필요DPC 이전 기사 보기