두부의 코딩일기

https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net ✅실버 Ⅳ 🔶 풀이 굴다리 길이(N)와 가로등 개수(M), 가로등 설치 위치가 주어지고, 굴다리의 모든 곳을 비추어라. 가로등 높이가 1 증가할 때마다 길이 1만큼 더 주위를 비출 수 있다. 이분 탐색을 이용해서 가로등의 적정 높이를 찾아주면 된다. 가로등의 높이를 기준으로 굴다리의 모든 곳을 비출 수 있는지 확인하면서 가능하다면 최댓값(right)를 mid-1로, 불가능하다면 최솟값(left)를 m..

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로만 풀 수 없고, 이진 탐색을 이용해야한다. 1. 입력하는 과정에서 min, max 값을 선언해주고, 다리는 양방향이므로 arrList에 두 번씩 입력해준다. for (int i=0; i

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 풀이 이번 문제는 랜선 자르기, 숫자 카드 등과 같은 이분 탐색 알고리즘 문제이다. 이분 탐색에 대해서 잘 모르거나 이해가 가지 않는다면 위 문제를 먼저 풀어보는 걸 추천한다. 이 문제의 목표는 N개의 집이 주어졌을 때 C개의 공유기를 집 간격을 최대한 띄워서 설치하는 것이다. 그렇다면 이분 탐색을 어떻게 적용시켜야할까? 이분 탐색에서 중요한 건..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색을 이용해서 풀어야하는 문제이다. 잘 모르겠다면 아래의 포스팅을 먼저 보고 오는 걸 추천한다. https://sookr5416.tistory.com/146 자바 이분 탐색 Arrays.binarySearch() 메서드 정의 및 사용 방법 알고리즘 문제를 풀다보면 이분 탐색을 이용한 문제를 많이 접할 수 있습니다. 이분 탐색이란 오름차순으로 정렬된 배열에서..