전체 글

Queue API Queue 자료구조는 Stack과 정반대의 특성을 지닙니다. 대표적으로 FIFO, 들어온 순서대로 나가는 특성을 지니고 있죠. Queue: linked-list representation 파이썬에서는 포인터라는 개념이 없기 때문에 더욱 어색하지만 개념은 간단한 것 같습니다. 아이템을 추가할 때는 맨 앞에, 제거할 때는 맨 뒤에서 하다보니 가리키는 주소값이 두 군데여야 한다는 것입니다. Queue dequeue: linked-list implementation Queue: linked-list implementation in Java 굳이 파이썬으로 이런 코드를 짤 필요는 없는 것 같습니다.. 단순히 deque를 불러와서 추가할 줄만 알면 충분합니다. 참고로 popleft를 쓰면 배열의 ..

Stack : resizing-array implementation array의 크기를 재조정하는 것은 아주아주 비효율적인 방식입니다. 왜냐하면 크기를 재조정할 때마다 배열의 모든 아이템을 복사해야 하기 때문이죠. 이러한 경우 N개의 아이템을 삽입할 때, 총 연산 횟수는 (N^2) / 2이기 때문에 N이 충분히 클 때는 활용 불가능한 방식입니다. 따라서 배열의 크기를 매번 재조정하는 것이 아니라, 배열이 꽉 찼을 때만 이를 두 배로 늘리는 방식을 사용합니다. 이때는 N개의 아이템을 삽입할 때 N만큼의 시간이 걸립니다. Stack : amortized cost of adding to a stack Stack : resizing-array implementation 배열의 크기를 줄일 때도, 그 작업을 매번..

Stacks and queues Stack : 가장 최근(마지막)에 추가된 아이템을 확인하는 자료구조 Queue : 가장 처음에 추가된 아이템을 확인하는 자료구조 Client, implementation, interface Stack API Stack과 관련된 아주 기본적인 method입니다. stack에 아이템을 추가하는 push, 마지막 아이템을 제거하며 반환하는 pop, stack이 비었는지 확인하는 isEmpty 등이 있습니다. 물론 Java 기준이기 때문에 Python과 약간의 차이는 있지만 LIFO 구조 자체는 동일합니다. Stack test client 아주 간단한 stack 예제 입니다. 문자열이 '-'과 동일할 땐 pop하며 출력, 그렇지 않을 땐 stack에 추가합니다. 따라서 예시는 ..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 소스 코드 import sys def main(): N,C = map(int, input().split()) house = [] for _ in range(N): house.append(int(sys.stdin.readline().strip())) house.sort() answer = 0 left, right = 1, house[-1..

문제 링크 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 소스 코드 import sys sys.setrecursionlimit(10**6) def main(): n, m = map(int, sys.stdin.readline().strip().split()) parents = [x for x in range(n)] # 부모 노드 리스트 def root(x): if x != parents[x]: # 자기 자신이 될 때까지 재귀 parents..

문제 링크 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 소스 코드 import sys def main(): n = int(input()) nums = sorted(list(map(int, sys.stdin.readline().strip().split()))) m = int(input()) low, high = 0, max(nums) # 최소, 최대 answer = 0 # 최종 정답 저장 while low