Algorithm/BOJ172 [BOJ]15810번: 풍선 공장 문제: https://www.acmicpc.net/problem/15810 이분 탐색으로 푸는 결정 문제입니다. Q. 임의의 K시간 동안 M개 이상의 풍선을 만들 수 있는가? 위 조건을 만족하는 K의 최소값을 구하는 문제입니다. 이분 탐색의 하한값은 0, 상한값은 (풍선의 갯수 x 가장 빨리 만드는 스태프의 시간) 입니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ15810.java 2022. 3. 3. [BOJ]2343번: 기타 레슨 문제: https://www.acmicpc.net/problem/2343 이분 탐색을 활용한 결정 문제입니다. Q. "하나의 블루레이 크기를 K로 했을 때 M개 이하를 사용해서 모든 강의를 녹화할 수 있는가?" 위 조건을 만족하는 K의 최소값을 찾는 문제입니다. 한 가지 함정이 있는데요. 블루레이 크기의 상한(maximum)과 하한(minimum)을 결정할 때 하한의 값은 max(각 강의의 길이)여야 합니다. 그 이유는 max(각 강의의 길이)보다 블루레이 크기가 작을 경우 블루레이에 최대 길이의 강의는 담을 수 없기 때문입니다. 이 부분만 유의해서 구현하시면 됩니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2343.java 2022. 3. 2. [BOJ]2512번: 예산 문제: https://www.acmicpc.net/problem/2512 이분 탐색을 활용한 결정 문제입니다. Q: "정수 상한액을 K로 했을 때 총 예산 금액안에서 모든 지방에 예산 분배가 가능한가?" 위 질문을 만족하는 K의 최댓값을 구하는 문제로 해결하면 됩니다. K의 범위는 다음과 같습니다. 0 2022. 3. 2. [BOJ]4195번: 친구 네트워크 문제: https://www.acmicpc.net/problem/4195 유니온, 파인드 문제입니다. 주어지는 친구 관계가 최대 10만이고, 한 번 친구 관계를 조회할 때 최대 10만개까지 노드를 탐색할 수 있습니다. (BFS, DFS 기준) 그러므로 O(10만^2) 으로 시간초과가 납니다. 그래서 노드 탐색 시간을 log시간으로 줄여야 시간 초과를 해결할 수 있습니다. 노드 탐색 시간을 log 시간으로 내리는 방법은 친구 관계가 주어질 때 마다 유니온, 파인드를 사용하여 컴포넌트 간에 연결 관계를 맺어줍니다. 새로운 관계를 맺는다면 친구 관계는 component1 + component2의 합이 될 것이고 이미 맺어진 관계(같은 컴포넌트에 속함)라면 component1 이나 component2 중 하나의.. 2022. 3. 2. 이전 1 ··· 7 8 9 10 11 12 13 ··· 43 다음
