[알고리즘] 그리디 알고리즘

그리디 알고리즘

 

그리디 알고리즘 = 탐욕법 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미

정당성 분석이 중요! 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토.

 

 

문제 1. 거스름돈 문제

 

Q. 500원, 100원, 50원, 10원짜리 동전이 무한한 경우 손님에게 거슬러 줄 돈이 N원일 때, 동전의 최소 개수는? 단, 거슬러 줄 돈 N은 항상 10의 배수

 

A. 가장 큰 화폐 단위부터 돈을 거슬러 주면 되는데 이게 최적의 해를 보장하는 이유는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

(만약 500원, 400원, 100원 이면 이런식으로는 최적의 해가 나오지않음)

 

n=1260 #거슬러 줄 돈
count = 0

#큰 단위의 화폐부터 차례대로 확인
array = [500,100,50,10]
 
for coin in array : 
    count += n//coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin # %= 좌항을 우항으로 나눈 나머지를 좌항에 대입
    
print(count)

=> 이 알고리즘의 시간 복잡도는 거스름돈의 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

 

문제 2. 1이 될때까지 빼거나 나누기

Q. 어떤 수 N이 1이 될 때까지 (1). N에서 1을 뺀다. (2). N을 K로 나눈다. 를 반복해 선택한다. 두번째 연산은 나머지 없이 나누어 떨어질때만 선택 할 수 있다. 예를 들어 N이 17, K가 4라고 가정하면 (1)을 한번 수행하고 (2)를 두번 수행하는게 실행횟수 3으로 최소 횟수가 된다. 이 때 N과 K가 주어질 때 N이 1이 될 때까지 (1)혹은(2)의 과정을 수행하는 최소 횟수를 구하는 프로그램을 작성하라.

A. 주어진 N에 대해 나누기를 많이 수행하는게 최소 횟수에 유리.

step 1. 나누어 떨어지는 수가 되어야 (2)를 수행할 수 있기 때문에 나누어 떨어지는 수를 먼저 구하기
step 2. 나누어 떨어지는 수는 정수로, (N//K)*K 로 구할 수 있음
step 3. N에서 나누어 떨어지는 수까지 (1) 수행으로 -1씩 진행
step 4. (2)실행 후 남은 수가 다시 K로 나누기 할 수 있는지 확인(K보다 남은 수가 커야함)
step 5.  남은 수가 K보다 작아서 나누기 할 수 없다면, 1까지 얼마나 (1)을 수행해 빼나가야 하는지 확인

#N,K 공백을 기준으로 구분하여 입력 받기
n,k = map(int, input().split())

result = 0

while True : 
    #N이 K로 나누어 떨어지는 수가 될 때까지 빼기 진행
    target = (n//k)*k # // 연산자는 좌항을 우항으로 나눔(정수형), 정수형이므로 k로 나누어 떨어지는 숫자가 나옴!    
    result += (n - target) #1을빼는 연산을 몇번 수행할지, 입력받은N에서 target이 될때까지 빼야함
    n = target 
    #N이 K보다 작을 때 (더 이상 나눌 수 없을때 반복문 탈출)
    if n < k : 
        break
    #K로 나누기
    result += 1 #N을 K로 나누는 연산 한번 실행
    n //= k #좌항에 우향을 나눈 값을 좌향에 대입(정수)
    
#마지막으로 남은 수에 대해 1씩 빼기
result += (n-1) #남은 수 N이 1보다 크다면 1씩빼는 연산 수행
print(result)

 

 

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

Q.각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하라. 단, 사칙연산 순차가 아니라 왼쪽에서부터 연산이 이루어진다.

 예를 들어 02984라는 문자열로 가장 큰 수를 만든다면

(0+2) * 9 * 8 * 4 = 579 이다. 만들어질 수 있는 가장 큰수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.

 

A.0혹은 1 숫자가 나올때만 더하고, 나머지는 곱하는게 더 큰 수를 만들 수 있음.

data = input()

#첫번째 문자를 숫자로 변경해 대입
result = int(data[0])

for i in range(1, len(data)) : 
    num = int(data[i]) #입력값확인
    if num <= 1 or result <= 1 : #둘 중 하나라도 0이거나 1이면 더하기로 수행
        result += num
    else : 
        result *= num

print(result)

 

 

문제 4. 모험가 길드 문제

Q.길드에서는 N명의 모험가가 있고, 이들 모두 '공포도'를 측정한다. 모험가 그룹을 구성할 때, 공포도가 x 인 모험가는 반드시 x명 이상으로 구성한 그룹에 참여해야 여행을 떠날 수 있다. 최대 몇 개의 모험가 그룹을 만들 수 있는가

A.공포도 x 가 제일 작은 수, 0 혹은 1인 경우에는 혼자서도 떠날 수 있다, 따라서 공포도를 기준으로 오름차순으로 정렬하여 최소한의 인원으로 그룹을 모두 결성해 진행하는게 좋다

n=int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 #총 그룹의 수
count = 0 #현재 그룹에 포함된 모험가의 수

for i in data: #공포도를 낮은 것부터 하나씩 확인
    count += 1 #현재 그룹에 해당 모험가를 포함
    if count >= i:
        result += 1 #총 그룹 수 증가
        count = 0 #그룹 모험가 수 초기화
        
print(result) #총 그룹 수

 

---

 

시뮬레이션과 완전 탐색

 

 

구현(Implementaion) 문제

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭

1. 알고리즘은 간단한데 코드가 지나치게 길어짐

2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야함

3. 문자열을 특정 기준에 따라 끊어서 처리

4. 적절한 라이브러리를 찾아서 사용해야 하는 문제

 

 

출처 : 이코테2021

 

 

문제 5. 상하좌우 문제

Q.여행가 A는 N*N 크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 왼쪽 위에서 여행가가 출발한다고 가정하고 L : 왼쪽한칸이동, R : 오른쪽 한칸이동,  U : 위로 한칸 이동, D : 아래로 한칸이동 이 이동 계획을 나타내는 문자라면(공간을 벗어나는 이동은 불가) N과 이동계획문자들이 주어질 경우 최종 도착지점의 좌표 (X,Y)를 공백을 기준으로 구분해 출력하라

A. 일련의 명령을 차례로 이행한다는 점에서 시뮬레이션유형으로 분류되며 단순히 구현이 중요한 대표적 문제 유형이다.

 

#입력값
n = int(input())
x, y = 1,1 #시작위치
plans = input().split() #입력 문자열들 배열로 담기

#L,R,U,D에 따른 이동방향
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_types = ['L','R','U','D']

#입력받은 이동계획들 하나씩 확인
for plan in plans : 
    #이동 후 좌표 구하기
    for i in range(len(move_types)) : 
       if plan == move_types[i] : 
           nx = x + dx[i] #앞서 따로 초기화 하지 않고 이렇게 바로 사용해도됨
           ny = y + dy[i]
       #공간을 벗어나면 무시
       if nx < 1 or ny < 1 or nx > n or ny > n : 
           continue
       #이동 수행
       x,y = nx,ny
       
print(x,y)

 

 

문제 6. 시각 문제

Q.정수 N이 입력 되면 00시00분00초부터 N시 59분 59초 까지 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각 ( 00시 00분 03초, 00시13분 30초) 반면 다음은 3이 하나도 포함되어 있지 않으므로 세면 안되는 시각 (00시 02분 55초, 01시 27분 45초)

A.가능한 모든 시각의 경우를 하나씩 다 세서 풀 수 있음. 00시 00분 00초 ~ 23시 59분 59초까지 모든 경우는 86,400(24*60*60)

이러한 유형은 완전 탐색 문제 유형 이라고 명칭

#입력받기
h = int(input())

count = 0
for i in range(h+1) : 
    for m in range(60) : 
        for s in range(60) : 
            #3포함인지 확인
            if '3' in str(i)+str(m)+str(s) : 
                count += 1
print(count)

 

문제 7. 왕실의 나이트

Q.8*8 좌표 평면에 나이트는 L자 형태로만 이동하고 밖으로는 나갈 수 없다. 수평으로 두 칸 이동 후 수직으로 한 칸을 이동하거나 수직으로 두 칸 이동 후 수평으로 한 칸 이동하는 경우만 가능할 때 입력 문자(a1 처럼 열과행을 나타냄)가 주어진 경우 이동할 수 있는 경우의 수를 출력.

A. 나이트가 이동 가능한 좌2상1, 좌2하1, 우2상1, 우2하1, 상2좌1 상2우1, 하2좌1, 하2우 여덜바지 경로를 하나씩 확인해 이동이 가능한지 센다. 리스트를 이용해 8가지 방향에 대한 방향 벡터를 정의

#현재 나이트 위치 입력받기
input_data = input() #a1 같은 형식
row = int(input_data[1]) #행의 위치 a1 인 경우 1
#문자로 들어온 값을 아스키 코드로 변환하고 문자 a를 아스키로바꾼 값을 빼고 1을 더함
column = int(ord(input_data[0])) - int(ord('a')) + 1 #열의 위치 a1인 경우 a

#나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2,-1), (-1,-2), (1, -2), (2, -1), (2,1), (1,2), (-1,2), (-2,1)]

#8가지 방향에 대해 각 위치로 이동이 가능한지 확인
result = 0
for step in steps : 
    #이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    #해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >=1 and next_column <= 8 : 
        result += 1
        
print(result)

 

 

문제 8. 문자열 재정렬

Q.알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬해 이어서 출력하고, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. (K1KA5CB7이 들어오면 ABCKK13을 출력)

A. 리스트에 저장해 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력

data = input()
result = []
value = 0

#문자를 하나씩 확인
for x in data : 
    #알파벳이면 결과리스트에 삽입
    if x.isalpha() : 
        result.append(x)
    #숫자는 따로 더하기
    else : 
        value += int(x)
        
#알파벳을 오름차순으로 정렬
result.sort()

#숫자가 하나라도 존재한느 경우 가장 뒤에 삽입
if value != 0 : 
   result.append(str(value))

#최종 결과 리스트를 문자열로 변환 해 출력
print('',join(result))