1. 강의 자료
https://www.notion.so/4-c777c38a75654648bd8c35522c43fc75
[스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 4주차
매 주차 강의자료 시작에 PDF파일을 올려두었어요!
www.notion.so
2. 강의 듣기 전 계획과 생각
4주차 커리큘럼에는 트리, 힙, DFS, BFS 등 자료를 탐색하는데 자주 사용되는 알고리즘들이 담겨있었습니다. 동적계획법 같은 경우는 코드를 구현하면서 자주 문제가 발생하는 부분이라 주의깊게 들어야겠다고 생각했습니다.
3. 핵심 강의 내용
▶ 트리 : 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조.
☞ 비선형 자료구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있음.
선형구조는 자료를 저장하고 꺼내는 것에 초점, 비선형구조는 표현에 초점.
> Node: 트리에서 데이터를 저장하는 기본 요소
> Root Node: 트리 맨 위에 있는 노드
> Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
> Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
> Child Node: 어떤 노드의 하위 레벨에 연결된 노드
> Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
> Sibling: 동일한 Parent Node를 가진 노드
> Depth: 트리에서 Node가 가질 수 있는 최대 Level
▶ 힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리.
☞ 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조.
▶ 그래프 : 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구죠.
☞ 그래프는 연결 관계에 초점이 맞춰져 있음.
> 노드(Node): 연결 관계를 가진 각 데이터를 의미.정점(Vertex)이라고도 함
> 간선(Edge): 노드 간의 관계를 표시한 선.
> 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)
▶ DFS(깊이 우선 탐색) : 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색.
▶ BFS(너비 우선 탐색) : 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 BFS를 적용.
☞ DFS와 BFS의 차이점?
> DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구함. 따라서 공간을 적게 쓴다. 그러나 최단 경로를 탐색하기 쉽지 않음.
> BFS 는 최단 경로를 쉽게 찾을 수 있음. 모든 분기되는 수를 다 보고 올 수 있기때문. 그러나, 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있음.
▶ DP(동적 계획법) : 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘.
☞ 재귀 알고리즘과의 차이점?
> 문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있음. 그러나 다른 점은, 그 결과를 기록하고 이용한다는 점이다.
결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고, 문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)라고 칭함.
4. 문제풀이
▶ 농심 라면 공장
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
last_added_date_index = 0
max_heap = []
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
answer += 1
heappop = heapq.heappop(max_heap)
stock += -heappop
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))Comment : 힙에 대해 익숙하지 않았던 만큼, 힙으로 접근해서 해결하는데 애를 먹었습니다. 그냥 아무것도 모른채로 접근했으면 더 빠르게 풀 수 있었을 것 같기도 합니다. 역시 문제는 여러가지 관점에서 바라봐야한다는 것을 다시 한번 되새길 수 있었습니다.
▶ 샤오미 로봇 청소기
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]
]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
x = len(room_map[0])
y = len(room_map)
cnt = 1
room_map[r][c] = 2
room_queue = [[r, c, d]]
while room_queue:
r, c, d = room_queue.pop(0)
temp_d = d
for i in range(4):
temp_d = (temp_d + 3) % 4
temp_r, temp_c = r + dx[temp_d], c + dy[temp_d]
if 0 <= temp_r < y and 0 <= temp_c < x and room_map[temp_r][temp_c] == 0:
cnt += 1
room_map[temp_r][temp_c] = 2
room_queue.append([temp_r, temp_c, temp_d])
break
elif i == 3:
temp_r, temp_c = r + dx[(d + 2) % 4], c + dy[(d + 2) % 4]
room_queue.append([temp_r, temp_c, d])
if room_map[temp_r][temp_c] == 1:
return cnt
# 57 가 출력되어야 합니다!
print(get_count_of_departments_cleaned_by_robot_vacuum(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 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(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 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(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 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(6,2,0,current_room_map4))Comment : 오래걸렸습니다.. 하지만 해결했습니다. 비슷한 형식의 문제들을 풀어봤던 경험이 도움이 되었던 것 같습니다. 문제해결의 아이디어 중에 i = 3 즉, dx와 dy가 각각 (1, 0) 인경우에는 청소기가 후진을 해야하기 때문에 갈 곳이 없다고 생각해도 된다는 부분과 d의 방향에 따라 달라지는 dx, dy를 정의하는 부분이 어려웠습니다.
▶ CGV 극장 좌석 구하기
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]
fibo_memo[n] = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
return fibo_memo[n]
def get_all_ways_of_theater_seat(total_count, fixed_seat_array):
answer = 1
visited = []
fixed_array = []
for idx in range(1, total_count + 1):
if idx in fixed_seat_array:
fixed_array.append(len(visited))
visited.clear()
else:
visited.append(idx)
if visited:
fixed_array.append(len(visited))
for cnt in fixed_array:
answer *= fibo_dynamic_programming(cnt, memo)
return answer
# 12가 출력되어야 합니다!
print(get_all_ways_of_theater_seat(seat_count, vip_seat_array))
print("정답 = 4 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(9, [2, 4, 7]))
print("정답 = 26 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(11, [2, 5]))
print("정답 = 6 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(10, [2, 6, 9]))
seat_count = 9
vip_seat_array = [4, 7]
# 예전에 만들었던 fibo_dynamic_programming 에서 가져오면 됩니다!
memo = {
1: 1, # 이 문제에서는 Fibo(1) = 1, Fibo(2) = 2 로 시작합니다!
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
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
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))
print("정답 = 4 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(9,[2,4,7]))
print("정답 = 26 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(11,[2,5]))
print("정답 = 6 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(10,[2,6,9]))Comment : 문제해결의 아이디어를 우연치 않게 피보나치 수열로 증가한다는 것을 알게 되었습니다. 접근방법은 제 풀이와 튜터님의 풀이가 유사했지만 공간복잡도 측면에서는 튜터님의 코드가 조금 더 좋았던 것 같았습니다.
5. 4주차 강의를 통해 새롭게 알게된 점
아직 헷갈리는 부분이 많습니다. DFS, BFS, DP에 대해서 조금 더 자세히 파고들어야 할것 같습니다.
'All Development' 카테고리의 다른 글
| Unity) Lerp 의 사용법 (0) | 2023.10.28 |
|---|---|
| Sparta_algorithm_course_05) velog (1) | 2022.07.29 |
| Sparta_algorithm_course_03) velog (0) | 2022.07.14 |
| Sparta_algorithm_course_02) velog (1) | 2022.07.08 |
| Sparta_algorithm_course_01) velog (0) | 2022.06.30 |