1. 풀이 (1) 각 숫자의 계수를 구해준 후 (2) 계수가 가장 큰 숫자부터 9에서 0까지 차례대로 넣어준다. 이때 알파벳이 10개이상일 때(숫자 0까지 써야할 때) 첫째자리에 있는 숫자가 0이되지 않도록 주의한다. ​ ex) (1) 숫자의 계수 구하기 ABC : 100A+10B+C BCA : 100B+10C+A 총합 => 101A+110B+11C ​ (2)계수가 가장 큰 수부터 9에서 0까지 차례대로 넣기. 정렬하면 => 110B,101A,11C 계수가 큰 수 부터 9씩 넣기 (B=9, A=8, C=7) ​ ※참고 : [boj]1339 단어수학 ​ 2. 소스코드 N=int(input()) gasoo=[[0,"A"],[0,"B"],[0,"C"],[0,"D"],[0,"E"], [0,"F"],[0,"G"]..

1. 풀이 (1) 물병의 개수가 a일때, 최대로 합칠 수 있는 개수를 반환하는 함수 cheak(a)를 만든다. - 2로 나누었을 때 몫이 묶인 물병의 수가되고, 나머지가 묶이지 않은 물병의 수가된다. ​ (2) i는 N에서 시작하여 1씩 증가하면서 cheak(i)가 K이하가 되는 첫번째 수를 구한다. - 그 수가 최소로 더 필요한(더 사야할) 물병의 수가 된다. ​ 2. 소스코드 N,K=map(int,input().split()) def cheak(num): ans=0 while(1): a=num//2 b=num%2 ans+=b num=a if num==0: break return ans if K>=N: print(0) else: i = N while(1): if cheak(i)

1. 풀이 가장 큰 줄어드는 숫자는 9876543210 이므로 0부터 포문을 돌리면 당연히 시간초과. 재귀적인 방법이나 수학적인 구현으로 문제를 해결하려고 했으나 방법이 떠오르지 않았다. ​ 결론은 조합을 이용하여 모든 경우를 다 구하고 N번째를 출력하면 된다. 만들 수 있는 모든 줄어드는 수는 10C1+10C2+10C3...10C10개 이다. (하나의 경우의 수를 뽑은 후 내림차순으로 정렬 시켰을때 특정한 하나의 줄어드는 숫자에 대응 된다.) 즉 경우의 수를 다 합쳐도 1024밖에 되지 않기 때문에 위의 방법으로 풀 수가 있다. ​ *나올 수 있는 경우의 수를 구할 수 있고, 시간복잡도를 계산 후 완전탐색이 가능한, 위와 같은 경우를 유의하자. ​ 2. 소스코드 from itertools import ..

1. 풀이 처음엔 에라토스테네스의 체를 이용하여 소수를 모두 구하고, dfs를 이용하여 구하려고 했다. (소스코드1) (1)소수리스트가 정렬되어 있기 때문에 크기가 N보다 커지면 벡트래킹. (2) i번째 숫자를 추가했을때 x값이 나오는 경우는 더이상 탐색하지 않기위해서 visited[i][x]를 관리해 주었지만 시간초과가 났다. ​ 정답은 골드바흐의 추측을 응용해서 풀이하는것이였다. (소스코드2) [골드바흐의 추측] 2보다 큰 모든 짝수는 2개의 소수의 합으로 표현할 수 있다. 이를 응용하면 가장 작은 네개의 소수로 만들 수 있는 수 8(2+2+2+2)이상의 숫자는 소수4개로 표현할 수 있다는 뜻인데 그 방법은 다음과 같다. ​ (1) N이 짝수일때 N이 짝수일때는 N-4도 짝수이다. (N-4>=4) 따..

1. 풀이 처음엔 dfs로 완전탐색했고 시간초과가 발생했다. (소스코드1) 규칙을 찾아서 풀어야 한다. 처음에 같은모양을 갖고 있지 않는 행은 열 단위로 스위치를 누를 때 절대 같아질 수 없다. 즉 (1) 동시에 켜져있는 행이 될 수 있는 행들 시작할 때 같은 모양을 갖는 행들 (union find로 찾았다) (2) 해당 집합이(같은 모양을 갖는 행들) k번째에 켜져있는상태가 될 수 있는가? 시작할때 0의 개수와 k를 2로 나눈 나머지가 같다 ​ 2. 소스코드1 (시간초과,dfs 완전탐색) N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) k=int(input()) def push(j): for i in range(N..

1. 풀이 (1) 가장 큰 숫자를 만들기 위해선 최대한 많은 자릿수를 확보해야한다. => 최대한 많은 숫자를 사기 위해서 가장 싼 숫자를 구매한다 (pick=[a,b,c,d] => d*1000+c*100+b*10+a를 나타낸다) (2) 가장 큰 자릿수 부터 큰 숫자로 바꿀 수 있는지 (남은돈)과 (바꿀때 드는 차액)을 비교한다. => pick에 가장 오른쪽 원소부터 가장 큰 숫자에서 하나씩 작은 숫자로 내려오며 확인한다. ​ *예외 (1) 0이 가장 싼 경우가 있다. 이경우 시작숫자가 0000...이된다(pick=[0,0,0,0...]) 이때 0을 산다고 돈을 다 쓰고 다른 숫자를 살 수 없으면, 숫자를 만들 수가 없다. 따라서 그 경우(0만있고 다른숫자를 살 수 없는)를 대비해 0을 다시 환불하고 돈을..

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