list는 set과 dictionary 보다 요소를 찾는 속도가 느리다. ​ 1. list(시간초과) N,M=map(int,input().split()) L=[] for i in range(N): L.append(input()) ans=0 ansL=[] for i in range(M): temp=input() if temp in L: ans+=1 ansL.append(temp) L.remove(temp) print(ans) for i in sorted(ansL): print(i) 2. set(통과) N,M=map(int,input().split()) s=set() for i in range(N): word=input() s.add(word) ans=0 ansS=set() for j in range(M):..

0. 기억해 실버3 이지만, stack을 생각하지못하면 풀 수 없는 문제임. 커서가 나오면 보통 스택을 쓴다고 하니 유념할것 ​ 1. 리스트 하나 (시간초과) (1) cursur변수를 따로두고, 리스트하나로 풀때. (2) insert와 del를 위해 리스트를 처음부터 끝까지 탐색해야하기 때문에 시간초과. import sys T=int(input()) for t in range(T): word = sys.stdin.readline().rstrip() size = len(word) cursur = 0 nowWord=[] for i in range(size): if word[i]=="": if cursur0: del nowWord[cursur-1] cursur-=1 else: if cursur==len(now..

1. 생각 수열의 연속합 중에서 특정 숫자를 만족하는 연속합을 찾는다. (1) 수열의 요소들이 모두 양수가 아니기 때문에, 투포인터는 쓸 수 없고, (2) N이 최대 200,000이므로 O(N)으로 끝내야한다. ​ 2. 풀이 (1) 수열의 누적합을 계속해서 구한다. (S[i] : 0에서부터 i까지의 누적합) ​ (2) i번째 숫자를 포함하는 연속합 중 K값이 되는 경우의 수는 S[i]-S[x]=K 를 만족하는 x의 개수와 같다. (즉 S[x]=S[i]-K 를 만족하는 x의 경우의 수.) ​ (3) d라는 map을 관리하여 이를 바로 찾아준다 (d[a]=c : 누적합이 a가 되는 경우가 c개) ​ 3. 소스코드 N,K=map(int,input().split()) L=list(map(int,input().s..

1. 풀이 (1) 약 한알을 다먹었을때 w, 반개만 먹었을때 H이므로 나올수있는 경우는 약이 2개일때 WWHH를 적절히 조합한 경우. (2) 이때 고려해야할 점은 약이 반개가 남으려면 그 전에 한개를 쪼갠적이 있어야한다. 즉 앞에서부터 순서대로 진행할 때 H의 개수가 W의 개수보다 많으면 안된다. (HW(X),WHH(X),WHWHH(X)) (3) 따라서 아래와 같은 점화식을 만들 수 있다. DP[i][j] : 알약반개 i번, 알약한개를 j번 먹었을때 경우의 수 그리고 이는 알약반개를 i-1번먹고, 알약한개를 j번먹은상태 (dp[i-1][j]) 에서 알약 반개를 먹는경우 + 알약한개를 i번먹고, 알약반개를 j-1번먹은상태(dp[i][j-1])​ 에서 알약 한개를 먹는경우의 합이된다. => 즉 dp[i][j..

난 이 문제가 너무어렵다. 이전에 저장한 캐시를 쓰긴 하지만 계속해서 새로운것이 추가되는 형태의 dp문제는 처음이라 너무 어렵다. ​ 1. 풀이 (1) i가 홀수이면 만들 수 있는 경우가 없으므로 0 (2) 짝수일때는 아래의 두가지 경우를 합해준다 ① i-2일때 만들 수 있는 경우에 세가지 서로다른 형태를 추가한 경우 dp[i-2]*3 ② i-2에서 추가한것만으론 만들 수 없는 형태 (2칸씩 쪼개지지 않는 경우) 매번 새롭게 만들어지는 형태 ​ 2. 소스코드 N=int(input()) dp=[0 for i in range(N+1)] dp[0]=1 for i in range(2,N+1): if i%2!=0: continue dp[i]+=dp[i-2]*3 for j in range(4,i+1,2): dp[i..

1. 풀이 dp[i][j] : i에서 j문자열까지 만들 수 있는 길이 중 최대 dp[i][j]를 구하기 위해선 아래 두가지를 고려해주면 된다. ​ (1) (A[i]==a and A[j]==t) or (A[i]==g and A[j]==c) 인경우 dp[i+1][j-1]+2 => 양끝이 조건에 만족하면 KOI유전자 ​ (2) dp[i][j]=max(dp[i][j-s]+dp[i+j+1-s][j] (k: 1~j-i)) => () + ()가 가능(각조합에서 최댓값 찾기) 2. 소스코드 A=input() size=len(A) dp=[[0 for j in range(size)] for i in range(size)] for j in range(1,size): for k in range(size-j): dp[k][j ..

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..

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값을 반..

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개의 색 ..

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..

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

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..

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

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): ..

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..

최소로 움직이는 횟수 = 전체명수 - 처음에 최대로 정렬되어있는 개수(LIS) LIS를 구성하는 요소를 제외하고는 모든 유치원생이 각자 한번씩은 반드시 움직여야 한다. N=int(input()) L=[] for i in range(N): L.append(int(input())) lis=[1 for i in range(N)] for i in range(1,N): for j in range(0,i): if L[j]

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])

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번째를 마시지 않는..