모든 내용은 (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬 에서 비롯되었습니다.
강의 요약 및 복습을 위해 포스팅합니다.
12강 : 그리디 알고리즘 개요
그리디 알고리즘
- 그리디 알고리즘(탐욕법) : 현재 상황에서 당장 좋은 것만 고르는 방법
- 일반적 그리디 알고리즘은 문제를 풀기 위한 최소 아이디어를 떠올리는 능력을 요구한다
- 그리디 해법은 정당성 분석이 중요 → 단순히 좋아 보이는 것을 반복 선택해도 최적해를 구할 수 있는지 검토.
- 일반적 상황에서 그리디 알고리즘은 최적 해를 보장할 수 없을때가 많다.
- BUT 코딩 테스트 내 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.
거스름돈 문제
- Q. 1260원을 거슬러줘야 할 때 500원/100원/50원/10원의 갯수를 최소로 거슬러 주는 방법은 무엇인가?
- A. 파이썬 코드 작성 (파일 첨부)
거스름돈 문제 : 시간 복잡도 분석
- 화폐 종류가 K라고 할때, 소스코드의 시간 복잡도는 O(K)다.
- 해당 알고리즘의 시간 복잡도는 거슬러줘야하는 금액과 무관.
- 동전의 총 종류만큼 함수가 실행되므로 화폐의 종류가 시간복잡도를 결정한다.
13강 : 그리디 유형문제 풀이
문제 1 : 1이 될때까지
- 어떠한 수 N이 1이 될때까지 다음 두 과정 중 하나를 반복 선택해 수행하려 합니다.
1. N에서 1을 뺍니다.
2. N을 K로 나눕니다.
- N과 K가 주어질 때 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램은?
→ 주어진 N에 대해 최대한 많은 나누기가 수행되어야 한다.
문제 2 : 곱하기 또는 더하기
- 문자열 S가 주어졌을 때 왼쪽에서 오른쪽 하나씩 모든 숫자를 확인해서
- 숫자 사이에서 x 또는 + 연산자를 넣어 만들어질수 있는 가장 큰 수를 구하시오.
→ 두 수 중에서 하나라도 1 이하인 경우는 더하기, 나머지가 2 이상인 경우 곱셈
문제 3 : 모험가 길드
- 한 마을에는 모험가 N명이 있다.
- N명 모험가를 대상으로 ‘공포도’를 측정하여 공포도가 높으면 상황 대처 능력이 낮다
- 따라서 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야한다
- 따라서 최대 몇 명의 모험가 그룹을 만들 수 있는가?
- 또한 모든 모험가를 다 그룹에 참여할 필요는 없다
→ 공포도 낮은 요소부터 하나씩 확인, 현 그룹에 해당 모험가를 하나씩 포함, 현 그룹의 모험가 수가 현 공포도 이상이면 그룹 결성