https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 처음 딱 읽었을 때 풀이방법이 떠오르지 않았다. 왜 스택 생각이 안났을까.. 알고리즘 분류를 먼저 보고 풀었다면 고민도 안하고 풀 문제였어서 아쉬웠다.. 풀이방법은 간단하다. 기타의 각 줄마다 스택을 만들어 놓고 새로 누를 줄이 스택의 상단보다 작으면 pop을 해나가는 식으로 체크를 하면 된다. 이미 누르고 있는 프렛이 입력으로 또 주어질 수 있다는 점만 주..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 여러 책 이름들을 입력받는데 이 중 가장 많이 중복된 책의 이름을 출력하면 되는 문제이다. 중복되는 요소의 count -> C++에서는 map, 파이썬에서는 dictionary를 이용하면 된다. 여기서 한 가지 더 생각해야 하는 것은 count가 같은 책 이름들이 있을 때, 사전순으로 나열해 가장 앞에 오는 순서의 책 이름을 출력해 주어야 하는 것인데, 결국 map, 또는 dic을 써서 카..

- 최소 힙(min-heap)의 구조 - 삽입/삭제: O(logN) import heapq로 사용 가능 push: heapq.heappush(hq, item) pop: heapq.heappop(hq) import heapq pq = [] heapq.heappush(pq, 6) heapq.heappush(pq, 12) heapq.heappop(pq) heapify - 리스트 x를 heap으로 변환 x = [4, 3, 1, 2, 5, 6] print(x) # [4, 3, 1, 2, 5, 6] heapq.heapify(x) print(x) # [1, 2, 4, 3, 5, 6] heapq를 사용하는 이유? from queue import PriorityQueue로 일반 우선순위 큐도 사용할 수 있다. 하지만 이..