HwangHub

https://www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 문제 해석 해당 문제는 구간을 주고, 그 구간 내에서 특정 조건을 만족하는 경우를 '세어' 달라고 했다. 만약 일반적인 경우처럼 크게 입력값을 받는 loop로 묶고, 그 안에서 입력받은 것에 따라 x부터 y까지 슬라이싱을 하고, 슬라이싱한 배열을 sum 함수로 돌린다면 시간복잡도가 O(Q*N*(y-x))이다. 최악의 경우 이미 0.5초를 훌쩍 넘겨 버리므로, 다른 방안을 고려해야 한다. 마침 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 해석 해당 문제는 "넓은 탐색 범위에서 특정 숫자를 찾는 것"이므로 시간복잡도를 고려했을 때 이분탐색으로 풀어야 한다. 문제 풀이 첫 번째 시도 import sys input = sys.stdin.readline """real input""" n, m = map(int, input().split()) li = list(map(int, input().sp..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해석 쉬운 이분탐색 문제이다. 만약 단순히 for loop과 in 연산자를 이용해서 탐색하려 한다면, 그 시간복잡도가 O(n^2)이고 M의 개수가 100,000이므로 1초는 가볍게 넘길 것이다. 따라서 단순히 모든 요소를 탐색하는 개념으로 접근해서는 안된다. 이러한 경우 절반씩 짤라서 탐색하는 이분탐색(Binary Search)를 이용하면 O(..

https://www.acmicpc.net/problem/13423 13423번: Three Dots 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 www.acmicpc.net 문제 분석 우선 탐색을 해야 하는 문제이다. 이진 탐색에 대한 이야기해보면 필요 없는 범위에 대한 탐색을 막음으로서 탐색을 좀 더 빠르게 수행하는 방법이다. 보통 O(logN)을 갖는다. """(이진탐색) 첫 번째 풀이-시간초과""" t = int(input()) for i in range(t): n = int(input()) li = sorted(list(map(in..

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net algorithm_type math(정수론, 유클리드 호제법) is_clear False 문제 풀이 이 문제는 정말 "수학적인 사고"를 요하는 문제였다. 주어지는 숫자들은 모두 같은 숫자로 나눠서 같은 나머지를 가져야 하므로, 각 숫자들은 동일한 나머지 값을 뺀 상태에서 공약수가 존재한다는 의미이다. 따라서, 우리는 저 m이 어떤 수인지 알아내면 된다. 그러면 우리가 고등학교 때 x를 구했던 것 처럼, m을 구하..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 소수를 구할 때, 그 정의에 따라 우리는 아래 식을 쉽게 떠올릴 수 있다. def is_prime(n): for i in range(2,n): if n % i == 0: return False return True trash = input() li = list(map(int, input().split())) ans = 0 for i in li: if i == 1: pass elif is_prime(i): ans += 1 prin..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 문제 해석 위 문제는 조합으로도 쉽게 풀 수 있는 문제이지만, 백트래킹으로도 풀 수 있을 것 같아 백트래킹으로 풀어보려고 한다. 조합 이 풀이는 itertools 라이브러리의 조합을 이용하면 된다. 단순히 주어진 리스트 값에서 6개의 숫자를 뽑아주면 되는 문제다. 입력의 수가 주어지지 않아 혹시 몰라서 EOF처럼 try/except를 걸어주었다. # 첫 번째 풀이 : 조합 이용 impo..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/25916 25916번: 싫은데요 $6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다 www.acmicpc.net 첫 번째 풀이 우선, 조건에 따라 '연속'된 구멍의 '합'이 햄스터의 부피보다 작아야 하므로 투포인터로 풀면 되겠다고 판단했다. 이제 로직을 구성하면 되는데, 일정 연산 결과가 조건보다 작으면 냅다 오른쪽 포인터를 진행시키는게 일반적이라 생각했는데, 이번 문제에서는 포인터가 가리키는 범위의 합이 항상 햄스터의 부피 이하여야 하므로 오른쪽 포인터를 진행한 상황에서의 값이 몇인지 체크하고, 부피 이하로 들어올 경우 오른쪽 포인터를 진행시킨 뒤에 max 값(이후 결과값)을 저장했다. 이를 ..