04_ 피보나치 수열 및 여러 문제들(hard)

input = 20


def fibo_recursion(n):
    # 구현해보세요!

    if n==1 or n==2:
        return 1

    return fibo_recursion(n-1) + fibo_recursion(n-2)


print(fibo_recursion(input))  # 6765

피보나치 수열은 재귀함수로 간단하게 구현할수 있다... 하지만 굳이 n-1, n-2 이렇게 저장하면서 하면 될꺼같은데 이렇게 계산량을 늘릴 필요가 있나? 싶던 찰나에

 

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}


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

    # 구현해보세요!



print(fibo_dynamic_programming(input, memo))

바로 나오더라 ㅋㅋ.. 동적프로그램을 만들어서 계산을 엄청 줄인 모습이다. 

 

 

 

이어서 문제를 풀었다. 

 

 

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):
    # 풀어보세요!
    heap = []
    need_stock = k - stock
    count = 0

    for suppliy in supplies:
        heapq.heappush(heap,suppliy * -1)

    sum_need_stock = 0
    while sum_need_stock < need_stock:
        sum_need_stock += heapq.heappop(heap) * -1
        count +=1

    return count


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

첫번째 문제는 비교적 쉬웠다. heap을 이용하여 간단하게 클리어

 

 

두번째 문제가 진짜 어려웠는데..

문제길이부터 어지러움

아직 백준 실버레벨정도만 풀어봐서 항상 어느정도 자신감에 차있던 나는... 이리저리 고민하고 한시간 두시간정도 고민하다가 결국 반포기했다.

 

결국 어느정도 참고해서 풀어봤다. ( 최대한 안보고 풀려했음)

 

queue 구조를 써야한다는 것과 방향전환에 대한 어느정도 아이디어를 캐치하고 푸니 풀만했다.

 

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 rotate_to_left(d):
    return (d+3) % 4

def 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])
    room_map[r][c] = 2
    count =1
    queue = [[r,c,d]]

    while queue:
        r,c,d = queue.pop(0)
        temp_d = d


        for i in range(4):
            temp_d = rotate_to_left(temp_d)
            new_r = r + dr[temp_d]
            new_c = c + dc[temp_d]

            if room_map[new_r][new_c] == 0:
                count +=1
                room_map[new_r][new_c] = 2
                queue.append([new_r,new_c,temp_d])
                break #???

            elif i == 3:

                temp_d = go_back(temp_d)
                new_r, new_c = r + dr[temp_d], c + dc[temp_d]
                queue.append([new_r,new_c,d])   #왜 여기가 d가 들어가야 하지? << 그래야 프로그램이 끝난다?!?
                # 서,남,동을 확인 한담에 결국 첫위치로 돌아오기때문에 고정된 d가 필요하다!

                if room_map[new_r][new_c] == 1:
                    return count




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

세번째 문제는 

 

이런 문제였다. 확률과 통계 방식을 쓰면 되겠지 생각하고 고정 자리의 사람들을 빼고 [ [1,2,3] , [5,6] ,[8,9]] 식으롬 ㅏㄴ든다음에 그사람들끼리 공식쓰면 되겠네! 라고생각했는데 거기서 막혀버렸다.

수학적 한계(?) 에 부딪혀서 답을 약간 참고했더니 피보나치 수열이 나온다고 한다. 그래서 냉큼 적용해서 풀었다.

 

seat_count = 9
vip_seat_array = [4, 7]

memo = {
    1: 1,
    2: 1
}
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):

    non_vip_lst = []
    non_vip_small_lst = []
    count = 1

    for person in range(1,total_count + 1):

        if person not in fixed_seat_array:
            non_vip_small_lst.append(person)
        else :
            non_vip_lst.append(non_vip_small_lst)
            non_vip_small_lst = []

    non_vip_lst.append(non_vip_small_lst)

    for non_vip_people in non_vip_lst:

        count *= fibo_dynamic_programming(len(non_vip_people)+1,memo)





    return count


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

끝!