[Python] 백준 알고리즘 1260번 : DFS와 BFS
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 👩💻문제 이해 DFS와 BFS의 결과를 각각 반환하는 것이다. 두 접점의 번호가 주어졌을 때, graph가 어떻게 생겼는지 파악을 하는 것이 문제 풀이의 핵심이다. 👩💻 스택과 큐를 이용한 DFS, BFS 알고리즘 구현 : 성공🌈 🎯전체 코드 n,m,v = map(int,input().split()) graph = [[0]*(n+1) for _ in ran..
[Python] 백준 알고리즘 15903번 : 카드 합체 놀이
https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 👩💻문제 이해 합이 최소가 되도록 해야하기 떄문에 heappop 두 번으로 가장 작은 숫자를 가진 card 두장을 뽑은 후, 두 장을 더한 값을 다시 heappush로 넣어주면 된다. 👩💻heappop, heappush, heapify를 사용한 코드 : 성공🌈 # 15903번 : 카드 합체 놀이 from heapq import heappop, heappus..
[Python] ⭐️백준 알고리즘 1655번 : 가운데를 말해요
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 👩💻문제 이해 👩💻leftheap 과 rightheap의 크기가 같아질 때 중간값 반환 : 성공🌈 import heapq n = int(input()) leftHeap = [] rightHeap = [] for i in range(n): num = int(input()) if len(leftHeap) == len(rightHeap): heapq.heappush(leftHeap,..
[Python] 백준 알고리즘 2075번 : N번째 큰 수
https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 👩💻문제 이해 힙 구조를 이용해 N x N 개의 숫자 중 N번 째 큰 수를 찾는 문제 숫자 자체를 찾는 것은 어렵지 않지만, 시간과 메모리를 고려하기 위해 힙 구조를 잘 활용해야 한다. 메모리 제한이 12mb이므로 입력값을 모두 저장해서 사용할 수 없다. 👩💻heapq 모듈을 사용해 절댓값 힙 구현 : 메모리 초과☠️ from heapq import heappop, heappush n = int(in..
[Python] 백준 알고리즘 11286번 : 절댓값 힙
https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 👩💻heapq 모듈을 사용해 절댓값 힙 구현 : 성공🌈 from heapq import heappop, heappush import sys n = int(input()) heap = [] for i in range(n): num = int(sys.stdin.readline()) if num != 0: heappush(heap,(abs(num), num)) else: try:..
[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..