알고리즘/백준
-
[백준] 1655번 가운데를 말해요 (파이썬)
1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 코드 import heapq import sys left, right = [], [] n = int(input()) for _ in range(n): x = int(sys.stdin.readline()) if len(left) == len(right): heapq.heappush(left, (-x, x)) else: heapq.heappush(right, (x, x)) if right and left[0][1] > right[0][1]: left..
-
[백준] 11286번 절댓값 힙 (파이썬)
11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 코드 import heapq import sys n = int(input()) queue = [] for _ in range(n): x = int(sys.stdin.readline()) if x == 0: if not queue: print(0) else: print(heapq.heappop(queue)[1]) else: heapq.heappush(queue, (abs(x),x))
-
[백준] 1927번 최소 힙 (파이썬)
1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 코드 import heapq import sys n = int(input()) queue = [] for _ in range(n): x = int(sys.stdin.readline()) if x == 0: if not queue: print(0) else: print(heapq.heappop(queue)) else: heapq.heappush(queue, x)
-
[백준] 11279번 최대 힙 (파이썬)
11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 코드 import heapq import sys n = int(input()) queue = [] for _ in range(n): x = int(sys.stdin.readline()) if x == 0: if not queue: print(0) else: print(heapq.heappop(queue)[1]) else: heapq.heappush(queue, (-x, x))
-
[백준] 12015번 가장 긴 증가하는 부분 수열 2 (파이썬)
12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 코드 import sys def find(i): low, high = 1, len(stack)-1 while low i: high = mid else: low = high = mid return high if __name__ == '__main__': n = int(sys.stdin.readline()) li = list(ma..
-
[백준] 2110번 공유기 설치 (파이썬)
2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 코드 import sys N, C = map(int, (input().split())) house = [int(sys.stdin.readline()) for _ in range(N)] house = sorted(house) start, end = 1, house[-1] - house[0] def router_counter(distance): count = 1 cur_house = house[0] for i in..
-
[백준] 2805번 나무 자르기 (파이썬)
2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 코드 import sys if __name__ == '__main__': n, m = map(int, input().split()) li = list(map(int, input().split())) low, high = 0, sys.maxsize while low = 0: num += i-mid if num >= m: low = mid+1 else: high = mid-1 print(high)
-
[백준] 1654번 랜선 자르기 (파이썬)
1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 코드 import sys if __name__ == '__main__': k, n = map(int, input().split()) li = [] for _ in range(k): li.append(int(input())) low, high = 0, sys.maxsize while low = n: low = mid +1 else: high = mid -1 print(high)