[알고리즘] 스파르타 코딩 : 알고리즘 - 4주차(숙제)

숙제

Q1. 농심 라면 공장

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다.

원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에

해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고,

라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock,

밀가루 공급 일정(dates)과

해당 시점에 공급 가능한 밀가루 수량(supplies),

원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때,

밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환 하시오.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

 

A1.

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):
    count = 0
    last_added_date_index = 0 # 마지막으로 공급한 날짜
    max_heap = []

    # stock이 k보다 많아야 k날까지 버틸 수 있음
    # k날까지 버티기(재고가 k보다 많을 때까지)
    while stock <= k:
        # 재고(버틸 수 있는 날)가 공급 일자보다 작아질 때까지(공장이 멈추기 직전까지)
        while last_added_date_index < len(dates) and dates[last_added_date_index] <= stock:
            heapq.heappush(max_heap, -supplies[last_added_date_index])
            last_added_date_index += 1

        # 지나온 날 줄 가장 큰 말가루 수량을 담음(날짜는 상관 없음, 가장 큰 값만 가져오면 됨)
        count += 1
        heappop = heapq.heappop(max_heap)
        stock += -heappop

    return count


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))

 

---

Q2. 샤오미 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

 

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며,

1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다.

 

청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다.

지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

 

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력 조건

로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다.

이 때 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

또한 청소하고자 하는 방의 지도를 2차원 배열로 주어진다.

빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이라고 했을 때, 로봇 청소기가 청소하는 칸의 개수를 반환하시오.

 

A1.

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]
]

# amp = 0 : 청소 안 한 장소, 1 : 청소 못 하는 장소, 2 : 청소한 장소
# 북 동 남 서
# 위 오른쪽 아래 왼쪽
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_d_index_when_go_back(d):
    return (d + 2) % 4


def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
    n = len(room_map)       # 행 갯수
    m = len(room_map[0])    # 열 갯수
    count_of_departments_cleaned = 1  # 청소하는 칸의 개수
    room_map[r][c] = 2      # 현재 장소는 청소한 상태로 변경
    queue = list([[r, c, d]])   # 청소할 위치와 다음에 청소할 방향 큐에 담기

    # 큐가 비어지면 종료
    while queue:
        r, c, d = queue.pop(0)
        temp_d = d

        # 4방향 청소하기
        for i in range(4):
            # 방향 전환
            temp_d = get_d_index_when_rotate_to_left(temp_d)
            # 다음에 이동할 위치
            new_r, new_c = r + dr[temp_d], c + dc[temp_d]

            # 새로운 위치가 맵 밖을 벗어나지 않고 청소를 안 했다면
            if 0 <= new_r < n and 0 <= new_c < m and room_map[new_r][new_c] == 0:
                count_of_departments_cleaned += 1   # 청소한 횟수 ++
                room_map[new_r][new_c] = 2          # 청소하기
                queue.append([new_r, new_c, temp_d])# 큐에 담아서 다음에 위치 청소하게 하기
                break

            # 더이상 갈 곳이 없었던 경우
            elif i == 3:
                # 후진하기
                new_r, new_c = r + dr[get_d_index_when_go_back(d)], c + dc[get_d_index_when_go_back(d)]
                # 후진해서 청소할 곳 있나 찾기 위해 큐에 넣기
                queue.append([new_r, new_c, d])

                # 뒤가 벽인 경우
                if room_map[new_r][new_c] == 1:
                    return count_of_departments_cleaned


# 57 가 출력되어야 합니다!
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))

---

Q3. CGV 극장 좌석 자리 구하기

극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다.

공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.

 

예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다.

단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.

 

예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다.

그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

 

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

 

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다.

총 좌석의 개수와 VIP 회원들의 좌석 번호들이 주어졌을 때,

사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 반환하시오.

 

A1.

seat_count = 9
vip_seat_array = [4, 7]


# 예전에 만들었던 fibo_dynamic_programming 에서 가져오면 됩니다!
memo = {
    1: 1,  # 이 문제에서는 Fibo(1) = 1, Fibo(2) = 2 로 시작합니다!
    2: 2
}

# [1, 2] 옳기기 = [1, 2] [2, 1] 총 2개
# [1, 2, 3] 옮기기 = [1, 2, 3] [2, 1, 3] [1, 3, 2] 총 3개
# [1, 2, 3, 4] 옮기기 = [1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [2, 1, 3, 4] [2, 1, 4, 3] 총 5개
# [1, 2, 3, 4, 5] 옮기기 = [1, 2, 3, 4, 5] [1, 2, 3, 5, 4] [2, 1, 3, 4, 5] [2, 1, 3, 5, 4]
# [1, 2, 4, 3, 5] [2, 1, 4, 3, 5] [2, 1, 3, 4, 5] [1, 3, 2, 4, 5] 총 8개

# 2, 3, 5, 8... => 피보나치 수열 이용!
def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    return nth_fibo


def get_all_ways_of_theater_seat(total_count, fixed_seat_array):
    all_ways = 1
    current_index = 0

    # 시작 ~ 고정된 좌석 - 1까지의 좌석 이동 가능 횟수 구하기
    for fixed_seat in fixed_seat_array:
        fixed_seat_index = fixed_seat - 1
        count_of_ways = fibo_dynamic_programming(fixed_seat_index - current_index, memo)
        all_ways *= count_of_ways
        current_index = fixed_seat_index + 1

    # 고정된 좌석 + 1 ~ 끝 자리까지의 좌석 이동 가능 횟수 구하기
    count_of_ways = fibo_dynamic_programming(total_count - current_index, memo)
    all_ways *= count_of_ways
    return all_ways


# 12가 출력되어야 합니다!
print(get_all_ways_of_theater_seat(seat_count, vip_seat_array))

---

...

백준 문제보단 쉬울 거라고 생각했는데.................

갈 길이 멀구나....^^에반데

아니...

진짜 에반데

그래도 어떤 방식으로 이렇게 풀면 되겠는데?<라는 생각은 나긴 했었음

파이썬에 아직 어색해서 코드를 잘 구현하지 못했던 거...라고 생각하기엔 풀이 방법도 구체적으로 생각난 건 아니었음

그래도 규칙을 찾아보자라는 교훈을 얻었다.

...............파이팅!