알고리즘 이론 정리(1) - 그리디, 구현

그리디 알고리즘

->  "현재 상황에서 지금 당장 좋은 것만 고르는 방법"
-> 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며 , 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서  "가장 큰 순서대로"  "가장 작은순서대로" 와 같은 기준을 알게 모르게 제시해준다. (주로 정렬 알고리즘과 짝을 이루어 출제된다.)

대표적인 문제로  "거스름돈" 문제가 있다.

구현(Implementation)

-> "머리속에 있는 알고리즘을 소스코드로 바꾸는 과정"

-> "완전탐색", "시뮬레이션" 모두 구현 유형으로 묶어서 다룬다.

-> "완전탐색"  :  모든 경우의 수를 확인하여 계산하는 해결 방법

-> "시뮬레이션"  : 문제에서 제시한 알고리즘을 차례대로 직접 수행

**구현 문제 구분하는 방법**

보통 구현의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다.

 

 

출처 :  "이것이 코딩 테스트다" [나동빈 저]