ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] 그리디 정리
    알고리즘 2022. 9. 16. 14:56
    728x90

    그리디 ( 탐욕법 ) - 정당성 분석 (최적의 해 찾기)

    그리디는 지금 현재 상황에서 고를 수 있는 최적의 해를 구하는 것이다.

    그리디 특징

    • 사전에 외우지 않고 풀수 있을 가능성이 있는 유형, 따라서 많은 유형을 접해보는것이 중요하다
    • 문제를 풀기 위한 최소한의 아이디어를 요한다. ( 특정 문제에서 현재 상황에 가장 좋아 보이는 것만을 선택해 풀수있는지 파악할 수 있어야 한다.
    • 일부는 다익스트라 알고리즘 처럼 암기가 필요한 부분이 있다
    • 정렬 라이브러리의 사용 방법을 알아야한다 ( 순서에 대한 기준을 알아야 한다. )

     

    문제 1 ) 거스름돈 문제

    N은 항상 10의 배수

    idea - 가장 큰 단위가 작은 단위의 배수이므로, 가장 큰 화폐 단위부터 거슬러야함

    n = 1260 # 1260원을 내야함
    count = 0
    
    array = [500,100,50,10] # 큰화폐부터 차례로 확인
    
    for coin in array:
    	count += n // coin  # 거슬러 줄수있는 동전 개수세기 1260 // 500 == 2
    	n %= coin # 260원이 남음
    
    print(count) # 화폐종류가 K일때, 시간복잡도는 O(K)
    

    → O(K) : 화폐의 종류만큼 반복 수행, 시간 복잡도는 금액과는 무관, 화폐 종류에만 영향을 받음

     

     

    문제 2) 1이 될때까지 : N을 1로 만들때까지 수행횟수의 최솟값 찾기

    수행과정

    • N에서 1을빼기 ( 1≤n≤100.000), ( 2≤k ≤100.000)
    • N을 K로 나누기
      • 두가지의 수행을 통해 n→1로 하고 그 횟수를 최소한으로 하기

    idea

    • n을 최대한 많이 나누기
    • 2이상 수로 나누는 작업이 1을 빼는것보다 좋다
    n.k = map(int,input().split())
    res = 0 # 연산 횟수
    
    while True:
    	target = (n//k) * k  #n이 k로 나눠 떨어지지 않을때, 나눠떨어질수있는 가장 가까운값 찾기
    	res += (n - target) #n이 k로 나눠 떨어지는 수가 될때까지 빼기
    	n = target
    	if n < k:
    		break
    	res += 1 # k로 나누기
    	n //= k
    
    # 마지막으로 남은 수에 대하여 1씩 빼기 ㅠ
    res += (n-1)
    print(res)
    
    

     

     

    문제 3) 곱하기 혹은 더하기

    수행과정

    • 각 문자열은 0 ~ 9 로 이뤄져있고, 각 숫자들을 ‘+’ 혹은 ‘*’을 연결해서 최댓값 구하기

    idea

    • 대부분 ‘+’보다는 ‘*’가 더 크게 만든다
    • 다만 하나라도 0 혹은 1이 있다면, ‘+’을 수행
    data = input() #문저열로 받아짐
    res = int(data[0]) # 받은 데이터의 1번째 데이터를 int형으로 바꿈
    for i in range(1, len(data)): # 1부터 data의 길이만큼 수행
    	num = int(data[i])
    	if num <= 1 or res <=1:
    		res += num
    	else:
    		res *= num
    print(res)
    

     

     

    문제 4) 모험자 길드

    수행과정

    • 모험가 N명 (N명을 대상으로 공포도 측정, 공포도가 크면 상황 대처능력이 떨어짐)
    • 공포도 x인 모험가는 x명이상으로 그룹참여 가능
    • 여행을 떠날 수 있는 그룹의 최댓값
    • ex) N = 5, 공포도가 각각 2,3,1,2,2 → 그룹은 1,2 즉, 2개 가능 & 남은 사람은 마을에 남아 있어도 된다.
    • 여기서는 3이 해당됨

    idea

    • 오름 차순 정렬 → 공포도가 낮은 모험가부터 하나씩 확인
    n = int(input())
    data = list(map(int,input().split()))
    data.sort()
    
    res = 0 # 총 그룹수
    count = 0 # 현재 그룹에 포함된 모험가 수
    for i in data: # i는 공포도
    	count += 1
    	if count >= i:
    		res += 1
    		count = 0
    print(res)
    
Designed by Tistory.