오늘은 알고리즘 주차의 마지막 날이다. 마지막 시험을 진행했다.
아침에 정글 티셔츠 한정 판매가 있어서 구매했다. 밤식빵이 맛있다고 소문나서 사봤는데, 진짜 맛있다.
9:00 ~
DP와 그리디 알고리즘에 대해 복습했다. 코드를 외워야한다.
3.동전문제 와 10.동전 0 문제로 복습을 했다.
10:00 ~ 12:00
시험 수행 후 발표 진행.
12:00 ~ 13:00
발표 때문에 시간이 좀 걸려서 끝나고 밥먹었다.
13:30 ~
오늘의 발제 시작(알고리즘 주차 종료)
대충 내용은 아래와 같다.
나중에 연차가 되면 컴퓨터 관련된 지식이 중요하게 되는 최적화 위주로 한다.
c언어와 친숙해 질것이다. 특히, 포인터를 이해할 수 있는 시간이 될 것이다.
우분투 18.04 이상이어야 한다.
도커를 써도 된다. 나는 써보고 싶긴하다.
(옵션)
과제에서
깃에서 리포지트리를 만들어서 과제를 진행해야한다. 개인 또는 팀원 도커로 하실분은 밑에 있는 도커 내용으로 진행하면 된다. 그대신 기존의 도커는 끊어야함.
이번에도 시험도 올린다. 시험 형식이 살짝 다르니, LMS 확인 후 진행
일주일하면서 2분 동안 작업에 대해 자랑할만한거, 어려웠던거 등을 발표해야한다.(모두)
컴퓨터는 1장 ~ 3장 보면된다.
14:00 ~ 15:00
운영진 티타임 참여하고 왔다. 생각보다 유용한 정보와 여러 방법을 알게 되었다.
아이패드에 내용이 있으니 추후에 정리해서 올려보겠다.
16:00 ~ 17:00
코드리뷰 진행중
17:00 ~ 18:45
운동을 하고 오늘은 배달 음식을 먹기로하여 샤워를 바로하고 왔습니다.
이후 코드리뷰 내용을 마저 마무리 하여 완료했습니다. 내 리뷰에 대해 답장을 남기고 머지후 삭제 했습니다.
18:45 ~ 20:30
인프런 이동욱 CTO님의 강의가 있어 듣고 왔습니다.
20:30 ~ 21:00
강의 평가, 팀원 평가 등 4주차 마무리 진행
21:00 ~22:00
굽네치킨 고추바사삭 식사
22:00 ~ 02:30
도커 관련 환경 세팅
도커 하고 깃을 했는데, 이렇게 하고 나니 도커가 안된다. 이유를 모르겠어서 내일 하겠다. 벨로그하고 노션 정리해야된다.
오늘만큼은 일찍 갈려했는데, 도커를 처음 만져봐서 시간이 좀 오래걸렸다.
이렇게 총 4주차에 걸쳐 알고리즘 공부가 끝났다. 심오하기도 하고 새로운 C언어에 대해 배울 생각에 좋다.
이하 오늘 배웠던 추가적인 알고리즘에 대해 정리했다.
[추가] 1번 14916 거스름돈
https://www.acmicpc.net/problem/14916
# 2, 5만 써서 거스름돈에 맞게 거실러 줘야한다.
# 포인트는 큰 수 부터 돌아가면서 동전의 개수는 최소가 되게끔하는 것이다.
# 그러면 그리디가 적합할 것이다.
import sys
input = sys.stdin.readline
n = int(input())
coin = [5, 2]
def coin_cnt(n, coin):
count = 0
# 0 예외사항 처리
if n == 0:
return 0
for i in range(n // coin[0], -1, -1): # coin[0] = 5
remain = n - coin[0] * i # 5를 최대한 뺌
if remain % coin[1] == 0: # 2로 나눈 나머지가 0일때
return i + (remain // coin[1]) # 기존의 5의 몫과 2의 몫을 더한값을 리턴
return -1 # 나누지 못했을때 예외처리
print(coin_cnt(n, coin))[추가] 2번 1890 점프
https://www.acmicpc.net/problem/1890
import sys
input = sys.stdin.readline
N = int(input())
board = [list(map(int, input().strip().split())) for _ in range (N)] # 2차원 배열을 만든다.
dp = [[0] * N for _ in range(N)] # 초깃값으로 0을 넣어준다
dp[0][0] = 1 # 시작지점은 1
for i in range(N):
for j in range(N):
if dp[i][j] > 0 and board[i][j]: # 0보다 크거나 범위 안에 라면 점프 시행
jump = board[i][j]
if i + jump < N: # 세로축 N보다 점프량이 적을시 기존꺼에서 더해서 갱신
dp[i + jump][j] += dp[i][j]
if j + jump < N: # 가로축 N보다 점프량이 적을시 기존꺼에서 더해서 갱신
dp[i][j + jump] += dp[i][j]
print(dp[N-1][N-1])[추가] 3번 1379 강의실 2
https://www.acmicpc.net/problem/1379
import sys
import heapq
input = sys.stdin.readline
n = int(input())
lectures = []
for _ in range(n):
num, start, end = map(int, input().split())
lectures.append((start, end, num))
# 시작 시간 기준으로 정렬, 시작 시간이 같으면 종료 시간 기준으로 정렬
lectures.sort(key=lambda x: (x[0], x[1]))
# 우선순위 큐: (강의 종료 시간, 강의실 번호)
pq = []
# 강의실 번호 할당을 위한 변수
room_number = 0
# 각 강의에 배정된 강의실 번호를 저장할 딕셔너리
lecture_room = {}
for start, end, num in lectures:
# 현재 강의의 시작 시간보다 작거나 같은 종료 시간을 가진 강의실이 있다면 재사용
if pq and pq[0][0] <= start:
_, room = heapq.heappop(pq)
else:
# 새로운 강의실 필요
room_number += 1
room = room_number
# 현재 강의의 종료 시간과 배정된 강의실 번호를 우선순위 큐에 추가
heapq.heappush(pq, (end, room))
# 해당 강의 번호에 배정된 강의실 번호 저장
lecture_room[num] = room
# 최소 강의실 개수 출력
print(room_number)
# 각 강의 번호에 해당하는 강의실 번호 출력
for i in range(1, n + 1):
print(lecture_room[i])
