본문 바로가기

전체 글74

귤고르기 k개의 귤을 담을때 크기의 종류가 최소가 될수있게 담을때귤종류의 최솟값 구하기1. 각 귤 크기별로 몇개인지 담는다 { 1 :2 } 1이 두개 이런식으로2. 개수가 많은 순으로 내림차순해서 정렬한다3. 귤의 개수와 종류 => 두개의 변수생성해서 k개와 비교하기   -개수와 종류 두개를 안셈def solution(k,tangerine): graph = {} for i in tangerine: if i not in graph: graph[i] = 1 else: graph[i] += 1 graph = sorted(graph.items(),key=lambda x:x[1],reverse=True) cnt = 0 for i i.. 2024. 6. 24.
구명보트 문제이해보트의 최대 제한무게가 나오고 사람들의 무게배열이 나올때(보트에 최대 2명까지만 탈 수 있음)모든사람들이 보트를타고 이동할때필요한 최소한의 보트개수구하기*무게가가장작은사람 + 무게가 가장높은사람 묶어서 생각def solution(people,limit): people.sort() i,j = 0, len(people)-1 while i 2024. 6. 24.
거스름돈(dp) 문제이해n원을 만들려고 할때 money로 만들수 있는 방법의 수 구하기dp(동적계획법)1. dp[i]는 i원을 만드는 방법의 수def solution(n, money): # dp 배열 초기화, 0부터 n까지 저장 dp = [0] * (n + 1) dp[0] = 1 # 0원을 만드는 방법은 1가지 # 각 동전에 대해서 for coin in money: # dp 배열을 업데이트 for i in range(coin, n + 1): dp[i] += dp[i - coin] return dp[n]# 예제 입력n = 5money = [1, 2, 5]print(solution(n, money)) # 출력: 4  amount = 123 # .. 2024. 6. 23.
*지형이동 문제이해N*N격자의 판에 적힌 숫자가 각 칸의 높이이고모든칸을 다방문해야하고상하좌우로 이동하며 높이가 height이하이면 비용이 안드고 이상일 경우는 두칸의 높이의 차 만큼 비용발생=> 모든 칸을 방문하기 위해 필요한 최소비용구하기1. 모든칸을 방문해야한다 -> 방문배열만들어서 체크2.최소비용 => import heapq다 min_heap 만들어서 [(0,0,0)] # 비용과 시작 행열을 담고3. while min_heap:  import heapqdi = [-1,0,1,0]dj = [0,1,0,-1]def solution(land,height): n = len(land) total_cost = 0 visited = [[False]*n for _ in range(n)] min_hea.. 2024. 6. 18.