인프런 커뮤니티 질문&답변
작성한 질문수
5주차 개념강의 중 그리디의 개념에 대해 질문드립니다
해결된 질문
작성
·
362
0
안녕하세요
그리디를 배우면서
1) 무식하게 > 2) DP > 3) 그리디 순서로 문제를 접근해보라고 배웠습니다.
그와 함께 그리디는 현재 인덱스를 기준으로 최선의 해라고 생각되는 것이 전체의 최적해가 될 수 있음을 갖고 푸는 것이며, 최적부분구조 및 탐욕적 속성을 갖는 경우에 사용한다.
>> 하지만 우리는 '이게 되지 않을까?'라는 생각으로 접근하여 그리디를 사용한다.
라고 배웠습니다.
DFS, BFS, 비트마스킹 완전탐색, 백트래킹 등은 그래도 A=B이다 라는 식으로 해당 개념이 공식처럼 와닿았습니다. 하지만 그리디의 경우 단순히 "정렬 및 우선순위 큐를 활용하면 그리디다"는 아닌 것 같습니다.
제가 이해한 바로는
1) 그리디는 말 그대로 '이렇게 풀면 되지 않을까?'라고 시도해보는 접근방법이다 - 명확한 공식이 있는 것이 아니다 -
2) 하지만 그리디는 정렬 및 우선순위큐를 활용하는 문제가 빈번하다
3) 정렬 및 우선순위큐로 풀리지 않는다면 그 외의 다른 최선의 방법을 강구해본다.
이렇게입니다.
제가 그리디에 대해 이해한 것이 맞을까요?
3)의 경우로 가야한다면 다른 방법이 있는 것인지, 경험에 의해 고민해가며 해결해나가야 하는 것인지 궁금합니다.
감사합니다.
답변 1
1
1) 그리디는 말 그대로 '이렇게 풀면 되지 않을까?'라고 시도해보는 접근방법이다 - 명확한 공식이 있는 것이 아니다 -
네 맞습니다. 휴리스틱에 가깝죠. 근데 이걸 원리적으로 푼다면 이렇게 풀어야 해요. 어떠한 점화식을 작성합니다. 귀납법이든 뭐든 증명을 합니다. 해당 명제를 기반으로 코드를 구축해서 푸는 것이 정석입니다.
하지만. 이런 것을 코테에서 하기에는 어려워요. 그래서 그냥 ~~ 하면 되지 않을까? 생각하고 푸시면 됩니다.
2) 하지만 그리디는 정렬 및 우선순위큐를 활용하는 문제가 빈번하다
맞습니다. 그러나 빈번하다라고 해서 그렇게 단정지으면 안되요
https://blog.naver.com/jhc9639/222093730646
이걸 잠깐 볼까요? 이 문제는 그리디 문제인데 정렬과 우선순위큐를 쓰지 않았죠? 먼저 정렬이나 우선순위큐를 생각하는 것은 좋으나 단정지으시면 절대 안됩니다.
3) 정렬 및 우선순위큐로 풀리지 않는다면 그 외의 다른 최선의 방법을 강구해본다.
네 좋은 접근법이에요.
친절하게 정리해주셔서 감사합니다!