목차
- CCW
- 제한된 소인수
- 케르베로스 밥먹이기
- 소코반
- 최소의 연료통
1. CCW
풀이
def solution(points):
p1, p2, p3 = points
x1, y1 = p1
x2, y2 = p2
x3, y3 = p3
val = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3)
if val == 0:
return 'LINE'
elif val > 0:
return 'CCW'
else:
return 'CW'Test case
# 테스트 1
입력값 〉 [[0, 0], [0, 10], [10, 5]]
기댓값 〉 "CW"
# 테스트 2
입력값 〉 [[-2, 3], [-2, 6], [-2, 9]]
기댓값 〉 "LINE"
# 테스트 3
입력값 〉 [[4, 7], [-3, 5], [2, 4]]
기댓값 〉 "CCW"2. 제한된 소인수
풀이
"""
* DP/수학문제입니다.
* Tabulation 방식으로 계산하면서, 현재까지 구한 값 중 작은 값에 *2, *3, *5한 값을 추가해 나갑니다.
* 값을 추가한 이후에는 2,3,5를 곱할 대상을 더 큰 값으로 바꾸어 줍니다.
"""
def solution(n):
dp = [0 for _ in range(n)]
dp[0] = 1
mult2, mult3, mult5 = 0, 0, 0
for i in range(1, n):
val2 = dp[mult2] * 2
val3 = dp[mult3] * 3
val5 = dp[mult5] * 5
dp[i] = min([val2, val3, val5])
if dp[i] == val2:
mult2 += 1
if dp[i] == val3:
mult3 += 1
if dp[i] == val5:
mult5 += 1
return dp[-1]
Test case
# 테스트 1
입력값 〉 10
기댓값 〉 123. 케르베로스 밥 먹이기
풀이
그리디 문제
"""
* 그리디 문제입니다!
* 가장 많이 먹는 머리 순으로 순서대로 주면, 최대한 양손을 많이 쓸 수 있습니다.
* 양손으로 먹이를 주는 것이 끝나면 나머지는 한손으로 주어야 합니다.
* 한 손으로 주는 것이 최소가 되게 하는것이 핵심!
"""
def solution(food):
food.sort(reverse=True)
count = 0
curr = food[0]
for f in food[1:]:
if f < curr:
curr -= f
count += f
else:
count += curr
curr = f - curr
count += curr
return countTest case
# 테스트 1
입력값 〉 [6, 3, 4, 5]
기댓값 〉 9
# 테스트 2
입력값 〉 [10, 4, 9, 6, 8, 1, 9, 4, 10, 4]
기댓값 〉 334. 소코반
풀이
"""
* 상자가 이동할 최단거리와, 상자를 움직일 플레이어의 최단거리를 함께 구하는 문제입니다.
* BFS, DFS의 조합으로 해결할 수 있으나, 여기에서는 A* 알고리즘으로 구현한 코드를 소개합니다.
* 참조 코드와 리트코드의 원본 문제를 참고해 주세요!
*
* 참조 코드: https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/2257156/Python3-A*-beat-100
* 원본 문제: https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/
"""from heapq import heappush, heappop
# 참조 코드: https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/2257156/Python3-A*-beat-100
def solution(map):
m, n = len(map), len(map[0])
for i in range(m):
for j in range(n):
if map[i][j] == 4:
target = (i,j)
if map[i][j] == 3:
box = (i,j)
if map[i][j] == 1:
person = (i,j)
def valid(pos):
nonlocal map, m, n
return 0 <= pos[0] < m and 0 <= pos[1] < n and map[pos[0]][pos[1]] != 2
def manhattan_dist(p1, p2):
return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def check(s, d, box):
open_set = [(manhattan_dist(s, d), 0, s)]
vis = {s, box}
while open_set:
_, dist, pos = heappop(open_set)
if pos == d:
return True
for new_pos in [(pos[0]+1, pos[1]), (pos[0]-1, pos[1]), (pos[0], pos[1]+1), (pos[0], pos[1]-1)]:
if valid(new_pos) and new_pos not in vis:
vis.add(new_pos)
heappush(open_set, (dist+1+manhattan_dist(new_pos, d), dist+1, new_pos))
return False
open_set = [(manhattan_dist(box, target), 0, box, person)]
vis = {box+person}
while open_set:
_, dist, box, person = heappop(open_set)
if box == target:
return dist
b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]
p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]
for new_box,new_person in zip(b_coord,p_coord):
if valid(new_box) and valid(new_person) and new_box+box not in vis and check(person, new_person, box):
vis.add(new_box+box)
heappush(open_set,(dist+1+manhattan_dist(new_box, target), dist+1, new_box, box))
return -1
Test case
# 테스트 1
입력값 〉 [[2, 2, 2, 2, 2], [2, 0, 2, 2, 2], [4, 0, 0, 0, 0], [2, 0, 2, 2, 0], [2, 3, 2, 2, 0], [2, 0, 2, 2, 0], [2, 1, 0, 0, 0]]
기댓값 〉 35. 최소의 연료통
풀이
"""
* 최대힙을 이용하여 풀이할 수 있는 문제입니다.
* 현재 갈 수 있는 장소 중 가장 큰 연료통을 찾아갑니다.
* 연료통을 더 얻지 않고 목적지에 도달할 수 있다면 곧바로 목적지로 갑니다.
* DP로 풀 수도 있지만, DP로 풀 경우 불필요한 연산이 많아집니다.
"""
from heapq import heappush, heappop
def solution(dest, start, station, fuel):
heap = []
N = len(station)
curr_fuel = start
curr_pos = 0
count = 0
for i in range(N + 1):
if i == N:
curr_target = dest
else:
curr_target = station[i]
curr_fuel = curr_fuel - (curr_target - curr_pos)
while curr_fuel < 0 and heap:
curr_fuel += -heappop(heap)
count += 1
if curr_fuel < 0:
return -1
if i < N:
heappush(heap, -fuel[i])
curr_pos = curr_target
return countTest case
# 테스트 1
입력값 〉 12, 6, [2, 3, 5, 10], [5, 2, 3, 1]
기댓값 〉 2출처
해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.
모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.
Comment