본문 바로가기

이분탐색3

BOJ S2 2805 나무 자르기 JAVA 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 읽기 이 문제는 일단 입력 값이 너무 컸기 때문에 바로 이분 탐색을 써야 겠다고 생각이 들었다. 입력 값을 한번 보자. 나무의 수 N : 1~1,000,000(백만) 필요한 나무 길이 M : 1 ~ 2,000,000,000(이십억) 나무의 높이 : 0~1,000,000,000(십억) 만약 완전 나이브하게 풀이한다면, 나무를 자를 높이를 0에서부터 십억까지 1씩 증가시키면서, N개의 나무를 다 잘라보고, 총합이 필요한 .. 2024. 3. 20.
BOJ P5 3197 백조의 호수 BFS+이분탐색 JAVA 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 읽기 처음에 문제를 읽었을 때는 일반적인 시뮬레이션 문제 같았다. 단순하게 생각하면 다음과 같은 구조로 풀이를 할 수 있을 것이다. 모든 판을 순회하며 물과 인접한 얼음에 없앤다는 표식을 남긴다 다시 모든 판을 순회하며 표식이 있는 얼음을 녹여 물로 만든다 위 과정이 끝났으면 백조 한 마리의 위치에서 BFS를 수행하여, 물로만 이동했을 때 다른 백조까지 도달하는 지 파악한다 두 백조가 만났다면 끝내고, 만나지 않았지만 1-3 과.. 2024. 1. 12.
BOJ G2 1655 가운데를 말해요 JAVA 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 읽기 맨 처음에 문제를 읽자마자 트리 형태가 먼저 생각났다. 하나씩 숫자를 넣으면서 중간 값을 찾아낼 수 있지 않을까 하는 생각. 하지만 자료구조를 본 게 시간이 좀 지나서 어떤 식으로 구현해야 할 지는 감이 잘 잡히지 않았다. 그 다음 생각난 접근은 정렬이다. 하나씩 값이 들어오고, 값이 몇 개 들어왔는지 알 수 있고.. 그렇다면 삽입 정렬을 하면 되지 않을까 싶었다. 하지만 삽입 정렬의 시간복잡도는 최악의 경우 N^2이기 때문에(문제에서.. 2024. 1. 11.

티스토리툴바