파이썬 그리디

문제 설명 모험가 길드에서 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 위기 대처능력이 떨어집니다. 공포도가 X인 모험간는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있습니다. N 명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 최댓값을 구하는 프로그램을 작성하세요. # N = 5이고, 각 모험가의 공포도가 [ 2 3 1 2 2 ] 라면 그룹 1에 공포도가 1,2,3인 모험가를 넣고, 그룹 2에 공포도가 2, 2 인 모험가를 넣게 되면 2개의 그룹을 만들 수 있다. 모든 모험가를 특정한 그룹에 넣을 필요는 없다. 입력 예시 출력 예시 5 2 3 1 2 2 2 문제 해결 아이디어 오름 차순 정렬 후 공포도가 낮은 모험가 부터 확..

문제 설명 각 자리 숫자(0~9)로만 이뤄진 문자열 s가 주어졌을때, 왼쪽부터 오른쪽까지 하나씩 모든 숫자를 확인하며 숫자사이에 'X' 혹은 '+' 연산자를 넣어 만들어 질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 단 모든 연산은 왼쪽부터 순서대로 이루어진다. 문제 해결 아이디어 두 수 중에 하나라도 0 or 1이면 더하기를 수행, 예외 경우는 곱하기수행 풀이 : O(N)의 시간 복잡도 data = input() result= int(data[0]) for i in range(1,len(data)): num=int(data[i]) if num

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 보르는 방법, 닫순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 꼭 필요! 거스름돈 문제 카운터에는 거스름돈으로 사용할 500원, 100원, 50원 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, N은 10의 배수 해결 방법 - 최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 준다. >> N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러주고 이후 단위도 똑같이 반복 - 최적의 해가 보장되는 이유 : 큰 단위가 항상 작은 단위의 배수이기 때문! >> 800원을 ..