오늘 문제는 코테99에서 여러 번 풀어봤던 이분 탐색 알고리즘 문제인백준 2805번 '나무 자르기'다.https://www.acmicpc.net/problem/2805  이번 문제 해결 아이디어는 아래와 같다.문제 해결 과정배열에 각 나무의 길이를 저장하고 정렬한다.가장 긴 길이를 max로 두고, start = 0 / end = max / mid = (start + end) / 2로 둔다.start 각 길이 - mid의 값을 모두 더한 것을 sum으로 함.sum과 M을 비교했을 때 sum >= M일 경우 result = mid, 그리고 start를 mid + 1로 하여 한 칸 더 오른쪽으로 이동해본다.sum  이렇게 코드를 작성해서 제출해봤더니, 아래와 같은 문제들이 있었다.반복문 내에 sum = 0 /..

오늘의 문제는 백준 2470번 '두 용액' 이었다.   이번 문제는 '투 포인터'를 활용하는 문제였다.처음에는 단순하게 모든 조합을 확인하는 방식으로 풀려고 했지만, N이 최대 100,000까지 주어지기 때문에 O(N^2)로 접근하면 시간 초과가 날 가능성이 컸다.이번 문제의 알고리즘 분류를 보니 '이분 탐색'과 '두 포인터'가 있었다.그래서 O(N log N)으로 풀 수 있는 투 포인터 방식을 사용하도록 했다.  문제 해결 과정배열을 정렬한다.음수는 왼쪽, 양수는 오른쪽에 위치하게 된다.투 포인터를 사용하여 최소 합을 찾는다.하나는 가장 왼쪽 (left = 0), 하나는 가장 오른쪽 (right = N-1) 에 배치한다.두 개의 용액을 더한 값이 0과 가까운지를 확인하면서 포인터를 조정한다.두 용액의 ..

오늘의 문제는 백준 2343번 '기타레슨'이다.https://www.acmicpc.net/problem/2343  4일차 문제도 역시 이분 탐색을 활용하는 문제다.어제 문제보다는 훨씬 직관적이어서 생각보다 수월하게 풀 수 있었다 문제 해결 아이디어블루레이 크기를 결정하는 것이 핵심이다. 따라서 이분 탐색을 적용할 수 있을 것 같았다.블루레이 크기의 최솟값은 가장 긴 강의 길이, 최댓값은 모든 강의 길이의 합이 된다.mid 값을 블루레이 크기로 설정하고, 해당 크기에서 블루레이 개수를 계산한다.블루레이 개수가 M 이하이면 더 작은 블루레이 크기도 가능할 수 있으므로 줄이고, 많다면 블루레이 크기를 늘린다. 코드 구현package Boj;import java.io.BufferedReader;import ja..

2일차 오늘의 문제는 백준 1654번 '랜선자르기'다.https://www.acmicpc.net/problem/1654   오늘 목표는 문제 분석 시간 줄이기였는데, 이해하는 데 시간이 많이 걸렸다.해당 문제의 알고리즘을 살펴보니, '이분 탐색'과 '매개 변수 탐색' 이라길래'매개 변수 탐색'에 대해 먼저 알아보았다.  매개 변수 탐색이라는 단어가 처음에는 낯설었는데, 조건을 만족하는 최대값을 구하는 방법이었다.즉, 특정 조건을 만족하는 최적의 값을 찾는 것이다. 매개변수 탐색은 내부적으로 이진탐색을 사용하고, start와 end라는 변수를 사용한다.여기서 start는 무조건 되는 경우, end는 무조건 안되는 경우이기 때문에 이 경우 최대값을 구할 수 있게 된다.Yes 또는 No일 경우를 가르는 것이라..

드디어 시작한 99클럽 코테 스터디! 오늘의 학습 키워드는 1일차인 만큼 '문제 분석 연습'이다. 1일차 문제는 백준 2776번 '암기왕'이다.https://www.acmicpc.net/problem/2776   여기서 입력받는 N과 M의 크기가 (1 ≤ N, M ≤ 1,000,000) 이므로, O(nlogn)으로 풀어야 한다.풀이 코드는 아래와 같다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.LinkedHashSet;import java.util.StringTokenizer;public class Main { ..