TIL-Greedy algorithm, Implementation

Greedy algorithm

• Greedy: "탐욕스러운, 욕심 많은"이라는 의미
• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 탐욕 알고리즘의 해결 단계 구분
  1. 선택 절차: 현재 상태에서 최적의 해답을 선택
  2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사
  3. 해답 검사: 원래의 문제가 해결되었는지를 검사, 해결되지 않았다면 선택절차로 돌아가 위의 과정을 다시 반복
• 특정한 두가지 조건을 만족하는 상황이 아니라면, 탐욕 알고리즘은 최적의 해를 보장하지 못함
  1. 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않는다
  2. 최적 부분 구조: 문제에 대한 최정 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다
• 항상 최적의 결과를 도출하지는 않지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점

Implementation

• Implementation: 구현하다
• 알고리즘 문제를 푼다는 것은, 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것과 같다
  • 수많은 문제 해결 과정은 대부분 여러 개의 카테고리로 묶여진다
    • N개의 숫자들을 특정한 기준으로 순서를 조정하는 것을 정렬이라고 부름
    • 그래프 탐색의 경우 탐색 방식에 따라 DFS/BFS라고 부름
    • 각 카테고리는 원하는 의도가 분명하고, 그것을 해결하는 것이 목표