1. 내 코드# 각 부서가 신청한 금액만큼을 모두 지원# 최대 몇 개의 부서def solution(d, budget): total = 0 # 적은 금액부터 차례로 더해서 budget 이 커버 가능한 최대 개수 return for i, req in enumerate(sorted(d)): total += req # total 이 budget 을 넘을 경우 if total > budget: return i # total 이 budget 보다 작을 경우 return len(d) sort 를 써서 복잡도는 배열길의 n 의 O(nlogn) 이 된다.일차 반복문 -- O(n)합 및 비교 연산 -- O(1)=> 최..
1. 내 코드for 문에서 리스트를 직접 수정할 경우 수정 직후 반복문이 끝나게 된다.그래서 lost=[3,4] reserve=[4,3] 케이스에서 3만 없어지고 4는 남게 됨.이럴 경우, [:] 를 써서 리스트 카피본으로 반복문을 돌리면 반복문이 끝까지 다 돌 수 있다. 내 코드의 복잡도는 이중 반복문 (X) 과 sort (log) 로,L (lost size), R (reserve size) 라고 할 때,O(L x R + LlogL) 이다.def solution(n, lost, reserve): answer = 0 # 여벌 체육복 중 하나만 도난당했을 경우 for l in lost[:]: if l in reserve: lost.remove(l) ..
# N이 1이 될 떄까지 1 혹은 2 과정을 수행해야 하는 횟수의 최솟값# 1) N-1# 2) N/K -- N이 K로 나누어떨어질 떄에만 선택 가능def until_one(): n, k = map(int, input("25 5 --").split()) result = 0 while n != 1: if n % k == 0: n /= k else: n -= 1 result += 1 return resultprint(until_one())'''# K로 가능한 한 많이 나눴을 때 가장 빠르게 N=1 만들 수 있다.# N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식# N, K를 공백으로 구분하여 입력받기n, ..
# 배열의 수들을 M번 더하여 가장 큰 수를 만드는 법칙.# 단, 특정 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수는 없음.# 인덱스가 다른데 값이 같을 경우 서로 다른 값으로 간주함.# N: 배열 크기, M: 숫자 더하는 횟수, K: 연속해서 더할 수 있는 횟수# N, M, K 공백으로 구분하여 입력 받기n, m, k = map(int, input().split())# N개의 자연수 공백으로 구분하여 입력 받기data = list(map(int, input().split()))max_value = max(data) # 가장 큰 수data.remove(max_value)next_max = max(data) # 두 번째로 큰 수result = 0cnt = k# 가장 큰 수를 더하는데,..
그리디 알고리즘이란?어떠한 문제가 있을 때, 단순 무식하게, *탐욕적으로 푸는 알고리즘.(탐욕적: 현재 상황에서 가장 좋은 것만 고르는 방법)현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 즉, 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형.단, 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야한다.창의력이 중요함! 그리고 문제 풀이를 위해 해법을 찾을 때, 이것이 정당한지 검토해야 답을 도출할 수 있다.문제 유형 파악이 어렵다면 그리디 알고리즘을 의심하고,오랜 시간 고민해도 그리디 알고리즘으로 해결방법을 찾을 수 없다면, 그때는 다른 알고리즘 방법을 떠올려보다. # 여러 개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임# 행을 선택 -> 가장 숫자가 작..
