Q1. 농심 라면 공장 - heapq
라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.
해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.
현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환하시오.
dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.
import heapq
ramen_stock = 4
supply_dates = [4, 10, 15]
supply_supplies = [20, 5, 10]
supply_recover_k = 30
def get_minimum_count_of_overseas_supply(stock, dates, supplies, k):
answer = 0
idx = 0 # last added date index
max_heap = []
while stock < k:
# 현재 stock 으로 도달할수있는 모든 공급날짜를 일단 max heap 에 추가
while idx < len(dates) and stock >= dates[idx] :
heapq.heappush(max_heap, -supplies[idx])
idx += 1
# heapq 에서 가장 많은 밀가루 수 공급받기
stock += -heapq.heappop(max_heap)
answer += 1
return answer
print(get_minimum_count_of_overseas_supply(ramen_stock, supply_dates, supply_supplies, supply_recover_k))
print("정답 = 2 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15], [20, 5, 10], 30))
print("정답 = 4 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15, 20], [20, 5, 10, 5], 40))
print("정답 = 1 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(2, [1, 10], [10, 100], 11))Note:
Max Heap:
Heapq.heappush(list, -value_to_add)
Heapq.heappop(list)
Q2. 샤오미 로봇 청소기 - DFS
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
로봇 청소기는 다음과 같이 작동한다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
입력 조건
로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. 이 때 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.
또한 청소하고자 하는 방의 지도를 2차원 배열로 주어진다.
빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.
로봇 청소기가 있는 칸의 상태는 항상 빈 칸이라고 했을 때,
로봇 청소기가 청소하는 칸의 개수를 반환하시오.
-
현재 위치를 청소한다.
→ 현재 위치를 청소했는지 아닌지에 대해서 저장을 해야 합니다! -
현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
→ 이 문제는 "방향" 이라는 개념이 존재합니다. 즉, 왼쪽방향으로 회전한다는 개념을 구현해야 합니다.
이를 위해서 북, 동, 남, 서 순서를 정의해보겠습니다!
r c
북 -1 0
동 0 1
남 1 0
서 0 -1a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
→ 회전은 어떻게 구현할 수 있을까요? 왼쪽 방향으로 회전을 하기 위해서는
아까 만든 방향을 사용하시면 됩니다!
북쪽에서 왼쪽으로 회전하면? 서쪽이 됩니다. 즉, 0번째 인덱스가 3이 됩니다.
동쪽에서 왼쪽으로 회전하면? 북쪽이 됩니다. 즉, 1번째 인덱스가 0이 됩니다.
남쪽에서 왼쪽으로 회전하면? 동쪽이 됩니다. 즉, 2번째 인덱스가 1이 됩니다.
서쪽에서 왼쪽으로 회전하면? 남쪽이 됩니다. 즉, 3번째 인덱스가 2가 됩니다.
rotate 라는 함수를 쓰면 방향의 인덱스가 +3 % 4 한다는 것을 알 수 있습니다!
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
→ 현재 본 방향에서 청소할 곳이 없다면 다시 한 번 왼쪽으로 회전하라! 라는 의미입니다. 즉 회전하면서 모든 방향에서 청소할 곳이 있는지 확인하라는 의미입니다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
→ 모든 방향이 청소되어있다면 뒤로 한 칸 후진합니다.
후진도 방향에 따라 후진하는 게 다릅니다. 한 번 같이 생각해볼게요!
북쪽에서 후진하면? 남쪽이 됩니다. 즉, 0번째 인덱스가 2이 됩니다.
동쪽에서 후진하면? 서쪽이 됩니다. 즉, 1번째 인덱스가 3이 됩니다.
남쪽에서 후진하면? 북쪽이 됩니다. 즉, 2번째 인덱스가 0이 됩니다.
서쪽에서 후진하면? 동쪽이 됩니다. 즉, 3번째 인덱스가 1이 됩니다.
이걸 수식으로 나타내면 +2 % 4 입니다!
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
→ 만약 모든 방향을 다 봤는데 갈 곳이 없고 뒤에도 벽이라면 멈추면 됩니다!
이렇게 위의 개념들을 그대로 구현하시면 됩니다!
def clean_room(r, c, d, room_map):
# 북 동 남 서
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
n = len(room_map)
m = len(room_map[0])
cleaned = set()
def turn_left(direction):
# 0 = 북, 1 = 동, 2 = 남, 3 = 서 (same order as directions)
return (direction + 3) % 4
def simulate(r, c, d):
# 1. 현재 위치 청소 if not cleaned
if (r, c) not in cleaned:
cleaned.add((r,c))
# 2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 탐색
# a. 왼쪽에 아직 청소하지 않은 공간이 있다면, turn_left & clean
# b. 왼쪽 방향에 청소할 공간이 없다면 또 횐쪽 회전 후 2번
for _ in range(4):
new_d = turn_left(d)
# new 세로, new 가로
new_r, new_c = r + directions[new_d][0], c + directions[new_d][1]
if (new_r, new_c) not in cleaned and room_map[new_r][new_c] == 0:
simulate(new_r, new_c, new_d)
return # Exit after moving to a new position
# update d if 네방향 모두 이미 청소되어있을경우
d = new_d
# 네방향 모두 이미 청소 되어있을경우
# c. 바라보는 방향 유지한채로 한칸 후진후 2번으로 돌아가기
back_d = (d + 2) % 4
back_r, back_c = r- directions[d][0], c - directions[d][1]
# 후진가능경우
if room_map[back_r][back_c] == 0:
simulate(back_r, back_c, d)
simulate(r, c, d)
return (len(cleaned))
current_r, current_c, current_d = 7, 4, 0
current_room_map = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 57 / 현재 풀이 값 = ",clean_room(current_r, current_c, current_d, current_room_map))
current_room_map2 = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 29 / 현재 풀이 값 = ", clean_room(6,3,1,current_room_map2))
current_room_map3 = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 33 / 현재 풀이 값 = ", clean_room(7,4,1,current_room_map3))
current_room_map4 = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 25 / 현재 풀이 값 = ", clean_room(6,2,0,current_room_map4))Or
def clean_room(r, c, d, matrix):
# 북, 동, 남, 서 방향 정의 (0: 북, 1: 동, 2: 남, 3: 서)
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
n = len(matrix)
m = len(matrix[0])
cleaned = set() # 청소한 위치 저장
def turn_left(direction):
return (direction + 3) % 4
def simulate(r, c, d):
if (r, c) not in cleaned: # 현재 위치 청소
cleaned.add((r, c))
for _ in range(4):
d = turn_left(d) # 왼쪽으로 회전
next_r, next_c = r + directions[d][0], c + directions[d][1]
if (next_r, next_c) not in cleaned and matrix[next_r][next_c] == 0: # 청소하지 않은 공간이라면
simulate(next_r, next_c, d) # 전진 후 재귀적으로 청소
return
# 네 방향 모두 청소되어있거나 벽인 경우
back_r, back_c = r - directions[d][0], c - directions[d][1] # 후진
if matrix[back_r][back_c] == 0: # 후진 가능한 경우
simulate(back_r, back_c, d)
simulate(r, c, d)
return len(cleaned)or if using BFS
# 북 동 남 서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
# 방향 전환
def get_d_index_when_rotate_to_left(d):
return (d + 3) % 4
def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
n = len(room_map) # row
m = len(room_map[0]) # col
queue = deque([(r, c, d)])
cleaned = set()
cleaned.add((r, c)) # Start by cleaning the initial position
while queue:
r, c, d = queue.popleft()
was_cleaned = False
for _ in range(4):
d = get_d_index_when_rotate_to_left(d)
next_r, next_c = r + dr[d], c + dc[d]
# a
if 0 <= next_r < n and 0 <= next_c < m and room_map[next_r][next_c] == 0 and (next_r,next_c) not in cleaned:
cleaned.add((next_r, next_c))
queue.append((next_r, next_c, d))
was_cleaned = True
break # Break after successful clean to continue from this position
# 네 방향 모두 청소되어있거나 벽인 경우
if not was_cleaned:
back_r, back_c = r - dr[d], c - dc[d]
# if you can 후진
if 0 <= back_r < n and 0 <= back_c < m and room_map[back_r][back_c] != 1:
queue.append((back_r, back_c, d))
# if you cannot 후진
else:
break # If back is also a wall, stop the operation
return len(cleaned)Q3. CGV 극장 좌석 자리 구하기 - Dynamic Programming
극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다.
공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.
예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다.
단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.
예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고,
6번 좌석이나 8번 좌석에도 앉을 수 있다.
그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.
그런데 이 극장에는 “VIP 회원”들이 있다.
이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
예를 들어서,
그림과 같이 좌석이 9개이고,
4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다.
또한 <213465789> 와 <132465798> 도 가능한 배치이다.
그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.
오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다.
총 좌석의 개수와 VIP 회원들의 좌석 번호들이 주어졌을 때,
사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 반환하시오.
seat_count = 9
vip_seat_array = [4, 7]
memo = {
1: 1,
2: 2
}
def fibo_dynamic(n, memo):
if n in memo:
return memo[n]
# return fibo(n-1) + fibo(n-2)
nth_fibo = fibo_dynamic(n-1, memo) + fibo_dynamic(n-2,memo)
memo[n] = nth_fibo
return nth_fibo
def get_all_ways_of_theater_seat(total_count, fixed_seat_array):
ways = 1
prev_vip = 0
# before each vip seat from the start
for vip in fixed_seat_array:
count = vip - prev_vip - 1
ways *= fibo_dynamic(count, memo)
prev_vip = vip
# last vip seat to the last seat
count = total_count - vip
ways *= fibo_dynamic(count, memo)
return ways
# 12가 출력되어야 합니다!
print(get_all_ways_of_theater_seat(seat_count, vip_seat_array))if not using Dynamic Programming,
def fibo(n):
if n == 1:
return 1
if n == 2:
return 2
return fibo(n-1) + fibo(n-2)
```