kjk9704   1년 전

제가 해결했던 방식을 공유합니다.

이렇게 보여도 848ms 기록이 나올 정도로 나쁘지 않는 성능을 가집니다.

이진 탐색 알고리즘을 어떻게 활용해야 하는지 잘 모르겠다면

"무조건 가장 높은 나무부터 자르자!!!"라는 목표를 세워봅니다.

예시로 나무들이 10m, 20m, 30m, 30m, 40m가 있고 20m 정도 필요하다면 무조건 가장 높은 나무인 40m부터 자릅니다.

그렇게 하면 10m, 20m, 30m, 30m, 30m가 되고 10m 정도 확보합니다.

그 뒤 30m 3그루를 각각 4m씩 절단하면 총 22m 정도 확보되고 목표량을 달성하게 됩니다.

그러면 10m, 20m, 26m, 26m, 26m가 되고 26m로 설정하면 답이 나옵니다.

그리디 알고리즘은 지금 당장 눈 앞에 보이는 최적해를 구하면 답을 구할 수 있도록 하는 알고리즘이고

여기서 이 문제의 최적해는 (지금 당장 보이는 가장 높은 나무들부터 자르자)입니다.

수정 : 정확히는 최적해를 여러 번 적용한 "브루트 포스 알고리즘"에 더 가까운 것으로 판단합니다.

zenith82114   1년 전

이 풀이는 순수한 그리디라기보다는 그리디스러운 최적화가 들어간 브루트포스라고 부르는 것이 더 적합하다고 생각합니다. 본질은 모든 높이를 다 시도해보는 것이지만, 절단 높이가 높을수록 잘리는 나무가 적다는 사실을 이용해서 절단 높이를 올라가는 방향이 아닌 내려가는 방향으로 순회하여 계산량이 줄어듭니다.

kjk9704   1년 전

그리디 느낌이 나는 브루트 포스 알고리즘... 아 그것도 맞는 말이군요.

그러면 최적해(그리디 알고리즘)를 여러 번 적용한 브루트 포스 알고리즘으로 해석하는게 더 맞겠군요.

댓글을 작성하려면 로그인해야 합니다.