알고리즘 4주차

농심 라면 공장

❓

Q. 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환 하시오. dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

stock = 4
dates = [4, 10, 15]
supplies = [20, 5, 10]
k = 30

# 다음과 같이 입력값이 들어온다면,
# 현재 재고가 4개 있습니다. 그리고 정상적으로 돌아오는 날은 30일까지입니다.
# 즉, 26개의 공급량을 사와야 합니다!
# 그러면 제일 최소한으로 26개를 가져오려면? supplies 에서 20, 10 을 가져오면 되겠죠?
# 그래서 이 경우의 최소 공급 횟수는 2 입니다!

stock = 4
dates = [4, 10, 15]
supplies = [20, 15, 10]
k = 30

# 이 때! 다음과 같이 입력값이 들어온다면 어떻게 해야 할까요?
# supplies 에서 20, 15를 가져오는게 가장 최고의 상황입니다!
# 즉, 4일과 10일에 공급량을 가져오는 게 좋습니다!

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):
    # 풀어보세요!
    return


print(get_minimum_count_of_overseas_supply(ramen_stock, supply_dates, supply_supplies, supply_recover_k))

주의할 점: 그냥 제일 큰 값만 가지고 와서 넣으면 안된다. 재고가 다 떨어지기 전에 한번이라도 공급을 받아야 하기때문이다. 재고가 바닥나는 시점 이전까지 받을 수 있는 라면 중 제일 많은 라면을 받는 것이 목표이다.

현재 재고의 상태에 따라 최곳값을 받아야 한다.(동적으로 변경), 두번째로 제일 많은 값만 가져가면 된다.

데이터를 넣을 때마다 최댓값을 동적으로 변경시키며 최소/최댓값을 바로 꺼낼 수 있는 자료구조가 필요하기에 '힙' 자료구조를 쓰면 된다.

stock이 k보다 많아야지 정상적으로 시도가 가능하다.

# 정답
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
    current_day_index = 0 # 오늘이 며칠인지에 따라서 가지고 올 수 있는 supply 수가 다르기에
    max_heap = [] # 현재 공급량이 떨어지지 않는 선에서 가장 많은 공급량을 가지고 올 수 있게

    while stock < k:
        # date를 기준으로 반복. 왜냐면 지금 내가 재고가 바닥난 상황인지 아닌지를 알기 위함
        for date_index in range(current_day_index, len(dates)):
            if dates[date_index] <= stock: # 현재 스톡이 4고 요일이 10이면 10 < 4라서 조건이 안 맞기에
                heapq.heappush(max_heap, -supplies[date_index])
            else:
                current_day_index = date_index
                break
        answer += 1
        stock += -heapq.heappop(max_heap)
    return answer


print(get_minimum_count_of_overseas_supply(ramen_stock, supply_dates, supply_supplies, supply_recover_k))

샤오미 로봇 청소기

❓

Q. 문제 설명 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 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로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다. 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이라고 했을 때, 로봇 청소기가 청소하는 칸의 개수를 반환하시오.

r, c, d = 7, 4, 0
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]
]

# 코드 스니펫
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]
]


def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
    return


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

모든 칸을 탐색해야 하기에 전부 탐색하고 모든 칸을 탐색해야하기에 BFS를 활용하는 것이다.

현재 위치를 청소한다 - 청소하는 곳의 정보를 기록
1. 2차원 배열이라 visited를 쓰지 않고 배열에 표시
1. 0 은 청소하지 않은 장소
1. 1은 청소하지 못하는 장소
1. 2는 청소한 장소로 표시 함으로써 정보를 기록

현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.
1. 방향 개념이 필요하기에 배열 내에서 방향을 표시하기로함
1. 북쪽으로 가면 로우가 -1 컬럼은 0
1. 동쪽으로 가면 로우 0 컬럼 1
1. 남쪽으로 가면 로우 1 컬럼 0
1. 서쪽으로 가면 로우 0 컬럼 -1
1. dr과 dc라는 변수에 담음
1. dr = [-1, 0, 1, 0]
1. dc = [0, 1, 0, -1]

왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면 그 방향으로 회전하고 다음 한칸을 전진하고 1번부터 진행
1. 회전 개념이 필요함
1. dr, dc에서 북:0, 동:1, 남:2, 서:3
1. 북쪽에서 왼쪽 회전 서: 0 → 3
1. 동쪽에서 왼쪽 회전 북: 1 → 0
1. 남쪽에서 왼쪽 회전 동: 2 → 1
1. 서쪽에서 왼쪽 회전 남: 3 → 2
1. get_d_index_when_rotate_to_left() 함수를 구현. 3을 더한다음에 %4

왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
1. 현재 본 방향에서 청소할 곳이 없다면 다시 왼쪽으로 회전하라는 의미

모든 방향이 청소가 되어있거나 벽인 경우에는 바라보는 방향을 유지한채로 한 칸 후진을 하고 2번으로 돌아간다.
1. 모든 방향이 청소되어 있다면 뒤로 한칸 후진
1. 북 뒤로 돌면 남: 0 → 2
1. 동 뒤로 돌면 서: 1 → 3
1. 남 뒤로 돌면 북: 2 → 0
1. 서 뒤로 돌면 동: 3 → 1
1. 함수 구현. 2를 더한 다음에 %4

네 방향 모두 청소가 이미 되어있거나 벽이면서 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

우리가 마지막으로 반환해줘야 하는 것은 청소한 칸의 갯수. count_of_departments_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]
]

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]]) # 현재 위치와 방향을 전부 기록해놓고 어떻게 탐색할지 고민이 필요하기에 r,c,d 저장

    while queue:
        r, c, d = queue.pop(0)
        temp_d = d # 방향은 계속 돌릴 것이기에 임시 변수

        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 current_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(temp_d)], c + dc[get_d_index_when_go_back(temp_d)]
                queue.append([new_r, new_c, temp_d])
                if current_room_map[new_r][new_c] == 1:
                    return count_of_departments_cleaned

    return count_of_departments_cleaned


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

CGV 극장 좌석 자리 구하기

❓

Q. 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 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]

# 코드 스니펫
seat_count = 9
vip_seat_array = [4, 7]


def get_all_ways_of_theater_seat(total_count, fixed_seat_array):
    return


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

[1, 2, 3, 4, 5, 6, 7, 8, 9]에서 4와 7이 고정되어 있을때 앉을 수 있는 여러 가지의 가능한 개수에 대해 알아보는 문제

1 2 3

5 6

8 9

를 어떻게 마음껏 옮겨서 만들 수 있는 모든 경우의 수

좌석 [1, 2]: [1, 2], [2, 1] → 2개

좌석 [1, 2, 3]: [1, 2, 3], [2, 1, 3], [1, 3, 2] → 3개 # [3, 2, 1]은 3도 두 자리 옮기고 1도 두자리 옮기니 말이 안됨

좌석 [1, 2, 3, 4]: → 5개

...

피보나치 수열과 비슷한 것을 확인 가능

다른 점은 F(2) = 2, F(3) = 3 인점

그렇다면 왜 피보나치 수열일까?

총 좌석의 자리가 i개 있다고 가정하면

1 2 3 4 5 ... i 까지 있는 것

i 번째 좌석에 i번 티켓을 가지는 사람이 앉는 경우

i 번째 티켓을 가진 사람이 옮길 수 있는 경우는 i-1만 가능(1칸만 가능하기에)

1 2 3 4 5 .. i-1 i

만약 i-1 티켓을 가지는 사람이 i-2에 앉게된다면 쭉쭉 않다 보면 1자리(i자리)가 없어져 버린다. 그렇기에 i-1이 i-2에 앉으면 안된다. 무조건 i-1이 i 자리에 앉아야 한다.

i가 고정이 되어있으면 i-1 좌석들을 맘껏 배치할 수 있음. (경우의 수)

i와 i-1이 바꿔서 않게되면 i-2 좌석을을 맘껏 배치할 있음.(경우의 수)

F(N) = N명의 사람들을 좌석에 배치하는 방법 = N-1명의 사람들을 배치하는 방법 + N-2명의 사람들을 배치하는 방법 = F(N-1) + F(N-2)

이렇기에 피보나치 수열이다.

그리고 각 독립적인 값에 대해서 곱의 법칙을 적용해주면 전체 경우의 수.

4와 7이 고정되어 있으므로

1 2 3 F(3) = 3

5 6 F(2) = 2

8, 9 F(2) = 2

3 * 2 * 2 = 12가 모든 가지의 경우의 수

# 정답
seat_count = 9
vip_seat_array = [4, 7]
memo = {
    1: 1,
    2: 2
}


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 #초기 값 1개로 정함. 아무 자리도 안 움직이면 1개이기에.
    current_index = 0
    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
    # for 문이 끝났을때는 7까지해서 끝나기에 뒤에 8 9  부분이 생략된다. 그래서 끝나고도 한번 더 해줘야 한다.
    count_of_ways = fibo_dynamic_programming(total_count - current_index, memo)
    all_ways *= count_of_ways
     # 7까지 갔으면 마지막 9 - 7 = 2
    return all_ways


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

알고리즘 실전 - 2020 카카오 신입 개발자 블라인드 채용 1차 코딩테스트 - 1 (0)	2021.02.16
알고리즘 실전 - 2019 상반기 LINE 인턴 채용 코딩테스트 (0)	2021.02.15
알고리즘 4주차 - Dynamic Programming (0)	2021.02.10
알고리즘 4주차 - BFS, DFS (0)	2021.02.08
알고리즘 4주차 - 그래프 (0)	2021.02.05

우기의 알

우기의 알