아보카도 Blog
TIL 11일차: 깃 활용 기초 강의, oracle mySQL 다운, 알고리즘 4주차 연습문제 본문
깃 활용 기초 강의가 올라와져 있길래... 1주차 조금 들었다. 깃허브 데스크탑말고도 소스트리로 깃을 관리할 수 있구나.
계정 원래 있던 걸 삭제하고 다시 만드느라 계정이 꼬여서 땀 좀 났다. 있는 계정 다 삭제하고 다시 만듦.
수요일에 있을 DB 특강 때문에 오라클에서 만든 mySQL을 다운받느라 생각보다 시간을 많이 썼다.
로그인 하지 않고 다운받을 수도 있었는데 그걸 보지 못한 나는 처음에 asw랑 오라클이랑 연결하기 위해서
신용카드 등록도 전부 하고 난리를 쳤지만, paid version 인 asw랑만 히트웨이브라는 연결 할 수 있다는 안내를 받고
바로 오라클 회원가입... 그리고 다운로드 후 회원가입 한 정보랑 연동... 이 복잡한 과정을 왜 거친건지.
아무튼 mySQL, DBeaver까지 잘 깔아놨으니 수요일 특강 들을 준비 끝.
그리곤 알고리즘 4주차 숙제들을 했다. 숙제하다보니 4주차 전체에서 연습했던 코드들을 복습하고자
힙과 DFS, BFS, 동적계획법 연습문제들을
1.주석달린 힌트를 보고 2. 정답 보고 3. 힌트도 정답도 없이 오롯이 나 혼자 써보는 반복 연습을 세 번씩 거쳤다.
하루 종일 걸림.
첫번째 숙제는 농심 라면 공장에서 밀가루 퍼오는 거였다.
1단계: stock이 k보다 크거나 같아야 하며, 그 전까지 while로 밀가루 추가해야 한다.
2단계: supplies의 값들을 꺼내서 heap에 넣는다. 이를 위해 max_heap = [] initialize 해줘야함.
last_added_data_index = 0으로 초기값을 설정해주고,
이 값과 stock과의 관계, len(dates)와의 관계에 따라 while구문의 조건을 설정해주어야 한다.
3단계: heap에 있는 값들을 빼서 stock에 추가해주어야 한다. stock += -heappop
이 때 우린 최대의 양을 빼오는 것이므로 pop이나 push할 땐 -를 붙여주는 것을 잊지 말아야 한다.
들어가 있는 값들 중 최대 공급량을 stock에 추가한다. heappop이라는 변수에 놓는다. heapq.heappop(max_heap)
한 번씩 공급량을 추가했으니 answer도 하나씩 증가한다. answer += 1
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
max_heap = []
last_added_date_index = 0
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))
두 번째 숙제는 샤오미 로봇 청소기... 공간 감각이 부족해서인지 ㅠㅠ 얘는 절대 내가 혼자 생각할 수 없는 풀이법이었다.
일단 구하려는 값은 로봇 청소기가 청소하는 칸의 개수이므로, 갈 수 있는 칸을 전부 탐색해야 한다.
BFS로 풀어야 함을 알 수 있다.
우선 로봇이 바라보는 방향을 다음과 같이 설정해준다.
| 0 | 북 |
| 1 | 동 |
| 2 | 남 |
| 3 | 서 |
그 다음, 현재 위치를 청소했는지, 아닌지에 대해 저장해야 하므로
2차원 배열에 맵 정보를 저장한다.
| 0 | 청소하지 않은 장소 |
| 1 | 청소하지 못하는 장소 |
| 2 | 청소한 장소 |
그리고 가장 중요한 단계!
왼쪽 방향부터 회전하므로 북,동,남,서 순서로 정의한다.
| r (북쪽으로부터 높이) | c (서쪽으로부터 너비) | |
| 북 | -1 | 0 |
| 동 | 0 | 1 |
| 남 | 1 | 0 |
| 서 | 0 | -1 |
즉 dr = [-1, 0, 1, 0] 이고, dc = [0, 1, 0, -1]이다.
2번부터는 조건이 까다로워 진다. 방향 전환과 후진했을 때 각각으로 새로운 함수를 만들어야 한다.
1) 방향 전환
왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면,
그 방향으로 회전한 다음 한칸 전진하고 1번부터 진행한다.
| 이 방향에서 | 왼쪽으로 회전하면 | 이 방향으로 변한다. | 원래 인덱스에서 | 바뀐 인덱스로 변한다. |
| 북 | -> | 서 | 0 | 3 |
| 동 | -> | 북 | 1 | 0 |
| 남 | -> | 동 | 2 | 1 |
| 서 | -> | 남 | 3 | 2 |
얘를 수식으로 나타내면 +3%4
2) 후진
네 방향 모두 청소되었거나 벽일 때,
바라보는 방향을 유지한 채로 한 칸을 후진하고 2번으로 돌아간다.
| 이 방향에서 | 후진하면 | 이 방향으로 변한다. | 원래 인덱스에서 | 바뀐 인덱스로 변한다. |
| 북 | -> | 남 | 0 | 2 |
| 동 | -> | 서 | 1 | 3 |
| 남 | -> | 북 | 2 | 0 |
| 서 | -> | 동 | 3 | 1 |
이를 수식으로 나타내면 +2%4 이다.
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]
#방향 전환 (2-a)
def get_d_index_when_rotate_to_left(d):
return (d + 3) % 4
#후진 (2-c)
def get_d_index_when_go_back(d):
return (d + 2) % 4
def get_count_of_departments_cleaned_by_robot_vacumm(r, c, d, room_map):
n = len(room_map)
m = len(room_map[0]) #room_map이 2차원 배열이니 열과 행 각각의 길이를 n,m로 설정한다.
count_of_departments_cleaned = 1
room_map[r][c] = 2
queue = list([[r,c,d]]) #2차원 배열이니 괄호 두 개 연속해서 쓰기
# 탈출 조건: 큐가 빌 때까지 반복
while queue:
r, c, d = queue.pop(0) #queue의 첫 데이터로 initialize
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]
#1. 현재 위치를 청소한다. 현재 위치 청소했는지 여부를 저장. 2차원 배열에 맵 정보 저장.
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
#2-c 후진
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_vacumm(current_r, current_c, current_d, current_room_map))
세 번쨰 숙제는 CGV 극장 좌석 자리 구하기였다.
동적 계획법 배울 때 썼던 피보나치 수열 함수를 그대로 갖다 쓰면 되는 거였다. 혼자 못 품...
피보나치인걸 어떻게 아느냐...
고정 좌석 개념이 있고, 변경 가능한 좌석들의 규칙을 발견하면 된다는 것인데, 이런 규칙 찾기까지 시간이 꽤 걸린다.
일반 피보나치와 다르게, 극장 좌석 자리 변경에서는 F(2)가 2임에 유의하자.
솔직히 get_all_ways_of_theater_seat 함수 부분은 아직 잘 모르겠다. 정신 멀쩡할 때 다시 보는 걸루...
seat_count = 9
vip_seat_array = [4, 7]
#피보나치 수열: 3주차에서 배운 fibo_dynamic_programming 가져오기
memo = {
1: 1,
2: 2 # 일반 fibo와 다른점: Fibo(1) = 1, Fibo(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]))