알고리즘/알고리즘 문제 복기
뮤직비디오
내일도무사히
2021. 9. 17. 15:50
자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의
자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성
www.inflearn.com
직접 풀어본 뒤 김태원님의 강의를 듣고 정리한 내용입니다.
Q
A.
'결정 알고리즘'이라는 문제 풀이법을 푸는것이 핵심이였다.
결정 알고리즘이란 이진검색을 기반으로 하는 문제 풀이법으로
'범위 내에 찾고자하는 답이 분명히 있다'라는 확신이 있고 해당 값이 정렬되어 있을 때 사용 할 수 있는 방법이다.
이 문제에서 다음과 같이 적용 할 수 있다.
예제를 바탕으로 그린 그림이다.
우선 left값과 right 값을 정한다.
여기서는 'dvd의 곡의 길이'가 최소 1분부터 최대 모든 배열의 합인 45까지 있을 수 있다.
그 뒤에 중간 값을 구하고 23분으로 3개 이하의 DVD를 만들 수 있는지 체크한다.
이 역할은 6번라인의 count 함수가 담당하고 있다.
조건에 따라서 기존의 이진탐색 패턴대로 진행해나가며 문제를 풀어내면 된다.
문제의 핵심은 count함수를 만드는게 핵심이다.