2. 그리디 & 구현

hiworld·2022년 6월 15일
0
post-thumbnail

📌 그리디 알고리즘 개요

1. 그리디 알고리즘

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

  • 지금 당장 좋은 것만을 반복적으로 골랐을 때 최종적으로 최적의 해를 구할 수 있는 게 맞는지 검토하는 정당성 분석이 중요

  • e.g., 거스름돈 문제

    • 거스름돈의 종류가 500원, 100원, 50원, 10원과 같이 큰 단위가 작은 단위의 배수라면 그리디 알고리즘 사용 가능
    • 반대로, 500원, 400원, 100원과 같이 배수 관계가 아니라면 그리디 알고리즘을 사용했을 때 최적의 해를 보장받을 수 없음

📌 구현 유형 개요

1. 구현 유형

  • 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성

  • 흔히, 풀이를 떠올리기는 쉬우나 코드로 옮기기는 어려운 문제들이 해당됨

  • 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법

  • 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행


[참고]

profile
바쁘게 살아 보자!

0개의 댓글