오늘의 키워드
•
이분 탐색
•
최적화 문제
문제 파악 및 풀이
•
문제를 읽고 나눠줄 수 있는 과자의 최대 길이를 구해야 한다는 것을 이해했다.
•
하지만 어떤 알고리즘으로 접근해야 할지 몰라 끝내 풀지 못했다.
•
이후 풀이를 찾아보니, 이분 탐색을 활용하는 문제였다.
•
과자의 길이를 기준으로 이분 탐색을 하면서, 특정 길이로 과자를 나누었을 때 아이들에게 모두 나눠줄 수 있는지를 판별하는 방식이다.
핵심 아이디어
•
과자 조각의 길이를 기준으로 이분 탐색을 한다.
•
특정 길이로 나누었을 때, 아이 수보다 많이 만들 수 있으면 길이를 늘리고, 부족하면 길이를 줄인다.
오늘의 회고
어려웠던 점
•
과자를 나누는 문제에서 단순히 브루트포스나 그리디로 접근해야 하나 고민하다가 방향을 잡지 못했다.
•
'범위 내 최댓값을 구하는 문제'는 이분 탐색을 떠올려야 한다는 감각이 부족했다.
개선점
•
최댓값이나 최솟값을 구하는 문제에서는 이분 탐색을 우선적으로 고려하는 습관을 들이자.
•
이분 탐색 문제를 더 많이 풀어보고, 문제의 형태를 보고 빠르게 알고리즘을 유추하는 능력을 키워야겠다.