[Python] 백준 알고리즘 11279번 : 최대 힙
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 👩💻문제 이해 힙 자료구조를 이용해 최대 힙을 구현한다. 파이썬 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 heappush를 할 때 그냥 num이 아닌 (-num, num)으로 구성된 튜플을 이용하게 되면, 튜플의 첫 번째 원소인 -num이 우선순위로 힙이 구성되므로 최대 힙을 구현할 수 있다. 👩💻heapq 모듈을 사용해 최대 힙 구현 : 성공🌈 from heap..
[Python] 백준 알고리즘 1927번 : 최소 힙
https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 👩💻문제 이해 힙 자료구조를 이용해 문제를 푼다. 👩💻heapq 모듈을 사용한 코드 : 성공🌈 import heapq import sys n = int(input()) heap = [] for i in range(n): num = int(sys.stdin.readline()) if num != 0: heapq.heappush(heap, num) else: try: print..
[Python] 백준 알고리즘 1966번 : 프린터 큐
https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 👩💻문제 이해 FISRT IN FIRST OUT 구조이므로 큐를 활용해 문제를 푼다. 👩💻deque 모듈을 사용한 코드 : 성공🌈 test_case = int(input()) for i in range(test_case): n,m = list(map(int, input().split( ))) imp = list(map(int, input().split( ))) idx = list(range(len..
[Python] 백준 알고리즘 10866번 : 덱
https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 👩💻deque 모듈을 사용한 코드 : 성공🌈 import sys from collections import deque input = sys.stdin.readline N = int(input()) queue = deque([]) for i in range(N): command = input().split() if command[0] == "push_front": queue.app..
[Python] 백준 알고리즘 10773번 : 제로
https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 👩💻문제 이해 0이 입력될 경우 가장 마지막에 들어온 숫자가 빠지게 되므로 Last In First Out 구조의 스택(stack)을 이용해 문제를 푼다. 👩💻stack 구조를 이용한 코드 : 성공🌈 import sys k = int(input()) li = [] for i in range(k): num = int(sys.stdin.readline()) if ..
[자료구조] 스택(Stack), 큐(Queue), 덱(Deque)
🌵스택(Stack) 구조란? 스택(Stack)은 ‘쌓다’라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 즉, 데이터가 들어온 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 나오게되는 구조이다. LIFO (Last In First Out) 🌵특징 및 장단점 스택(Stack)은 정해진 방향으로만 쌓을 수 있으며, 새로 삽입된 자료는 stack.push를 사용해 스택의 top에 쌓일 수 있다. 삭제 연산은 stack.pop을 통해 이루어지며, top위치의 자료가 삭제된다. top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 장점 top 을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다. 단점 top 위치 이외의 데이터에 접근할 수..