Python

1. 아나콘다 설치 https://www.anaconda.com/download Download Anaconda Distribution | AnacondaDownload Anaconda's open-source Distribution today. Discover the easiest way to perform Python/R data science and machine learning on a single machine.www.anaconda.com  먼저 위 설치 사이트에 진입해준다.  그러면 이런 화면이 나오는데, 이메일을 무조건 입력하지 않아도 submit 버튼 아래 작게 skip registration 버튼이 존재하므로 이를 누르면 바로 설치 페이지로 이동 가능하다.  각자 운영체제에 맞는 버전을..

자료구조와 우선순위 큐를 사용하면 풀 수 있는 문제였다. 풀면서 설명이 잘 이해가 안되어서 제일 헷갈렸던 점이 있는데, 바로 예시 입출력에서 볼 수 있는 2 3 2 부분이다.2 3 2가 모두 선물 3개라고 이해하면 위 예제의 출력이 모순적인데, 맨 앞의 숫자 2가 충전할 선물의 개수이고 바로 뒤에 따라오는 나머지 숫자들의 나열이 선물의 개수만큼 가치가 입력되어 진 것이다. 즉 2(개) 3(선물1의 가치) 2(선물2의 가치) 이런 셈이라고 이해하면 쉽다! import sysimport heapqN = int(input())heap = [] for _ in range(N): data = list(map(int, sys.stdin.readline().split())) if data[0] == 0: ..

이번 문제는 앞서 풀었던 최대힙, 최소힙과 유사한 문제이지만 추가로 절댓값이 조건으로 추가된 문제이다. import sysimport heapqN = int(input())heap = [] # 비어있는 배열에서 시작for _ in range(N): calc = list(map(int, sys.stdin.readline().split())) for num in calc: if num == 0: if heap: print(heapq.heappop(heap)[1]) else: print(0) else: heapq.heappush(heap, (abs(num), num)) heappush로 숫자를 삽입할 때 튜플을 이용하는 것이 포인트였다..

저번에 파이썬의 heapq 라이브러리를 사용하여 최소 힙을 구현해보았었는데, 이번 문제와 같이 최대 힙의 경우에는 heapq 가 최대 힙 구현 기능을 제공하지 않는다는 특징이 있다. 참고로 heapq 의 heappush(heap, item) 메소드는 힙 불변성을 유지하면서 item 값을 heap으로 삽입해주고, heappop(heap) 메소드는 힙 불변성을 유지하면서 heap에서 가장 작은 항목들을 pop하고 반환해주는 메소드였다. 그러나 최대힙의 경우 이를 적절히 변형해서 구현할 수 있는데, 부호를 변경하는 방법을 사용해서 구현할 수 있다! import heapqheap = []values = [1, 5, 4, 2, 3]for v in values: heapq.heappush(heap, -v) #..

앞 전 문제와 유사한 최소힙 문제이다.역시나 파이썬이기 때문에 heapq 라이브러리를 사용해주면 간단하게 해결할 수 있다. import sysimport heapqN = int(input())heap = [] # 최소 힙for _ in range(N): calc = list(map(int, sys.stdin.readline().split())) for num in calc: if num == 0: if heap: print(heapq.heappop(heap)) else: print(0) else: heapq.heappush(heap, num) 조건에서 시간 제한이 눈에 띄길래 입력 문자열을 input() 대신 ..

이 문제의 핵심은 최소힙을 사용하는 것이었다. 사실 처음엔 배열이나 스택을 활용하려고 했었는데 너무 모르겠어서 구글링 해보니 다들 최소힙으로 푸셨음..ㅎ즉 최소힙의 특성을 기반으로 상위 N개의 큰 숫자만 유지하는 방식을 구현해야 하는 문제였다. 최소힙의 개념부터 복습해보자면,최소 힙은 root node가 항상 가장 작은 값을 가지는 이진 트리이다.파이썬에는 이를 효율적으로 구현할 수 있는 자료구조로 heapq 라이브러리가 이미 존재하는데, 노드 삽입을 위한 heappush와 제거를 위한 heappop 메소드(가장 작은 값인 0번째 원소 제거)가 존재하고 각각 O(log k)의 시간 복잡도를 가진다.동작 방식은 힙에 새로운 숫자를 삽입할 때 내부적으로 힙 구조를 유지하도록 자동으로 정렬이 되는데, 가장 작..