K

에라토스테네스의 체의 원리를 응용한 문제 시간 복잡도를 위해 제곱수 판별에 해당 원리를 응용한다. # 제곱 ㄴㄴ 수 # 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. # 첫째 줄에 두 정수 min과 max가 주어진다. # 첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다. import math min, max = map(int, input().split()) check = [False] * (max - min + 1) for i in range(2, int(math.sqrt(max)) + 1): now = i * i start = min // now if min % now != 0: start += 1 for j in r..

에라토스테네스의 체를 이용한 문제 일차원 배열의 크기를 왜 저렇게 설정하는 건지 모르겠다 .. # 소수 & 팰린드롬 # 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. # 첫째 줄에 N이 주어진다. # 첫째 줄에 조건을 만족하는 수를 출력한다. def Pal(x): num = str(x) mid = len(num) // 2 for i in range(mid): if num[i] != num[-i - 1]: return False return True import math n = int(input()) a = [0] * 10000001 for i in range(2, len..

에라토스테네스의 체를 이용한 문제 일차원 배열의 범위를 10^7까지 설정하는 것이 핵심 문제에서 제한 범위가 10^14인데, 제곱근을 찾으면 문제를 해결할 수 있기 때문 # 거의 소수 # 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. # 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. # 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. # 첫째 줄에 총 몇 개가 있는지 출력한다. import math m, n = map(int, input().split()) a = [0] * 10000001 # 시간복잡도를 위해 10^7까지만 수행 (문제 범위 10^14까지인데 제곱근만 찾으면 되기..

에라토스테네스의 체를 이용한 문제 제곱근까지만 계산해야 시간 복잡도를 만족할 수 있다. # 소수 구하기 # M 이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하시오. # 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. # 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. import math m, n = map(int, input().split()) a = [0] * (n + 1) for i in range(2, n + 1): a[i] = i for i in range(2, int(math.sqrt(n)) + 1): # 시간복잡도를 위해 제곱근까지만 수행 if a[i] == 0: continue for j in range(i + i, n + 1, i): a[j] = 0 for i i..

그리디 알고리즘을 이용한 문제 # 잃어버린 괄호 # 첫째 줄에 양수, +, -로 이루어진 식이 주어진다. 괄호를 적절히 이용하여 최소값을 만드시오. # 첫째 줄에 정답을 출력하시오. def Sum(i): B = list(i.split('+')) total = 0 for k in B: total += int(k) return total ans = 0 cnt = 0 A = list(input().split('-')) for i in A: k = Sum(i) if cnt == 0: # 첫 번째 값인 경우만 더하기 ans += k cnt += 1 else: ans -= k print(ans)

그리디 알고리즘을 이용한 문제 # 회의실 배정 # 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. # 첫째 줄에 회의의 수 N, 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어진다. 이는 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. # 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다. n = int(input()) A = [[0, 0] for _ in range(n)] for i in range(n): S, E = map(int, input().split()) A[i][0] = E # 종료시간을 기점으로 정렬해야 하기 때문에 앞에 저장 A[i][1] = S A.sort() cnt = 0 end = -1 for i in range(n):..

그리디 알고리즘과 우선순위 큐를 이용한 문제 # 수 묶기 # 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. # 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다. # 수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오. # 첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. # 수를 합이 최대가 나..

그리디 알고리즘과 우선순위 큐를 이용한 문제 # 카드 정렬하기 # 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. # N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오. # 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다. # 첫째 줄에 최소 비교 횟수를 출력한다. from queue import PriorityQueue n = int(input()) queue = PriorityQueu..

그리디 알고리즘을 이용한 문제 # 동전 0 # 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. # 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. # 첫째 줄에 N, K가 주어진다. 둘째 줄부터 N개의 줄에 동전의 가치가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) # 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. n, k = map(int, input().split()) A = [] for i in range(n): A.append(int(input())) # 리스트의 뒤부터 탐색하며 k보다 큰 동전..

간단하게 푸는 방법 그러나 n^2의 시간 복잡도를 가지기 때문에 실패한다. n = int(input()) k = int(input()) A = [[] for _ in range(n)] B = [] for i in range(n): for j in range(n): A[i].append((i + 1) * (j + 1)) x = (i + 1) * (j + 1) B.append(x) print(B[k]) 이 문제를 푸는 핵심은 이진 탐색을 이용하는 것 이진 탐색을 이용하여 중앙값보다 작은 값의 개수가 k-1개일 때 멈추면 된다. # K번째 수 # 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순..