자료구조&알고리즘

위 문제의 핵심을 절대값을 인덱스로 가지며 기존의 값을 가지고 있어야 한다는 점입니다. 문제  코드import sys, heapq as hqinput = sys.stdin.readlinen = int(input())ls = []for _ in range(n): num = int(input()) if num == 0: print(hq.heappop(ls)[1] if ls else 0) else: hq.heappush(ls, (abs(num), num))  설명heapq 모듈을 import 합니다절대값을 구해야 하기 때문에 튜플의 형태로 넣습니다그렇게 되면 기존의 값 (절댓값, 실제값)의 형태로 힙에 저장되게 됩니다 그 뒤 절대 값을 기준으로 정렬된 힙에 실제 값을 ..

https://www.acmicpc.net/problem/12015예전에 가장 긴 증가하는 부분 수열 문제를 풀었었는데 이번에는 다른 점이 메모리 부분이 다문제 코드import sysinput = sys.stdin.readlinen = int(input())cases = list(map(int, input().split()))lis = [0]for case in cases: if lis[-1]   설명이진 탐색을 사용하여 효율적으로 위치를 찾는게 목표입니다수열의 각 원소 case에 대해 lis 리스트에서 적절한 위치를 찾아 삽입하거나 대체하는 코드 입니다 큰 값은 단순 추가: 현재 수열의 값이 lis의 마지막 값보다 크면 lis에 그대로 추가합니다.작거나 같은 값은 대체: 그렇지 않으면 이진 탐색을..

배경https://www.acmicpc.net/problem/10816   코드import sysinput = sys.stdin.readlineN = int(input())cards = sorted([*map(int, input().split())])M = int(input())candidate = [*map(int, input().split())]count = dict()for card in cards: if count.get(card, False): count[card] += 1 else: count[card] = 1def binarySearch(arr, target, start, end): if start > end: return 0 ..

배경https://www.acmicpc.net/problem/13305   코드import sysinput = sys.stdin.readlinen = int(input())dist = list(map(int, input().split()))price = list(map(int, input().split()))result = 0maxx = price[0]for i in range(n-1): if price[i]   설명방법만 알면 어렵지 않은 문제이다.가장 값이 적은 주유소를 추적하면서 거리를 곱해주면 된다for문을 돌면서 새로운 주유소가 이 전 주유소 보다 값이 큰 지 확인한다.아니라면 그 전 주유소에서 다음으로 이동 하는데 필요한 기름을 넣어 주면 된다.  배운 점예전 소마 테스트에서 비슷한 문제..

배경https://www.acmicpc.net/problem/1541  코드import sysinput = sys.stdin.readlineminus = 0string = input().rstrip()list_to_split_minus = string.split('-')ls = []for list in list_to_split_minus: list_to_split_plus = map(int, list.split('+')) ssum = sum(list_to_split_plus) ls.append(ssum)result = ls[0]for i in range(1, len(ls)): result -= ls[i]print(result)  설명괄호를 잃어버렸다니 저런첫 번째 예시에서 힌트를 얻..

배경https://www.acmicpc.net/problem/11399  코드import sysinput = sys.stdin.readlinen = int(input())peoples = list(map(int, input().split()))peoples.sort()result = 0now_time = 0for people in peoples: result += people + now_time now_time += peopleprint(result)  설명앞선 회의실 문제와 비슷하지만 더 쉬운 문제이다현재 시간은 계속 가니까 더 빨리 인출 할 수 있는 사람을 기준으로 정렬시킨다.그리고 총 걸린 시간에 현재 시간을 더해준다  배운 점

배경https://www.acmicpc.net/problem/1931   코드import sysinput = sys.stdin.readlinen = int(input())meeting = []for i in range(n): start, end = map(int, input().split()) meeting.append((start, end))meeting.sort(key=lambda x: (x[1], x[0]))time = 0cnt = 0for start, end in meeting: if start >= time: cnt += 1 time = endprint(cnt)  설명시작과 끝나는 시간을 리스트에 담아준다. 문제를 풀기 위해서 필요한 값은 언제 끝나냐이다..

배경https://www.acmicpc.net/problem/11047    코드import sysinput = sys.stdin.readlinen, k = map(int, input().split())coins = list()for _ in range(n): coins.append(int(input()))coins.sort(reverse=True)result = 0for coin in coins: if k >= coin: result += k // coin k %= coin if k   설명대표적인 그리디 문제이다. 그리디 문제란그리디 알고리즘(탐욕 알고리즘)은 문제를 해결할 때 각 단계에서 최적이라고 생각되는 선택을 하는 방식입니다. 즉, 현재 단계에서..