몽상실현개발주의

[BOJ] 10816 / 숫자 카드 2 / Python 파이썬 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 [BOJ] 10815 / 숫자 카드 문제의 응용 문제이다. 처음 시도로는 해당하는 카드의 index 를 이분탐색을 진행하여 찾고, 그 index 를 기준으로 앞뒤를 탐색하는 방법을 구상하였지만 시간초과가 되어버렸다. 그 다음으로는 index 를 시작 숫자로 하여 다시 이분탐색을 하는 방법을 사용 ..

[BOJ] 10815 / 숫자 카드 / Python 파이썬 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 주어진 숫자만큼 이분탐색을 연속으로 하는 문제이다. for 문 안에서 이분탐색을 진행하여 간단하게 풀었다. N = int(input()) cards = list(map(int, input().split())) cards.sort() M = int(input()) nums = list(map(int, in..

[BOJ] 2110 / 공유기 설치 / Python 파이썬 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 풀이 풀이 방법을 떠올리기가 힘들었던 이진탐색 문제였다. "공유기 사이의 거리를 최대로 하는 설치 간격" 을 찾는 문제인데 이 조건을 "집 사이의 간격이 X 이상이 가능한 집의 수 == 공유기 대수" 로 다시 생각하여야 풀 수 있었다. 집 사이의 간격을 이진탐색으로 찾기 간격을 주어진 집..

[BOJ] 2805 / 나무 자르기 / Python 파이썬 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이진탐색의 기본 문제이다. 주어진 나무의 높이들을 빼주면서 결과를 비교하여, 탐색 범위를 좁혀 주는 방식으로 이진탐색을 하였다. res = M : 자를 높이 증가 N, M = map(int, input().split()) trees = list(map(int,..

[BOJ] 1654 / 랜선 자르기 / Python 파이썬 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색의 기본 문제이다. 첫 시도는 완전 탐색으로 접근하였지만 당연히 시간초과가 발생 하였다. 가장 기본적인 이분 탐색의 구조로 해결 하였다. import sys input = sys.stdin.readline K, N = map(int, input().split()) lines = [] for _ i..

[BOJ] 1967 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 전날 풀었던 [BOJ] 1167 / 트리의 지름 / Python 파이썬 문제와 같이 Tree 의 지름을 구하는 문제이다. 다시 복습하자면, Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx..

[BOJ] 1167 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 Tree 의 지름을 구하는 문제이다. 문제를 선형시간안에 풀기위해서는 Tree 의 지름과 구하는 알고리즘에 대한 사전 지식이 필요하였다. Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx를 잡..

[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 node의 root를 찾는 문제이다. 최상단의 root 노드가 항상 1로 시작하기 때문에, 모든 edge 를 기록한뒤 1부터 Tree 를 내려가며 root 를 기록하였다. from collections import deque N = int(input()) graph = [[] for _ in range(N+1)] for _ in range(N-1): f, t = map(int, inpu..