성덕이의 개발공간

1. 문제설명 2. 문제 조건 3. 문제해결 아이디어 오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인한다. 공포도를 하나씩 확인하며 "현재 그룹에 포함된 모험가의 수"가 "현재 확인하고 있는 공포도보다 크거나 같다면 이를 그룹으로 설정" 4. 답안 #모험가의 수 n = int(input()) promulgate = list(map(int, input().split())) answer = 0 people = 1 #올림차순 정렬 promulgate = sorted(promulgate) for i in range(n): if(promulgate[i] = i: #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상일 때 result += 1 count = 0 print(result)

1. 문제 설명 2. 문제 해결 아이디어 대부분의 경우 '+'보다는 'x'가 값을 크게 만든다. 다만 두 수중에서 하나라도 0, 1일경우 곱하기 보다는 더하기를 수행하는 것이 효율적이다. 즉, 하나라도 1 이하인 경우에는 더하며 두 수가 모두 2이상인 경우에는 곱해야한다. 3. 답안 각각 분리해서 계산해야 하므로 문자열로 받는 것이 좋겠다. 앞뒤를 비교해서 앞뒤합이 4이하일 경우 더한다. 맨 앞 인덱스의 수를 잡고 계속 연산해나간다. data = input() result = int(data[0]) for i in range(len(data) - 1): if(int(data[i]) + int(data[i+1])

1. 문제 설명 2. 문제 해결 아이디어 주어진 N에 대하여 최대한 많이 나누기를 수행 N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다. N = 25, k = 3일경우 3. 정당성 분석 N이 아무리 큰 수여도, k로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있다. 항상 1에 도달하게 된다. (최적의 해 성립) 4. 코드 #N, K을 공백으로 기준으로 구분하여 입력 N, K = map(int,input().split()) result = 0 while True: target = (N // K) * K result += (N - target) N = target #더이상 나누어 떨어지지 않으면 if N < K: break result += 1 N //= ..

그리디 알고리즘(탐욕법) 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 최적의 해를 구하기 예제) 그리디 알고리즘은 이처럼 매 상황에서 최고의 상황만 선택한다. 일반적인 상황에서 최적의 해를 보장할 수 없다. 코딩테스트의 경우 이처럼 그리디 알고리즘으로 푸는 것이 최적의 해가 나오도록 설계되어 있다. 정당성 분석을 진행한다. 문제1 : 거스름 돈 문제1 : 1. 문제 해결 아이디어 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 준다. N원을 거슬러 줘야 할 때, 가장 먼거 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 준..