* 나동빈님의 이코테 2021강의 정리
Grid Algorithm (탐욕법)
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
- 최소한의 아이디어 구상.
- 정당선 분석 중요. 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는 지 검토. 일반적으로 최적의 해가 아닐 때가 많음.
- 코딩테스트에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제.
문제1: 거스름돈
- 거스름돈 500원, 100원, 50원, 10원 동전. 거슬러 주어야할 동전의 최소 개수.
문제해결방법
- 가장 큰 화폐 단위부터 돈을 거슬러 줌(최적의 해를 구하기 위해).
- N원을 거슬러 줘야할 때, 500원 부터 거슬러 줌.
- 이후 동전 크기대로 차례대로 거슬러줌.
정당성 분석
- 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문. 500원, 100원, 50원, 10원 단위라서 배수임.
답안(Python)
n = 1260
count = 0
array = [500,100,50,10]
for coin in array:
count += n//coin # 해당 화폐로 거스러 줄 수 있는 동전의 개수
n %= coin 답안(Java)
int n = 1260;
int cnt = 0;
int[] coinTypes = {500, 100, 50, 10};
for(int i=0; i<coinTypes.length; i++){
cnt += n/coinTypes[i];
n %= coinTyes[i];
}시간복잡도
- 화폐의 종류가 K라고 할 때, 코드의 시간복잡도는 O(K).
- 시간복잡도는 동전의 총 종류에만 영향을 받음. 화폐의 종류만큼 for문 돌림.
문제2: 1이 될 때까지
- N이 1이 될 때까지 둘 중 하나 선택해서 반복 수행.
- N에서 1 빼기.
- N을 K로 나누기.(N이 K로 나누어 떨어질 때만 가능)
문제해결방법
- 최대한 많이 나누기.
- 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 많이 줄임.
정당성 분석
- 가능하면 최대한 많이 나누는 작업.
- K가 2이상 이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음. N은 항상 1에 도달(최적의 해 성립)
답안(Python)
n, k = map(int,input().split())
result = 0
while True:
//N이 K로 나누어 떨어지는 수가 될 때까지 빼기
target=(n//k)*k
result += (n-target)
n = target
//N이 K보다 작을 때(더 이상 나눌 수 없을 때)반복문 탈출
if n<k:
break
result += 1
n//=k
//마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)답안(Java)
int n = sc.nextInt();
int k = sc.nextInt():
int result = 0;
while True{
int target = (n/k)*k;
result += (n-target);
n = target;
if(n<k) break;
result += 1;
n/=k;
}
result += (n-1);문제3: 곱하기 혹은 더하기
- 숫자로 이루어진 문자열을(왼->오) x혹은 +하여 가장 큰수 구하기. 모든 연산은 왼쪽부터.
문제해결방법
- 두 수 중에 하나라도 1이하인 경우에는 더하며, 두 수가 모두 2이상인 경우에는 곱한다.
답안(Python)
data = input()
result = int(data[0]) # 첫 번째 숫자로 변경하여 대입
for i in range(1, len(data)):
# 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
num = int(data[i])
if num <= 1 or result <=1:
result += num
else:
reust *= num답안(Java)
String str = sc.next();
# 첫번째 문자를 숫자로 변경한 값을 대입
long result = str.charAt(0)-'0'; # 아스키 코드 값 빼줌
for(int i=1; i<str.length(); i++){
int num = str.charAt(i)-'0'; # 아스키 코드 값 빼줌
if(num <=1 || result<=1){
result += num;
}
else{
result *= num;
}
}문제4: 모험가 길드
- 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여. 여행을 떠날 수 있는 그룹 수의 최댓값.
문제해결방법
- 오름차순 정렬.
- 앞에서 부터 공포도 확인. 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 그룹으로 설정.
답안(Python)
n = int(input())
data = list(map(int,input().split()))
data.sort()
group = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수
for i in data: # 공포도 낮은 순
count += 1 # 현재 그룹에 해당 모험가 포함.
if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면 그룹결성
group +=1 # 그룹의 수 증가
count = 0 # 현재 그룹 모험가의 수 초기화답안(Java)
public static int n;
public static ArrayList<Integer> arrayList = new ArrayList<>();
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i=0;i<n;9++){
arrayList.add(sc.nextInt());
}
Collections.sort(arrayList);
int result = 0
int count = 0
for(int i=0; i<n; i++){
count+=1;
if(count>=arrayList.get(i)){
result += 1;
count = 0;
}}
Hello!