Beelog

www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제는 위와 같으며 크기가 가장 작은 카드 묶음들을 먼저 합쳤을 때, 비교 횟수가 가장 적다는 점을 이용하여 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin import heapq heap = [] n = int(stdin.readline()) for _ in range(n): bundle = int(stdin.readline()) heapq.h..

www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 문제는 위와 같으며 최소 힙을 구현할 수 있으면 쉽게 풀 수 있는 문제입니다. 또한 파이썬에서는 heapq 라이브러리를 통해 문제를 보다 쉽게 실수 없이 해결할 수 있습니다. 먼저 파이썬에서 heapq 를 사용한 코드를 살펴보면 다음과 같습니다. from sys import stdin import heapq n = int(stdin.readline()) heap = [] for _ in range..

www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제는 위와 같으며, 중위순회를 사용하면 위치가 앞인 노드부터 차례로 방문할 수 있습니다. 이때 해당 노드의 레벨을 키로 하고 노드의 위치를 값으로 하여 각 레벨에 존재하는 노드의 위치를 리스트로 저장합니다. (예: {level: [position, position, ...]. level: [position, ...], ...} ) 그런 다음 각 레벨의 노드 위치 리스트에서 가장 뒤에 있는 노..

www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제는 위에서 확인할 수 있으며 예제로 주어진 압축 문자의 압축을 푸는 방법을 보면 아래와 같습니다. 33(562(71(9))) => 33(562(79)) => 33(567979) => 3567979567979567979 => 결과: 19 처음에는 아주 쉽게 생각해서 순서대로 스택에 저장하다가 ")" 가 들어온 경우 "(" 를 찾을 때까지 앞으로 이동하면서 그 수를 세고 "(" 를 만나면 그 앞에 있는 수..

문제는 위와 같습니다. 저는 문제를 이해하는데 시간이 오래 걸렸는데... 주어진 공유기를 모두 설치하기 위해 떨어져 있어야 하는 집 사이의 최소 거리 중 최대 값을 구하는 것으로 생각하면 좋을 것 같습니다. 위 예제를 바탕으로 살펴보면, 공유기 설치 거리가 최소 2인 경우 1, 4, 8 또는 1, 4, 9 에 설치할 수 있습니다. 마찬가지로 공유기 설치 거리가 최소 3인 경우 1, 4, 8 또는 1, 4, 9 에 설치할 수 있습니다. 하지만, 공유기 설치 거리가 최소 4인 경우는 1, 8 또는 1, 9 아니면 4, 8 또는 4, 9 이렇게 최대 2개까지만 설치할 수 있습니다. 따라서 주어진 공유기를 모두 설치하기 위해서는 공유기 설치 최소 거리가 최대 3이므로 이 값이 출력됩니다. 또한, 최대한 많은 거..