그리디 & 구현

그리디

단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 한다.

ex) 거스름 돈 문제가 그리디 알고리즘으로 풀 수 있다는 정당성을 가지는 케이스는 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원 이라면 그리디 알고리즘은 동전이 4개로 답을 내리지만 정답은 400원 두개이다.

어떤 과정을 반복해야 이 문제를 풀 수 있나를 떠올리는게 중요한듯 하다.
ex) 거스름 돈 문제 : 큰 동전부터 거슬러 줘야 최소한의 동전 갯수를 필요로 한다 -> 위의 예처럼 정당성 살펴보기

구현

풀이를 떠올리는 것은 쉽짐나 소스코드로 옮기기 어려운 문제

알고리즘은 간단하나 코드가 길어지고, 실수, 소수, 문자열을 처리하는 문제가 많고 라이브러리도 쓰는 경우가 있어서 많이 풀어봐야 한다.

시뮬레이션이나 완전 탐색 문제로 나온다? 시뮬, 완전 탐색, 구현은 서로 유사한 점이 많다. 일련의 명령에 따라 개체를 차례대로 이동시킴

방향 벡터 구현해서 풀기