DonHurry

📖 문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 🔎 풀이 그리디하게 해결할 수 있는 문제입니다. 새로 만들어진 묶음은 또다른 묶음과 다시 비교를 진행해야합니다. 그러므로 가장 작은 두 묶음을 골라 새로운 묶음을 만들어내는 것이 유리합니다. 파이썬의 heapq를 활용하면 간단하게 구현이 가능합니다. 💻 코드 import sys import heapq input = sys.stdin.readline N = int(input()) heap = [] for _ in range(N): heapq..

📖 문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 🔎 풀이 다익스트라를 활용하는 기본 문제입니다. 다익스트라 구현 시에는 우선순위 큐를 활용하여 가장 적은 비용을 우선적으로 뽑아내도록 해야합니다. 그리디하게 매순간 가장 적은 비용의 경로를 뽑아내고, 처음 방문하는 정점일 경우 따로 저장해줍니다. 💻 코드 import sys import collections import heapq input = sys.stdin.readline V, E = map(int, input..

📖 문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🔎 풀이 DFS와 BFS를 구현해보는 기본 문제입니다. DFS는 스택, BFS는 큐를 활용하여 구현합니다. 💻 코드 import sys import collections input = sys.stdin.readline graph = collections.defaultdict(list) N, M, V = map(int, input().split()) for _ in range(M): a, b = map(int, inp..

📖 문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 🔎 풀이 이분 탐색을 이용하는 가장 기초적인 문제입니다. 다른 아이디어 필요 없이 이분 탐색을 짜는 코드만 알고 있으면 해결이 가능합니다. 아래 코드에서 주목해야할 점은 mid 값을 계산할 때 단순히 (left + right) // 2 로 하지 않았다는 것입니다. 사실 파이썬에서는 문제될 일이 없지만, 다른 언어에서는 left + right의 값이 자료형의 최대 저장값을 넘어갈 경우 오버플로가 발생할 수 ..

📖 문제 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 🔎 풀이 우선순위 큐를 활용하는 간단한 문제입니다. 파이썬 모듈 heapq를 이용하여 풀이합니다. 파이썬은 최소 힙만을 지원하기 때문에, 최대 힙 문제를 풀기 위해서는 작은 아이디어 하나가 필요합니다. 힙에 저장할 때, 입력값의 부호를 바꾸어 넣어주는 방식으로 최대 힙 문제를 해결할 수 있습니다. 💻 코드 import sys import heapq input = sys.stdin.readline N = int(input()) hq ..

📖 문제 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 🔎 풀이 큐를 이용하는 간단한 문제입니다. 파이썬에는 collections라는 모듈이 있습니다. 이중 deque는 이중 연결 리스트로 되어 있어, 양방향 삽입 삭제가 O(1)에 가능합니다. 남은 카드의 숫자가 2개 이상이면, 하나는 버리고 하나는 뽑아서 뒤에 다시 추가해주는 방식으로 코드를 구현합니다. 💻 코드 import collections N = int(input()) num = collections.deque(x for x in range(1, ..

📖 문제 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 🔎 풀이 유니온 파인드를 활용하는 최소 신장 트리 문제입니다. 백준 4386번 별자리 만들기 문제와 비슷합니다. 다른 점은 이미 연결되어 있는 간선이 존재한다는 것입니다. 이미 연결된 통로들은 길이 합에 넣어줄 필요가 없습니다. 따라서 길이를 계산하기 전에, 연결된 통로들의 root를 통합하여 줍니다. root를 통합하기 위해서는 미리 구현한 union 함수를 이용하면 됩니다. 아래 코드에서는 우주신이 1번이 아닌 0번부터 있..

📖 문제 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 🔎 풀이 유니온 파인드를 활용하는 최소 신장 트리 문제입니다. 백준 1197번 최소 스패닝 트리와 비슷합니다. 해당 문제는 노드 사이의 거리가 간접적으로 주어진다는 점이 다릅니다. 별들의 2차원 좌표가 주어지기 때문에, 별들 사이의 거리를 우선적으로 구하면 됩니다. 아래 코드에서는 가장 간단한 유클리디안 거리를 이용했습니다. 💻 코드 import sys input = sys.stdin.readline # root를 찾는 함수 def find_parents..