1. a와 b의 최대공약수를 찾는것 2. a%b가 0이면 a가 최대공약수 3. 그렇지 않으면 (b,a%b) 형태로 만들어서 다시 계산 4. 첫번째 반복에서 a

1. 두 수(A와 B) 의 약수들을 각각 모두 비교해준다 2. 비교 => A의 약수 a_n, B의 약수 b_n의 최대공약수를 뽑아서 최종답 ans에 곱해준다. 3. 숫자 = 숫자 % 10^9 + 10^9 해주면 숫자가 커지지 않고, 뒤에 9자리는 계속해서 보존 ​ ex) [boj]2824_최대공약수 #include #include #include using namespace std; int arrA[1001]; int arrB[1001]; int euclid(int a, int b) { int temp; while (1) { if (b == 0) { return a; } else { temp = b; b = a % b; a = temp; } } } int main() { int N, M; long lon..

소수구하기 수행시간(1,679 ms) 수행시간(6,004 ms이상) L=[2] for i in range(3,1000001,2): isDecimal=True for j in L: if i%j==0: isDecimal=False break if isDecimal==True: L.append(i) print(*L) 소수가 아닌수 a는 a보다 작은 소수에 의해 나누어 떨어짐 def isDecimal1(a): import math if a==2: return True if a==1 or a%2==0: return False for i in range(3,int(math.sqrt(a))+1,2): if a%i==0: return False return True L=[] for i in range(1000000):..

heap의종류 2가지 최대힙 : 부모노드가 자식노드보다 크거나 같음(root node에 최댓값) 최소힙: 부모노드가 자식노드보다 작거나 같음(root node에 최솟값) ​ * 직접 구현한 힙 # unsorted : heap으로 만들고자하는 리스트 # index : 아래로 내려가며 heap을 만들기 시작하는 노드 (해당 index의 자식노드들은 모두 heapify된다) def heapify(unsorted, index, heap_size): smallist = index left_index = 2 * index + 1 right_index = 2 * index + 2 if left_index < heap_size and unsorted[left_index] < unsorted[..

1. 아래가 없거나 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ​ 2. "\n"대신 endl이 들어가면 시간초과 #include #include #include using namespace std; int N, M, temp; set s; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 0; i > temp; s.insert(temp); } cin >> M; for (int i = 0; i > temp; cout

1. M에서 글자가 들어오면 index를 찾는 방식으로 구현했을때 시간초과가 발생. import sys N,M=map(int,input().split()) L=[] for i in range(N): L.append(sys.stdin.readline().rstrip()) for i in range(M): temp=sys.stdin.readline().rstrip() try: temp=int(temp)-1 print(L[temp]) except: print(L.index(temp)+1) 2. dictionary를 이용하여 key를 찾는 형식으로 했을 때 통과 import sys N,M=map(int,input().split()) dic1={} dic2={} for i in range(N): name=sys...

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