오늘의 글귀
아침에 일어나기가 어렵다면 마음속으로 이 생각을 하라. 나는 인간으로서의 의무를 다하기 위해 깨어나야 한다. 이 세상에 나를 존재하게 하는 일을 하기 위해 일어나야 한다. 그런데 이렇게 짜증을 낼 필요가 있는가? 나는 기껏 이부자리나 끌어안고 살기 위해 태어났는가? 이것이 내게 주어진 낙이란 말인가? 나는 분투하기 위해 태어났는가, 아니면 자기 위해 태어났는가?
(마르쿠스 아우렐리우스, 명상록)
회고
오늘은 오전 10시부터 공부 시작. 오전부터 머리 아픈 알고리즘을 하고 싶지 않아서, 알고리즘을 복기할 겸 정리글을 작성하여 블로그에 포스팅했다. [[다익스트라 알고리즘(Dijkstra Algorithm)]]과 [[플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)]]. 둘 다 최단 경로 탐색 알고리즘이지만, 다익스트라는 그리디 알고리즘 기반이고, 플로이드 워셜은 DP 기반이라 성격이 완전히 다르다. 또 다른 최단 경로 알고리즘으로 벨만 포드 알고리즘이 있는데 그건 내일 공부해봐야겠다
오후 3시부터 2시간 동안 코딩테스트를 또 진행했다. 카테고리는 어제와 똑같이 그래프이다. 첫 번째 문제인 "1012번: 유기농 배추"를 10분만에 풀고 제출했는데 시간초과가 떴다. 시간을 단축시키기 위해 로직을 이리저리 바꿔봤지만 계속해서 시간초과만 띄운채로 1시간이 흘렀다. 도저히 이유를 알 수 없어서 솔루션을 봤더니 로직이 거의 똑같았다. 유일하게 다른 점이 BFS 함수 내에서 노드에 대한 방문처리에 관한 코드였다.
def bfs(x, y):
queue = deque()
queue.append((x, y))
graph[y][x] = 0
while queue:
cur_x, cur_y = queue.popleft()
# graph[cur_y][cur_x] = 0 # 기존 위치. 시간초과됨.
for k in range(4):
next_x = cur_x + dx[k]
next_y = cur_y + dy[k]
if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
continue
if graph[next_y][next_x]:
queue.append((next_x, next_y))
graph[next_y][next_x] = 0 # 통과된 위치대체 노드에 대한 방문처리를 미리 하든 나중에 하든 아무 상관이 없을텐데 왜 시간초과가 나는건지 이해할 수가 없었다. 그래서 우선 문제를 제꾸고 다음 문제를 풀기 시작했다. 2번 "17086번: 아기 상어2" 문제를 30분만에 클리어. 그러나 2번을 풀고나니 종료시간 10분 전이었다. 1번에서 75분이나 잡아먹어서 뒷 문제를 보지도 못한채 모의 코테가 끝났다. 아쉽기 그지없다. 3번도 풀만했는데. 1번의 시간초과 이유를 도저히 알 수 없어서 동료들에게 물어보고나서야 이유를 알 수 있었다. queue에 노드를 집어넣을 때 방문처리를 해줘야 나중에 동일한 노드를 넣는지 체크할 수가 있다. 그렇지 않으면 queue에 계속해서 방문했던 노드가 쌓이면서 급수적으로 연산량이 늘어나는 것이다. 알고나니 속이 시원하다. 모의 코테 덕분에 미리 이런 것을 알 수 있었다. 취업 코테에서 이유도 모른채 이런 실수를 했을 걸 생각하면 아찔하다. 이 실패를 온전히 남겨두고 다음에는 실수하는 일이 없도록 해야겠다.
오늘 저녁은 간단히 편의점 라면과 주먹밥. 오랜만에 까르보불닭을 먹으니 맛있다. 2+1이니 나중에 또 먹어야지. 저녁 식사 이후부터는 채용 공고를 살펴보았다. 현대 소프티어에서 채용 공고 광고 이메일이 온 터라 흥미가 갔다. 동료들과 여러 채용 공고를 둘러보며 이런저런 이야기를 나누었고, 한번 현대 오토에버 코테라도 쳐보자는 이야기가 나왔다. 최신 출제 동향도 알 수 있고, 미리 자소서 작성하는 연습도 할 수 있으니 좋은 생각인 것 같다. 모집 마감은 5월 2일. 서류 제출자 모두에게 코테 기회가 있으니, 주말 중으로 자소서를 적당히 휘갈기고 지원할 예정이다. 코테도 통과하면 기분이 좋을 것 같다.
오후 10시 30분. 채용 공고를 보고나니 알고리즘 문제에 집중이 안 되어서 일찍 운동을 가기로 했다. 같은 헬스장을 다니는 블루반 동료 2명고 함께, 오늘은 하체 운동을 하기로 했다. 같이 하니 즐겁구나. 1시간 만에 운동을 조지고 돌아오는 길에 아이스크림 할인점에서 요깃거리를 사고 복귀했다. 이 동네 아이스크림 할인점은 처음 왔는데 과자가 생각보다 싸고 종류가 많아서 자주 애용해야겠다.
정글에 와서 어려움을 겪는 점은 바로 지갑 사정이다. 생각보다 카카오 26주 적금 나가는게 빡센데다가 동료들과 같이 밥을 시켜먹으려면 또 한번에 많이 나가니까, 부담이 조금씩 커지고있다. 아직 훈련수당이 나오려면 2주는 더 기다려야해서 걱정이 이만저만이 아니었는데, 방금 해결책을 찾았다. 카카오 정기예금에서 긴급출금으로 조금만 빼면 해결이다! 당장 밥 먹을 돈만 빼면 괜찮다. 햇반과 라면이 객실에 쌓여있긴 하지만, 매일 2번씩 햇반만 먹으면 좀 질리는게 사실이다. 한번씩 맛있는것도 먹고 해야한다. 개소리고 그냥 맛있는거 먹고싶다. 내일 저녁은 한솥 파스타 먹어야겠다.
TIL
- DFS/BFS 탐색 시 주의해야 할 사항이 추가됐다. 다음 노드를 큐에 추가할 때, 반드시 방문처리를 해줘야 한다! 그렇지않으면, 이미 큐에 존재하는 노드를 다시 큐에 쌓게되면서 탐색해야할 경우가 급수적으로 증가하게 된다. 결국 시간초과 엔딩이다. 반드시 주의하자.
- 큐에 너무 긴 리스트를 늘리면서 담으려고 하면 시간이 터지거나 메모리가 터진다. 리스트 재할당에 시간이 소요되고, 리스트를 큐에 넣다빼면서 또 시간이 소요되면서 이중으로 시간이 터진다. python으로 그래프 탐색 시, 시간초과를 굉장히 주의하며 풀어야겠다는 것을 몸소 느꼈다.
