그리디 알고리즘 (2) 썸네일형 리스트형 [Baekjoon] 백준 1789 '수들의 합' 문제풀이 파이썬, Python, 알고리즘 정리 📝 1789 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?. 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 🧐 풀이 S = int(input()) i = 1 sum = 0 cnt = 0 remain = 0 while 1 : sum += i i += 1 remain = S - sum if sum > S : break cnt += 1 print(cnt) 알고리즘 - Greedy (탐욕 알고리즘, 욕심쟁이 알고리즘), 최적해 찾기 Greedy Alogrithm Greedy는 사전적인 의미로 '탐욕스러운', '욕심많은' 이라는 뜻을 가지고 있다. 탐욕 알고리즘 또는 욕심쟁이 알고리즘 라고도 불린다. 미래를 생각하지 않고 선택의 순간마다 당장 눈앞에 보이는 최적의 선택을 하는 기법 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 그리디 알고리즘 해결 방법 선택 : 현재 상태에서 최적의 해답 선택 적절성 검사 : 선택된 답이 문제의 조건을 만족하는 지 확인 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다. 그리디 알고리즘 조건 그리디 알고리즘을 적용하기 위해서는 2가지 조건을 성립해야 한다. 1. 탐욕적 선택 속성 (Greedy Choice Prop.. 이전 1 다음
