[이것이 코딩 테스트다 with Python] 13강 그리디 알고리즘 유형 문제 풀이

※ 다음 강좌의 내용을 정리한 것입니다.

www.youtube.com/watch?v=_TG0hVYJ6D8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=13

 

- "1이 될 때까지" 문제 해결 아이디어: 주어진 N에 대하여 최대한 많이 나누기를 수행하기

(N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 훨씬 수를 많이 줄이므로)

 

- "1이 될 때까지" 정당성 분석: N이 아무리 큰 수여도, 2이상의 K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있습니다.

 

- Python에서는 정수 데이터를 처리할 때, 수의 범위의 제한이 없습니다.

 

- "곱하기 혹은 더하기" 문제 해결 아이디어: 두 수 중에서 하나라도 1이하인 경우에는 더하며, 모두 2 이상인 경우에 곱하기

 

- "모험가 길드" 문제 해결 아이디어: 오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인합니다.

앞에서부터 공포도를 하나씩 확인하며 '현재 그룹에 포함된 모험가의 수'가 '현재 확인하고 있는 공포도'보다 크거나 같다면 이를 그룹으로 설정하면 됩니다.