그리디

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

1. 그리디란?

매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘. 단, 최적해를 보장해주지 않는다.

=> 다음과 같이 A에서 B/D를 선택할때 최적의 선택.
=> 그리고 B를 갔을때 최적의 선택 .... 으로 이어짐.
=> 결과적으로 전체를 봤을때는 최고의 선택이 아닐 수 있음

실제 사용 예시

• 거스름돈 반환 문제

2. 그리디 알고리즘의 특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많음
  => 주로 선형 단위에서 해결이 됨
• 크루스칼, 다익스트라 알고리즘 등에 사용됨
• 직관적인 문제 풀이에 적합

=> 하나의 특정 문제풀이 방식이 아닌 하나의 개념으로 봐야함

3. 코테

핵심키워드 : 가장 큰 순서대로, 가장 작은 순서대로
참고 상황 : 탐색으로 풀 수 있으나 제한조건이 걸려있는 상황
대표문제 : 큰수만들기

꿀팁으로 강사님의 문제풀이 과정을 엿볼 수 있었음.

1. 맨 처음에 탐색을 고려해본다 그러나 제한조건에 걸림
   => N이 백만 이상이면 O(N), O(N log N) 만이 가능
   => 고로 모든 케이스를 찾는 탐색은 효율성에 걸린다.

2. 아이디어 제시
   => 테스트에 이 아이디어를 대입해본다
   => 틀리면 수정 틀리면 수정... 반복

3. 이를 통해 여러 조건들이 생성 되는데 하나하나 텍스트로 정리해본다

4. 해당 조건들에 맞는 자료구조 등 문제유형이 파악되면 적용한다.

현재 상황에서 제일 합리적인 판단을 하고 그리드의 특징은 규칙을 이용해 선형 시간을 사용한다
=> 결국엔 모든 값을 구하는 방법도 있기는 한데 제한시간으로 걸린다. 그러므로 기존에 알고 있는 명칭으론 가지치기 해서 처리하는 방법이라고 생각됨.