그리디 알고리즘
그리디 알고리즘은 탐욕법이라고도 불리며, 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕이라는 말은 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’ 을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
•
코딩 테스트에서의 그리디 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 하지만 많은 유형을 접해보고 훈련을 해야한다.
•
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로 와 같이 기준을 알게 모르게 제시 해 준다.
•
그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.
예제 3-1 거스름돈
손님한테 거슬러줘야 하는 동전의 개수가 최소 여야 하므로 가장 큰 화폐 단위부터 거슬러주면 좋을 것이다.
실전문제 큰 수의 법칙
공백으로 구분하여 입력받는 법Python
•
여러 변수를 공백으로 구분하여 입력받으려면
map(자료형, input().split())
•
N 개의 수를 공백으로 구분하여 입력받으려면
list(map(자료형, input().split()))
Java
•
scanner 의 경우 입력받을 때 공백으로 구분하여 입력 받는다.
•
N 개의 수를 공백으로 구분하여 입력받으려면 배열을 만들고 for 문 으로 입력을 받는다. (이때 scanner 로 입력 받는다.)
while 문을 써서 단순하게 구할수도 있겠지만 수열을 이용해서 푸는것이 좋다.실전문제 숫자 카드 게임
각 행에서 가장 작은 수를 구하고, 가장 작은 수들 중에서 최댓값을 찾는 문제Java 의 경우 이중 for 문을 사용해야 하는데, 이때 조건 중 하나인 ‘각 숫자는
1 이상 10000 이하의 자연수 이다’ 를 조심하여 코딩해야 한다.
실전문제 1이 될 때까지
단순 반복도 좋지만 숫자가 커질 때를 대비해서 코딩을 하는 것이 좋다.케이스를 한번 손으로 써서 관찰 해보고, 첫번째 과정과 두번째 과정을 몇번 수행
해야 할지 계산하는 식을 도출해보자.