파라메트릭 서치 (5) 썸네일형 리스트형 인터넷 설치 (1800번) - 백준 (BOJ) https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 백준 - 인터넷 설치 (1800번) 난이도 : Gold 1 알고리즘&자료구조 : Priority Queue (우선순위 큐) / Dijkstra (다익스트라) / 정렬 (Sorting) 시간복잡도 (Time Complexity) : O( (N)log(P) * log(max(L)) ) ▷ 아이디어 떠올리기가 상당히 어려운 문제였다. ★ 핵심 Idea ★ ◎ 다.. 통나무 자르기 (1114번) - 백준 (BOJ) https://www.acmicpc.net/problem/1114 1114번: 통나무 자르기 첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출 www.acmicpc.net 백준 - 통나무 자르기 (1114번) 난이도 : Gold 1 알고리즘&자료구조 : Parametric Search (파라메트릭 서치) & Sorting (정렬) 시간복잡도(Time Complexity) : O( K * logK ) 파라메트릭 서치를 적절히 활용해서 풀 수 있는 문제이다. class Log(): def __init__(self, L, K, C): acc = s.. 놀이 공원 (1561번) - 백준 (BOJ) https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 백준 - 놀이 공원 (LUNA) (1561번) 난이도 : Gold 2 알고리즘&자료구조 : Parametric Search (파라메트릭 서치) & Binary Search (이진 탐색) 시간복잡도(Time Complexity) : O( M * logN ) class Luna(): def __init__(self, N, M, arr): if N.. 기타 레슨 (2343번) - 백준 (BOJ) https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 백준 - 기타 레슨 (2343번) 난이도 : Silver 1 알고리즘&자료구조 : Parametric Search, Binary Search (이진 탐색) import sys input = sys.stdin.readline if __name__ == '__main__': N, M = map(int, input().split()) size = list(map(int, input().split())) s, .. K번째 수 (1300번) - 백준 (BOJ) https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 백준 - K번째 수 (1300번) 난이도 : Gold 2 알고리즘 : Parametric Search (Binary Search) Time Complexity : O( N * log(N) ) if __name__ == '__main__': N, k = int(input()), int(input()) s, e = 1, N*N while s >1 cnt = sum(min.. 이전 1 다음