[알고리즘 / 자료구조] 그리디 , 구현

⭐️  그리디 ⭐️ 

• 탐욕법 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 (현재 선택이 나중에 미칠 영향을 고려하지 않음 여기서 나중에 미칠 영향을 고려하는 것이 다익스트라, 플로이드 위셜 알고리즘)

 

예시

N원을 거슬러 주어야할 때 가장적은 숫자의 화폐를 이용해 거슬러주는 경우는? (잔돈 , 500 / 100 / 50 / 10 )

→ 대표적인 그리디 알고리즘으로 해결할 수 있는 방법 “가장 큰 화폐 단위로부터 돈을 거슬러 주면되는 것”

 

문제 해결과정

1. N원에 대해 500원으로 거슬러 줄 수 있을 만큼 거슬러 줌
2. 100원을 거슬러 줄 수 있을 만큼 거슬러 줌
3. 50 → 10 차례로 거슬러 줌

 

Python solve

n = 1260 # N원이 1260원일 경우
array = [500, 100, 50, 10]
cnt = 0
for i in array:
	cnt += n // i # 몫 구하기 i 몇개가 사용되었는지 
	n %= i # 나머지 가져오기 cnt 만큼 i를 사용했을 때 나머지 저장

# result cnt : 6

 

 

정당성

• 모든 문제에 그리디 알고리즘을 적용하기에는 어려움 : 최적의 해를 찾지 못하는 경우가 많음
• 정확한 답을 찾을 수 있다는 보장이 있는 문제에 한해 효과적임 : 그리디로 문제를 해결하였을 때 해법이 정당한지 검토할 필요가 있음

 

 

⭐️ 구현⭐️ 

• 시뮬레이션, 완전 탐색
• 머리속의 알고리즘을 소스코드로 바꾸는 과정
• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려움
• 해당 언어의 문법과 문제의 요구사항을 정확히 알고 있어야함
• 완전탐색 / 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다고 함

 

구현문제 예시

• 알고리즘은 간단한데 코드가 길어짐 : 프로그래밍 언어에 따라 다름
• 실수 연산을 다루고 특정 소수점 자리까지 출력해야하는 문제
• 문자열을 특정한 기준에 따라 끊어 처리해야하는 문제
• 적절한 라이브러리를 찾아서 사용해야하는 문제

메모리와 시간제한을 고려해야함!

 

 

 

* 출처 *

- 동빈나 "이코테"

- https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2 

*** 본 강의를 요약 제 의견을 추가한 내용으로 문제 발생 시 비공개로 전환하겠습니다. ***