그리디 알고리즘

  • 정의 현재 상황에서 지금 당장 조은 것만 고르는 방법

  • 정당성 분석이 중요함

    • 단순히 반복하는게 아닌 결과 값을 보장하는가

  • 해가 정당한지 점검할 수 있어야한다.

  • 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다

구현

  • 구현이란, 머릿 속에 있는 알고리즘을 소스 코드로 바꾸는 과정

  • 풀이를 떠올리는 것은 쉽지만, 소스 코드로 옮기기 어려운 문제를 지칭

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

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