그리디
[백준 파이썬] # 13305 주유소
Siver IV # 13305 주유소 그리디 알고리즘 링크 : https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 N = int(input()) D = list(map(int, input().split())) # Distance P = list(map(int, input().split())) # Price C = 0 # Cost M = 1000000001 # Minimum Distance C += D[0]*P[0] # D, P의..
[코드업 파이썬] # 3120 리모컨
코드업 그리디 문제 # 3120 리모컨 링크 : https://codeup.kr/problem.php?id=3120&rid=0 리모컨 현재 온도a 와 목표 온도b가 입력된다. ( 0
[백준 파이썬] # 1541 잃어버린 괄호
Silver II # 1541 잃어버린 괄호 그리디 알고리즘 링크 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 a = input().split('-') # '-' 기준으로 분리 li = [] for i in a: cnt = 0 i = i.split('+') # 각 i를 '+' 기준으로 분리 for j in i: cnt += int(j) # 계산을 위해 숫자형으로 바꿔야 함 li.append(cnt) n = li[0] for i..
[백준 파이썬] # 1931 회의실 배정
Siver II # 1931 회의실 배정 그리디 알고리즘 유형 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 N = int(input()) time = [] for i in range(N): start, end = map(int, input().split()) time.append([start, end]) time = sorted(time, key = lambda a : a[0]) # start 기준으로 오름차순 정렬 time = sorted(time, key = lambda a : a[1]) # end 기준으로 오름차순 정렬 ## 오름차순 정..
[이코테 자료구조] 2. 그리디 알고리즘 & 구현
그리디 알고리즘 by 나동빈님 링크 : https://www.youtube.com/watch?v=2zjoKjt97vQ 그리디 알고리즘(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 풀이의 정당성 분석이 중요 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다 많은 코딩 테스트에서 제시되는 문제 유형 중 하나 ※ 예시 문제 : [거스름 돈, 곱하기 혹은 더하기, 모험가 길드] 최적의 해를 빠르기 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적..
[백준 파이썬] # 11047 동전 0
Silver II # 11047 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 N, K = map(int, input().split()) count = 0 coin = [] for i in range(N): A = int(input()) coin.append(A) coin = sorted(coin, reverse=True) for i in coin: count +=..