공부 기록

✏️ 문제 문제 파악조건은 다음과 같다.팔 수 있는 계란의 수고객의 수 고객의 수 > 달걀의 수, 팔 수 있는 계란의 수 = 달걀의 수수익책정한 가격 고객이 제안한 가격이 경래가 책정한 가격보다 커도 책정한 가격으로 팔 수 밖에 없다.고객들에게 달걀을 딱 하나만 팔 수 있다. 알고리즘그리디 알고리즘정렬 코드import sysinput = sys.stdin.readlinen,m = map(int, input().split())cus = sorted([int(input()) for _ in range(m)], reverse=True)price = 0revenue = 0for i in range(min(n, m)): if revenue

✏️ 문제 문제 파악일단 첫 날을 1일로 계산하고 이장님을 다 자라고 다음날에 부르므로 각각 +1 씩 해준다. 그 후 다 심을 때까지의 날짜가 필요하므로 n개를 다 심으면 (n-1)일 후이므로 날짜에 (n-1)을 더해준다.그 후 내림차순 정렬하여 맨 앞에 있는 배열 요소가 0이 될 때까지 날짜가 필요하므로 배열[0]을 더해준다. 이때 처음 배열에 (n-1)일 후의 남은 날짜를 넣으려고 할 때 for 반복문을 2개 사용하면 시간 초과가 생기므로 이를 넣기 쉽게 하기 위해서 내림차순 정렬을 해주었다. 알고리즘그리디 알고리즘정렬  코드import sysinput = sys.stdin.readlinen = int(input())tree = list(map(int, input().split()))day = 1tr..

✏️ 문제 문제 파악꾸러미 중에 제일 작은 가격이 공짜이므로 큰 금액을 공짜로 받으면 이득이므로 꾸러미에 제일 작은 가격과 그 가격과 별로 차이 나지 않는 가격들끼리 묶어놓는 게 좋다. 그래서 정렬을 사용한 후 3의 배수 번째의 위치에 있는 가격들이 공짜이므로 그 가격들 제외하고 더하는 방식으로 풀었다. 알고리즘그리디 알고리즘정렬  코드n = int(input())line = []tip = 0for i in range(n): line.append(int(input()))line.sort(reverse=True)for i in range(n): if line[i]-(i+1-1) > 0: tip += line[i]-(i+1-1)print(tip)

✏️ 문제 문제 파악꾸러미 중에 제일 작은 가격이 공짜이므로 큰 금액을 공짜로 받으면 이득이므로 꾸러미에 제일 작은 가격과 그 가격과 별로 차이 나지 않는 가격들끼리 묶어놓는 게 좋다. 그래서 정렬을 사용한 후 3의 배수 번째의 위치에 있는 가격들이 공짜이므로 그 가격들 제외하고 더하는 방식으로 풀었다. 알고리즘그리디 알고리즘정렬  코드n = int(input())price = 0milk = []for i in range(n): milk.append(int(input()))milk.sort(reverse=True)for i in range(0, n): if (i+1) % 3 != 0: # 3번째의 위치빼고 다 가격을 지불 price += milk[i]print(price)

✏️ 문제 문제 파악제일 중요한 건 이런 식으로 같은 index에 있는 문자끼리 묶어서 그 열에서 제일 많이 사용되는 문자를 s에 추가하는 것이 포인트이다.제일 많은 사용되는 문자가 문자열과 비교해서 다르면 Hamming Distance += 1 하는 식으로 코드를 짜면 쉽게 풀 수 있다.문자열에서 가장 많이 나오는 문자를 가져오기 위해선 collections.Counter를 사용하면 된다. 알고리즘그리디 알고리즘구현문자열브루트포스 알고리즘  코드from collections import Countern, m = map(int, input().split())hamming = 0ary = []char_ary = [[] for _ in range(m)] for i in range(n): ary.append..

✏️ 문제 문제 파악처음에는 현재 위치를 기준으로 현재 위치가 중간에 있으면 앞뒤로 (현재위치-길이/2)부터 (현재위치+길이/2)까지 사과가 떨어지는 위치에 해당되면 거리를 더하지 않고 해당되지 않으면 거리를 더하고 이런 방식으로 코드를 짜려고 했다.  근데 하다보니 복잡하고 경우의 수가 너무 많은 것 같아서 결국 포기.. 바구니의 왼쪽 위치와 오른쪽 위치를 저장해두고바구니의 왼쪽 위치보다 사과의 위치가 작으면 이동거리 = (바구니의 왼쪽 위치 - 사과의 위치)바구니의 오른쪽 위치보다 사과의 위치가 크면 이동거리 = (사과의 위치 - 바구니의 오른쪽 위치)그 외의 경우는 가만히 있어도 바구니 위치에 사과의 위치가 해당 (들어옴)라고 푸는 게 훨 편했다.. 알고리즘그리디 알고리즘구현  코드n,m = map..

✏️ 문제 문제 파악일단 'H'를 기준, 경우의 수를 3가지로 나눴다.H의 위치가 K보다 작을 경우: H를 기준으로 좌로 K만큼 비교할 때 배열 범위를 벗어난다.H의 위치가 K보다 크고 N-K보다 작을 경우: H를 기준으로 좌우로 K만큼 비교할 수 있다.H의 위치가 N-K 크거나 같을 경우: H를 기준으로 우로 K만큼 비교할 때 배열 범위를 벗어난다.이때  i-k가 0보다 작으면, i+k가 n보다 크면 배열 범위를 벗어나므로 처리를 해주어야 한다! 알고리즘그리디 알고리즘  코드n, k = map(int, input().split())ary = list(map(str, input()))start = 0end = 0for i in range(len(ary)): if ary[i] == 'H': if ..

✏️ 문제 문제 파악문제 그대로 불만도를 최소를 하기 위해선 본인이 원하는 등수와 많이 차이나면 안되므로 차례대로 정렬해준다.그 후 예상 등수와 실제 등수를 빼서 절댓값을 불만도에 더해주면 된다. 이때 그냥 input()을 쓴 상태로 하면 시간 초과가 뜨므로 sys input()을 쓰든가 언어를 python3 대신 pypy3를 쓰면 같은 코드라도 통과된다!! 알고리즘그리디 알고리즘정렬  코드import sysinput = sys.stdin.readlinen = int(input())ary = []dis = 0for i in range(n): ary.append(int(input()))ary.sort()for i in range(n): if ary[i] != i+1: dis += abs(ary[i..

✏️ 문제 문제 파악보자마자 아 그냥 find랑 rfind 써서 인덱스로 비교하면 되겠구나 했는데 결국 풀지 못했다.질문 게시판에 있는 모든 반례UCPCCUCPPCUUCPCCUCPCUPCPC를 적용해봤을 때 다 잘 나왔는데 .. 그래서 주어진 문장이 "UPCP" 문자열의 index로 비교하여 차례대로 나오는 지 확인하는 방법으로 풀었다. 알고리즘그리디 알고리즘문자열  코드실패한 코드 - 반례 좀 찾아주세요 .. s = input()c_index = -1p_index = -1for i, char in enumerate(s): if char == 'P' and i 성공 코드s = input()target = "UCPC"index = 0for char in s: if char == target[idx]..

그리디 알고리즘? 최적해를 구하는 데 사용되는 알고리즘의 한 유형으로 문제를 해결하는 과정에서 현재 상황에서 가장 좋다고 생각되는 선택을 반복적으로 하는 방식이다.즉 전체적인 최적해를 고려하지 않고 현재 단계에서 가장 좋은 선택을 하는 것을 반복하여 최종적인 해결책을 찾는 알고리즘이다.이 알고리즘은 각 단계에서의 최적 선택이 결국 전체 문제에 대한 최적 해결책을 보장할 수 있을 때 유효하다.  특징탐욕적 선택 속성 (Greedy Choice Property): 각 단계에서 현 시점에서 가장 최적인 선택을 한다.최적 부분 구조 (Optimal Substructure): 문제의 최적 해결 방법이 부분 문제들의 최적 해결 방법으로 구성될 수 있다.장점간단하고 직관적: 구현이 간단하고 이해하기 쉬운 편빠른 수행..