분류 전체보기

# 2017481620 # 정렬 사용. # 좌표 압축 -> 주어진 x들의 값을 오름차순으로 정렬했을때의 인덱스값. # 같은 숫자가 있을 수 있으니 셋으로 정리 n = int(input()) numbers = list(map(int, input().split())) sort_nums = sorted(set(numbers)) dict = {sort_nums[i] : i for i in range(len(sort_nums))} # key : numbers의 각 값, value : 오름차순 정렬시 각 값의 인덱스 for j in range(len(numbers)): numbers[j] = dict[numbers[j]] print(' '.join(map(str, numbers))) https://www.acmic..

# 이분탐색. m만큼 자르는데 필요한 높이를 이분탐색으로 찾기 # 필요한 높이의 최소값은 1 최대값은 제일 높은 나무의 높이 # 나무의 높이가 중간값보다 크다면 값을 빼주고 총합을 구함. # 총합이 m과 같다면 중간값이 결과값. n, m = map(int, input().split()) trees = sorted(list(map(int, input().split()))) start, end = 1, max(trees) # 나무 높이를 이진 탐색하기 위해 정한 범위 while start = mid: # 나무 높이가 벌목 높이보다 높다면 temp += i - mid # 잘라낸 길이만큼 temp에 더함 if temp >= m: #잘라낸 길이가 m보다 크다 = 벌목 높이를 높여야함 start = mid + 1 ..

# 총 시간의 최소값을 구해야함 # 2번이 필요한 시간 = 1번 시간 + 2번 시간. 3번은 1번 + 2번 + 3번 ... # 오름차순으로 정렬 후 0번부터 현재값까지의 합을 결과값에 더해줌 n = int(input()) times = sorted(list(map(int, input().split()))) result = 0 for i in range(len(times)): result += sum(times[0:i+1]) print(result) 정렬을 활용하는 간단한 문제! 더해줘야하는 값은 sum과 슬라이싱을 사용해주었다. https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 ..

1. 이분 탐색(Binary Search) 정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 방법. 탐색 범위를 절반씩 줄여나가면서 탐색 범위가 1이 될때까지 진행한다. 시간 복잡도는 O(log n). 이진 탐색이라고도 한다. 이분 탐색 예시 코드 # 백준 2110번 : 공유기 설치 n, m = map(int, input().split()) trees = sorted(list(map(int, input().split()))) # 오름차순으로 정렬(필수) start, end = 1, max(trees) # 시작 위치와 끝 위치 지정 while start = mid: temp += i - mid if temp >= m: start = mid + 1 else: end = mid - 1 print(end) 예를 들..

from heapq import * n = int(input()) heap = [int(input()) for _ in range(n)] # 요소들 힙에 추가 heapify(heap) result = 0 while len(heap) > 1: # 힙에 더이상 더할 요소가 남지 않을때까지 x = heappop(heap) # 첫번째 작은 값 y = heappop(heap) # 두번째 작은 값 heappush(heap, x + y) # x + y 의 합을 다시 힙에 추가 result += x + y print(result) 문제 그대로 코드를 썼다. 최소값 순으로 두 값을 더하고 그 합을 남은 값과 다시 더하는 방식으로 구현했다. 힙에 더이상 더할 값이 없을때까지 반복문을 돌리게 하고 첫번째로 작은 값과 두번째..

# 절댓값 힙. 처음의 값을 기억해야하지만 정렬은 절댓값으로 해야함. from heapq import * import sys n = int(input()) # 입력 횟수 x_ls = [int(sys.stdin.readline()) for _ in range(n)] # 연산 리스트 heap = [] for x in x_ls: if x == 0: # x가 0이면 = 출력해야함 if len(heap) == 0: # 힙에 아무것도 없으면 0 출력 print(0) else:# 힙의 길이가 1개 이상이면 절댓값이 가장 작은 값을 출력한다 _, x = heappop(heap) print(x) else: # x가 0이 아닐때는 힙에 x의 절댓값과 x를 넣어줌 heappush(heap, (abs(x), x)) 생각보다 ..

from heapq import * n, m = map(int, input().split()) cards = [] # 카드를 넣어줄 힙 for num in list(map(int, input().split())): # 숫자들을 힙에 넣어줌 heappush(cards, num) for i in range(m): # m만큼 카드 합체하기 x = heappop(cards) # 1번째 작은 값 y = heappop(cards) # 2번째 작은 값 heappush(cards, x + y) # 기존의 카드가 빠지고 합이 추가됨 *2 heappush(cards, x + y) print(sum(cards)) # 카드의 총합을 출력 입력되는 카드들에 특정한 연산을 하고 만들 수 있는 가장 작은 점수를 계산해 리턴하는 문..

from heapq import * n = int(input()) heap = [] for _ in range(n): for i in list(map(int, input().split())): # 리스트를 돌면서 원소를 힙에 넣어줌 if len(heap) < n: # 만약 힙의 요소가 n개 미만이라면 i를 힙에 추가 heappush(heap, i) else: # 힙의 요소가 n개 이상일때 if heap[0] < i: # 만약 최소값이 i보다 작다면 heappop(heap) # 현재 힙의 최소값을 제거 heappush(heap, i) # 현재 요소를 힙에 추가 print(heap[0]) 처음에는 최대 힙을 구하고 n번째가 될때까지 pop을 반복하는 코드를 짰었다. 하지만 결과는.....^^ 입력값이 n^2..

# 한번 입었던 조합은 안됨 = 중복 안됨 # 의상의 분류와 의상들이 주어졌을때 중복 없이 만들 수 있는 조합의 수 # 옷의 종류별로 분류. 각 종류에 대해 (해당 종류의 옷 개수 + 안입는 경우(1))을 종류만큼 곱해주고 아무것도 안입는 알몸인 경우 1가지를 빼준다 import sys case = int(input()) for _ in range(case): # 케이스만큼 반복 n = int(input()) # 의상 수 clothes = {} for _ in range(n): name, type = sys.stdin.readline().rstrip().split() if type in clothes: # 의상의 종류별 총 개수를 딕셔너리에 저장 clothes[type] += 1 else: clothes..

1. 힙 (Heap) 정해진 우선 순위에 따라 원소를 O(log n)에 추가 / 삭제가 가능한 자료구조. 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조이다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있어서, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 파이썬에서는 heapq 라이브러리를 사용해 구현할 수 있다. 파이썬의 heapq 라이브러리는 최소값을 우선 순위로 하는 힙을 제공한다. 기본 연산 push : 힙에 새로운 원소 추가 pop : 힙에서 가장 우선 순위가 빠른 원소를 추출하고 그 값을 반환 heapq 라이브러리 heapify : 리스트를 최소 힙으로 변환 heappush : 힙에 원소 추가 ..