1.풀이 합이나 평균을 구할때 수학적 사고를 하자! ​ (1) i번째 숫자가 (0~9중)될 수 있는 모든 수를 찾는다. ex) digitLSize=[[1],[0,8],[8,9]] => 100의자리에 1이 올 수 있고, 10의자리는 0,8이 올 수 있고, 1의자리는 8,9가 올 수 있다. ​ (2) 될 수 있는 모든 경우의 수를 찾는다. * dfs로 완전탐색하려 했지만 메모리 초과가 났다(소스코드1) * 각자리에 올 수 있는 숫자를 나올수 있는 횟수만큼 더하면 총 합을 구할 수 있다. (소스코드2) 위의 예시에서 100의 자리 1은 총 2*2번나오므로 100*1*4, 10의자리 0은 총 1*2번나으모르 10*0*2... ​ 2. 소스코드 (1) 소스코드1 (메모리초과) import sys sys.setre..

1. 풀이 (1) 시간복잡도 그냥 풀면 정말 간단한 백트래킹 문제이지만 시간이 O(2^(N*N)) 이므로 초과이다. 해법은 체스판의 특성을 생각하고 하얀색 체스판에 채울 수 있는 최대의 비숍과 검은색 체스판에 채울 수 있는 최대의 비숍을 각각 따로구해서 더해주는 것이다. 이렇게 하면 시간복잡도는 아래와 같이 된다. O(2^(N/2*N/2)+2^(N/2*N/2))=O(2^(N/2*N/2)) (2) N이 짝수일 때 주의사항 N이 홀수이면 확인할 블럭이 아래와 같이 2씩 증가하지만 0 3 5 7 9 N이 짝수이면 확인할 블럭이 마지막 or 마지막 바로앞 열에서 3 or 1씩 증가해야 한다 0 2 5 7 8 10 13 15 따라서 이를 유의해서 탐색을 해줘야한다! 2. 소스코드 dR=[-1,-1,1,1] dC=..

파스칼의 삼각형으로 조합을 구할 수 있다. 위의 삼각형 형태를 행렬로 바꾸면 하삼각행렬로 만들 수 있다. (i,j)위치의 값이 정확히 iCj가 되는 예쁜 형태가 된다. (j==0일때만 1을 넣어주면된다.) ​ ex)[boj]11051_이항계수2 #include #include using namespace std; long long pascal[1000][1000]; int main() { int N, K; int max = 10007; cin >> N >> K; for (int n = 0; n

1.풀이 (1) a의 b승을 구하는문제. 진짜 a를 b번 곱하면 당연히 시간초과. (2) a^b => (a제곱)^(b//2) 로 계산하는것이 핵심. EX) 2^4는 2를 네번곱해야 하지만, 2^4->4^2->16^1로 하면 3번만에 계산가능 (3) 제곱수가 홀수인 경우는 하나빼서 계산해야 하기 때문에 경우의 수를 나눠준다. (4) 제곱수가 1이 될 때 까지 재귀를 반복한다. ​ 2. 소스코드 A, B, C = map(int, input().split()) def power(a,b): #1이면 끝 if b==1: return a%C #짝수이면 제곱 if b%2==0: return power(a**2%C,b//2) #홀수이면 곱하고 제곱 else: return (a*power(a**2%C,b//2))%C d..

1. 풀이 처음엔 N개의 점을 모두 사용하여 N/2개의 선분을 만들었을 때 선분의 합이 최소가 되는 경우를 구해야 한다고 생각했다. 따라서 nC2*n-2C2*n-4C2...*4C2*2C2의 경우를 생각했었다. 하지만 문제에서 요구하는것은 "벡터의합의 길이"이다. ​ 즉 4개의 점 (x1,y1),(x2,y2),(x3,y3),(x4,y4) 가 있을 때 (x_a+x_b -x_c-x_d , y_a+y_b-y_c-y_d )의 길이의 최솟값을 구하면 된다. ​ 따라서 모든점의 개수(N개)중 시작점의 개수(N//2)를 뽑는 경우(나머지는 자동으로 도착점이 된다)는 nCn//2 이므로 해당 경우를 완전탐색하면 답이 된다. ​ 2.소스코드 import sys from itertools import combinations..

0~size-1까지의 모든 숫자들에 대해서 소수인지를 판별 1. isNotPrime는 소수인것이 0 int isNotPrime[size]; void eratosthenes(size) { isNotPrime[1] = 0; isNotPrime[1] = 1; // 0과 1은 소수가 아니다. for (int i = 2; i*i < size; i++) { if (!isNotPrime[i]) { //소수이거나, 아직 탐색을 안했다면 (isNotprime은) 0 for (int j = i * i; j < size; j += i) { isNotPrime[j] = 1; } } } } 2. isPrime는 소수인것이 1 #에라토스테네스 isPrime=[1 for i in range(size)] def prime(): is..

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