[Algorithm] 그리디 알고리즘(Greedy Algorithm) & 구현(Implementation)

그리디 알고리즘

그리디 알고리즘(탐욕법)은 __현재 상황에서 지금 당장 좋은 것만 고르는 방법__을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 해법은 __정당성 분석__이 중요하다.

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

예를 들어, 루트 노드부터 시작하여 거쳐 가는 노드 합을 최대로 만들고 싶다면 최적의 해를 보장할 수 없다.

구현

구현이란, __머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정__이다. 흔히 __풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제__를 지칭한다.

예를 들면,

1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
3. 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
4. 적절한 라이브러리를 찾아서 사용해야 하는 문제

일반적으로 알고리즘 문제에서의 2차원 공간은 __행렬(Matrix)__의 의미로 사용된다.

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 __방향 벡터__가 자주 활용된다.

참고자료

이것이 취업을 위한 코딩테스트다. (나동빈 저)

관련동영상