[TIL] 그리디 알고리즘

오늘은 어제 봤던 그리디 알고리즘 영상을 마저 보고 백준에서 그리디 관련 문제들을 풀었다. 이번 글에서는 영상에서 나온 문제들을 정리하고, 백준 문제는 다른글에 정리했다.

문제2:곱하기 혹은 더하기

각자리숫자로만 이루어진 문자열S를 왼쪽부터 하나씩 모든 숫자 사이에 +혹은 x 를 넣어 가장 큰 수를 구하는 프로그램. 연산자에 상관없이 모든 연산은 왼쪽부터 순서대로 이루어진다.

• 해결법 : +보다는 x가 값을 더 크게 하므로 두 수중 하나라도 1 이하인 경우 x를 사용한다.

문제3: 모험가 길드문제

공포도가 x인 모험가는 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있을때 n명의 모혐가 중 여행을 떠날 수 있는 그룹의 최댓값 구하기

• 해결법 : 모험도를 오름차순 정렬해서 공포도가 적은 사람부터 팀을 짠다.

import sys
N=int(sys.stdin.readline().strip())
numli=[]
numli=list(map(int, sys.stdin.readline().split()))
numli.sort()
person=0
cnt=0
for i in range(N):
    person+=1
    if numli[i]<=person:
        cnt+=1
        person=0
print(cnt)

<구현 문제>

구현 유형의 문제란 풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제

ex)
알고리즘은 간단한데 코드가 많이 긴 문제
실수연산. 특히 소수점 자리까지 출력하는 문제
문자열을 특정 기준에 따라 끊어 처리해야하는 문제
라이브러리를 찾아 사용하는 문제

import sys
N=int(sys.stdin.readline())
move=list(map(str, sys.stdin.readline().strip().split()))
x=1
y=1
for i in range(len(move)):
    if move[i]=='R' and y!=N:
        y+=1
    elif move[i]=='L' and y!=1:
        y-=1
    elif move[i]=='U' and x!=1:
        x-=1
    elif move[i]=='D' and x!=N:
        x+=1
print(x, y)

위의 코드들은 영상에서 나온 코드가 아닌 직접 짠 코드이고, 이 이후의 문제는 아직 스스로 풀지 못해서 풀 수 있게 되면 정리해 올릴 예정이다.

참고사이트 : https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC