코딩성장스토리

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이 문제는 이분탐색과 bfs를 쓰면서 풀었다. 이 문제를 보고 처음 든 생각은 시간복잡도 이다. BFS와 이분탐색이 합쳐져 있기 떄문이다. BFS 시간 복잡도는 O(N) 이고 이분탐색은 O(logn) 즉 합쳐서 O(nlogn)이다. 일단 가중치(무게)를 1부터 최대값을 범위를 지정하고 무게에 따라 이분탐색을 실시했다. 섬이 연결되어 있는 ..

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 이 문제는 처음에 볼 때 이분탐색으로 푸는 것임을 알고 있음에도 고민을 많이 하였고 이분탐색이라도 기준을 어떻게 잡아야할지 감이 안잡혔다. 그래서 살짝힌트를 보았고 바로 알아차렸다. 일단 우리는 거리의 최대값을 구하는 것이므로 거리를 기준으로 이분탐색을 하면된다. 그리고 그 거리에 따라서 공유기가 최대 몇개 들어갈 수 있는 지 구하고 거리에 따른..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 이분 탐색으로 푸는 것이다. 일단 톱날의 높이가 낮아지면 가져가는 나무의 길이는 증가하고 톱날의 높이가 높아지면 가져가는 나무의 길이는 줄어든다. 그리고 우리는 가져가는 나무의 길이의 총량이 중요하므로 톱날로 잘랐을때 나오는 나무랑 가져가야하는 나무의 길이를 비교하면서 이분 탐색을 실시하면 된다. 코드를 보자 #include #include usi..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이 문제는 랜선의 길이를 구해야한다. 랜선의 길이 최댓 값을 구하기 위해 이분 탐색을 이융했다.순차 탐색을 하기에는 시간 초과가 나와 더 효율적인 이분탐색을 썻다. 랜선의 길이는 당연히 정렬 되어 있기에 이분탐색을 쓸 수 있고 랜선의 길이가 크면 랜선갯수는 적게 나오고 작으면 더 많이 나온다. 즉 n보다 크거나 같다라는 조건을 만족하면 left값을 mid+1로 지정하고..