전체 702

[백준]2624 동전바꿔주기 #경우의 수

1. 풀이 dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수. 기본적으로 무제한 동전dp(https://blog.naver.com/ngoodsamari/221664277387)와 같지만 사용할 수 있는 동전의 개수 제한이 추가된 문제이다. 무제한 동전 dp문제와 리스트형식은 같지만 푸는 방법이 전혀 다르다. ​ (1) 1번째부터 k번째까지 사용할 수 있는 동전을 하나씩 늘려간다 (2) i번쨰 동전을 사용할때는 i-1번째 동전까지 사용한 경우의 수에서 i번째 동전을 최대 사용가능한만큼 하나씩 늘려가며 확인한다. (3) i번째 동전까지 사용하여 0원을 만드는 경우는 1임을 주의한다. (무제한 동전dp와 같다) ​ 2.소스코드 T=int(input()) k=int(input()) L..

알고리즘/dp 2020.06.15

[백준]1563개근상 #dp#dfs

1. 풀이 처음엔 dfs만으로 완전탐색으로 문제를 풀었지만 시간초과. (소스코드1) 정답은 dp+dfs였다. 몇번을 풀었지만 어려운 dp & dfs문제.. ​ [원리] (1) 조건에 맞지 않으면 i. return 0으로 가지치기 (2) 조건에 맞으면 i. 끝까지가면 : return 1 ii. 방문한적이 있으면 return dp iii. 방문한적이 없으면 재귀후 저장 dp저장. 핵심은 바로 ii.방문한적이 있으면 return dp를 하는것! ​ ex) 4일동안 지각을 한번, 결석을 연속1번 한 경우를 생각해보자. 만약 이를 DFS+DP(소스코드1)로 푼다면, 해당 경우를 만족하는 모든 경우(OLOA,LOOA,OOLA)에 대해서 한번만 끝까지 계산을 해주고 DP에 저장해놓은다음, 다음에 만났을때 DP값을 반..

알고리즘/dp 2020.06.15

[백준]2482 색상환 #dp#grid

1.풀이 (1) 점화식 dp[i][j] : i개의 색 중 j개를 사용할 수 있는 경우의 수 (단 i dp[i][j]=dp[i-1][j]+dp[i-2][j-1] ​ dp[N][K] : N개의 색 중 K개를 사용할 수 있는 경우의 수. * i==N일때는 (원형이므로) 1번째 색깔이 칠해져있을때를 고려해주어야 한다. ㄱ. N-1번째까지 K개 사용한 경우 : dp[N-1][k] (i(=N)번째 색을 사용하지 않는 경우) : dp[N-1][K] ㄴ.1번째와 i-1번째가 색칠되어 있지 않는경우(i(=N)번째 색을 사용하는 경우) : dp[N-3][K-1] => dp[N][K]=dp[N-1][K]+dp[N-3][K-1] ​ (2) 초기조건 ㄱ. i개의 색 중 1개를 사용할 수 있는 경우는 항상 i개 ㄴ. i개의 색 ..

알고리즘/dp 2020.06.15

[백준]1912 연속합 #dp

1.풀이 (1) 연속된 수의 합이므로 수열이 모두 양수라면 당연히 모든수를 다합하는것이 최대연속합이 된다. 하지만 음수가 있다면 달라진다. ​ (2) 점화식 (dp[i] : i번째 숫자를 포함하는 최대연속합) - 소스코드1 dp[i]=max(L[i],dp[i-1]+L[i]) - 소스코드2 그전까지 값(nowSum)이 음수이면 -> 이전값과 더하지 않고 새로시작 그전까지 값(nowSum)이 양수이면 -> 이전값과 더함 ​ 2.소스코드 (1) 소스코드1 n=int(input()) L=list(map(int,input().split())) dp=[0 for i in range(n)] nowSum=0 for i in range(n): nowSum=max(nowSum+L[i],L[i]) dp[i]=nowSum p..

알고리즘/dp 2020.06.15

[백준]1699 제곱수의 합 #dp

1.풀이 N보다 작은 수들을 가지고 dp[N]를 만들 수 있는 방법은 다음과 같다 ​ (N-1^2) + 1^2 (N-2^2) + 2^2 (N-3^2) + 3^2 . . . ​ 따라서 dp[N]을 자연수 N의 최소 제곱수의 개수라고 할때 점화식을 dp[N]=min(dp[N-1^2],dp[N-2^2],dp[N-3^2]...)+1로 나타낼 수 있다. ​ 2.소스코드 import math INF=9876543210 N=int(input()) dp=[i for i in range(N+1)] dp[0]=0 for i in range(1,N+1): j=1 while(1): power=j**2 if i

알고리즘/dp 2020.06.15

[백준]1351 무한수열 #dp#dfs

1.풀이 처음에는 0부터 N까지 올라가는 bottom up 방식으로 쉽게 풀려고 했다. 하지만 N의 범위가 최대 10^12 이기 때문에 P,Q와 관계없이 무조건 시간초과 메모리초과다. ​(소스코드1) ​ 올바른 풀이는 다음과 같다. (소스코드2) (1) top down방식으로 dp를 풀어야 한다. N에서 시작하여 P,Q로 쪼개가면서 탐색한다. (2) 이때 한번 탐색한 곳은 저장해놓는다 (dp) (3) 하지만 N의 범위가 10^12 이기 때문에 배열로는 메모리 초과가 난다. 따라서 dictionary 자료형을 써야한다. 새로운 유형의 dp였다. ​ 2. 소스코드1 (1) 소스코드1 (bottom up, 메모리초과, 시간초과) N,P,Q=map(int,input().split()) dp=[1 for i in..

알고리즘/dp 2020.06.15

[백준]2666 벽장문의 이동 #dp#3차원

1. 풀이 (1) dp도 모든 경우를 탐색하는 방법이다. (2) dp[case][a][b] : case번째에 왼쪽문이 a에 열려있고, 오른쪽문이 b에 열려있을때 까지의 최소이동 (3) case-1에서 case로 넘어갈 때, 맨하탄거리를 더해주어서 더 최솟값을 찾는다. ​ 2. 소스코드 N=int(input()) a,b=map(int,input().split()) a-=1 b-=1 size=int(input()) L=[0] for i in range(size): L.append(int(input())-1) maxNum=500 # dp[case][a][b] : case번째에 왼쪽문이 a에 열려있고, 오른쪽문이 b에 열려있을 때 최소이동 (a

알고리즘/dp 2020.06.15

[백준]10844 쉬운계단수 #dp

1. 풀이 (N의 크기를 살펴보고 2차원이 가능하다면 2차원 dp를 떠올려보자..) ​ dp[i][j] : i자리수에서 j로 끝나는 계단 수의 개수 이때 i자리의 j로 끝나는 수는 i-1자리의 j-1로 끝나는수와 , j+1로 끝나는 수 끝에 j만 붙이면 되기때문에 두 경우의 수의 합으로 표현할 수 있다. (단 j가 0이면 1을, 9이면 8만을 붙일 수 있는것을 주의) ​ 따라서 아래와 같은 점화식을 만들 수 있다. dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1] ​ 2. 소스코드 N=int(input()) dp=[[0 for j in range(10)] for i in range(N+1)] for j in range(1,10): dp[1][j]=1 for i in range(2,N+1): ..

알고리즘/dp 2020.06.15

[백준]2294 동전2 #dp

1. 풀이 dp[i][j] : i번째 동전까지 이용해서 j원을 만들때 가능 한 최소동전개수. i번째 동전까지 이용해서 j원을 만들때 가능 한 최소 동전개수는 i-1번째 동전까지 이용했을때 j를 만드는 경우와 (j-(i번째동전의 금액))최소동전수+1 한 경우 중 최소 값을 선택하면 된다. ​ 따라서 점화식은 아래와 같다 dp[i][j]=min(dp[i][j-i번째 동전의금액]+1,dp[i-1][j]) ​ 이때 dp를 2차원으로 만들었을 때 바로 위에 행과 비교를 하기 때문에 1차원 dp 리스트를 만들어도 상관이 없다. => 1차원 for문에서 i번째 반복을 마친 상태가 결국 2차원 dp의 i행 따라서 메모리를 최적화 시키기 위해 1차원으로 dp를 생성한다. ​ 2. 소스코드 n,k=map(int,input..

알고리즘/dp 2020.06.15

[백준]9251 LCS #dp

1. 풀이 (1) dp[i][j] : A의 i번째, B의 j번째 문자열까지의 최장 공통 문자열의 수 (2) A[i]와 B[j]가 같다면? 왼쪽위(그전까지의 최장공통문자수)에서+1 (3) 다르다면? 위,왼쪽숫자중 최대수 ​ 2. 소스코드 A="0"+input() B="0"+input() sizeA=len(A) sizeB=len(B) dp=[[0 for i in range(sizeB)] for j in range(sizeA)] for i in range(1,sizeA): for j in range(1,sizeB): if A[i]==B[j]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) print(dp[sizeA-1][sizeB-1])

알고리즘/dp 2020.06.15

[백준]2156 포도주시식 #dp

1. 풀이 3번연속은 안된다. 따라서 경우의 수를 다음과 같이 나눈다 ​ (1) i번째를 마시고 i-1번째를 마시는경우 -> (i번째) + (i-1번째) + (i-3번째까지 최대) (2) i번째를 마시고, i-1번째를 마시지 않는 경우 -> (i번째) + (i-2번째까지 최대) (3) i번쨰를 마시지 않는경우 -> (i-1번째까지 최대) ​ 2. 소스코드 N=int(input()) dp=[0 for i in range(N+3)] preNum=0 for i in range(3,N+3): nowNum=int(input()) # i번째와 i-1번째를 마시는 경우 a=preNum+nowNum+dp[i-3] # i번째를 마시고, i-1번째를 마시지 않는 경우 b=nowNum+dp[i-2] # i번째를 마시지 않는..

알고리즘/dp 2020.06.15

[백준]11062 카드게임 #사선dp

https://blog.naver.com/ngoodsamari/221776557221 행렬곱셉순서와 비슷한 문제. 1. 풀이 (1) 단 두개가 남았을 때 부터 생각해서 N개의 카드가 있을 때 까지 확장한 후 최적의 선택을 찾는다. (2) dp[i][j] : i~j를 뽑았을 때 근우가 얻을 수 있는 최대 점수 (3) 근우가 항상 먼저 뽑기 때문에 현재까지 뽑은 카드의 개수(N-(j-i+1))가 짝수이면 근우차례이고, 홀수이면 명우차례이다. (4) 명우도 항상 최적의 선택을 하기 때문에, 명우차례일때는 근우입장에서 최소의값을 선택해야 한다. ​ 2. 소스코드 #include #include #include using namespace std; int L[1000]; // dp[i][j] : i~j를 뽑았을때..

알고리즘/dp 2020.06.15

[백준]1944 복제로봇 #MST

1. 풀이 더보기 시작점, 열쇠가 있는 모든 지점에서 로봇이 복제되고, 모든 열쇠를 얻어야 하며, 이때 모든 로봇의 이동거리를 구한다. 위의 문제가 MST문제임을 알면 구현은 매우쉽게 일반적인 MST를 푸는것과 같이 하면 된다. 하지만 위의 문제 MST문제인지를 알기가 어렵다. 따라서 조건을 어느정도 외워두고 비슷한 상황에서 MST를 떠올릴 줄 아는것이 중요해 보인다! 2. 소스코드 from collections import deque import sys dR=[0,0,-1,1] dC=[1,-1,0,0] N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def dist(sR,sC,fR,fC): q=deque([[sR,..

알고리즘/graph 2020.06.15

[백준]5573 산책 #dp

1. 풀이 (1) N번째의 상태를 확인하기 위해 N-1번수행한 후의 맵을 구현한다. (2) d[i][j] : 현재 맵의 상태. 0이면 아래, 1이면 오른쪽 (3) d[i][j]에 N번 존재하면, d[i+1][j], d[i][j+1]에 N/2번 존재한다. 이때 d[i][j]가 아래이면 d[i+1][j]가 추가로1이 더해지고, 오른쪽이면 d[i][j+1]가 추가로1 더해진다. (4) 최종맵은 홀수이면 오른쪽(1)이고, 짝수이면 아래(0)이므로 2로 모듈러연산을 해준다. (5) 최종답을 구하기 위해 N번째 산책을 시작한다. ​ 2. 소스코드 #include #include #include using namespace std; int d[1002][1002]; int map[1002][1002]; int mai..

알고리즘/dp 2020.06.14

[백준]1756 피자굽기 #dp#정석

dp가 어떻게 쓰이는지 직관적으로 와닿는 문제. ​ 1. 시간초과 코드 피자를 순서대로 위에서부터 들어갈 수 있을 때 까지 넣어보는 방식. *시간복잡도 O(피자수*오븐깊이) from collections import deque D,N=map(int,input().split()) oven=[9876543210]+list(map(int,input().split()))+[0] pizza=deque(list(map(int,input().split()))) #바닥임 bottom=D+1 i=100 for i in range(N): temp=pizza[i] for d in range(1,bottom+1): if oven[d]

알고리즘/dp 2020.06.14

[백준]5557 1학년 #dp

1. i행 j열의 의미 dp[i][j]는, j번째로 들어온 숫자까지 더하거나 뺏을 때 i가 되는 경우의 수를 나타낸다. ​ 2. 점화식 dp[i][j](i는 0~20)는 dp[i][j-1]에서 j번째들어온 숫자만큼을 더하거나 뺀값을 추가해주는 형태로 진행된다. 말이 어려우므로 표로 설명한다. 숫자가 가능한 범위는 0~20이므로 표의 행은 21개, 열은 들어오는 숫자의 개수만큼 확보한다. 11 8 3 2 4 8 7 2 4 0 8 8 (1) 첫번째 input 8에 1을 넣는다 8 0 1 0 1 2 3 4 5 6 7 8 1 9 10 11 12 13 14 15 16 17 18 19 20 2) 두번째 input은 3이다. 첫번째 input에서 3을 더하고 빼주면 5와 11이 된다. 이 경우들을 더해준다. 8 3 ..

알고리즘/dp 2020.06.14

[백준]7579 앱 #dp#배낭

배낭문제와 유사한 dp문제. 배낭 ​ 앱 가치 == 메모리 무게 == 비용 1. 풀이 (1) dp[i][j] : i번째 앱까지 끌 수있고, j 비용까지 가능할 때, 최대 메모리 (2) 비용이 0인 앱도 있으므로 0열은 0으로 채우지 않도록 주의. (3) 최대 메모리를 찾는 문제이기 때문에 나올 수 있는 최대 비용까지 열을 확보해야한다. (4) 점화식 dp[i][j]는 두가지 값을 비교하여 큰값을 넣는다. 1) i-1번째 앱까지 끌 수 있는 상황. => dp[i-1][j] 2) i-1번째 앱까지 끌 수 있는 상황에서 i번째 비용만큼이 확보된 값에서 i번째 앱을 끄는상황. => dp[i-1][j-(i의 비용)]+(i의 메모리) 5. 특정메모리(M)이상의 값을 확보할 수 있을 때 최소 비용을 찾으므로 탐색하면..

알고리즘/dp 2020.06.14