문제 최단거리 문제인데도 파블로프의 개마냥 dfs 조졌다가 실패하고, 문제 카테고리를 보고 알았다. 물론 벨만 포드라고 적혀있는걸 보고는 '벨만 포드라고?'라고 생각했는데, 바로 아차싶었다. 소요시간 중에 음수가 있기 때문에 최단 거리를 찾으면 되는 거라고 생각했다. 이전 문제와 같이 벨만 포드가 기억이 안나 구글링하여 코드를 작성했는데, 94%에서 시간 초과가 떠서 한 시간 정도 고민하다 결국 gg치고 질문 검색 탭을 찾아갔다. 이 글을 보고도 처음에는 무슨 말인가 이해가 되지않아서 정답 코드와 해설이 있는 블로그를 구글링했는데, 이 분의 해설을 보고 문제의 함정과 왜 코드를 저렇게 썼는지 이해할 수 있었다. 벨만 포드에서는 소요 시간이 음수인 엣지를 사이클 마냥 도는 경우가 있는지를 찾는데, 문제에 ..
분류 전체보기
문제 처음에는 dfs로 가능할까? 하고 시도해보려고 했는데, 그냥 문제에서 대놓고 '최단 거리'라고 언급해준 거 최단 거리로 푸는 게 맞겠다 하고 최단 거리로 해결했다. 물론 다익스트라가 기억이 안나서 다른 블로그 참고해서 푼다고 30분이나 걸렸다. (다익스트라는 유튜브 동빈나 님이 운영하는 블로그를 참고했다.) 처음에는 파티 열리는 장소를 시작으로 잡고 다익스트라 한번 돌리면 되겠다라고 생각했는데 예제부터 답이 다르게 나오길래 문제를 다시 읽었다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. 그리고 왕복 시간 중 가장 많이 소비된 시간을 구하는 문제여서, 거리를 저장하는 배열 dist도 2차원으로 바꾸고, 다익스트라도 모든 마을을 출발점으로 돌렸다. #include #i..
이전 기수의 1주 차 미션이었던 숫자 야구 게임이 2주 차로 나왔다. 처음에는 제공된 라이브러리와 테스트 코드를 보는데 이해가 안 돼서 이거부터 이해하고 넘어갔다. mock 객체를 써서 테스트하는 방식을 써본적이 없으니 이해하는데 좀 시간이 걸릴 뻔했는데, mock과 관련된 것들을 구글링 하여 읽고 나니 금방 이해할 수 있었다. 이번 주차는 과제하는 동안 느낀 것보다는 끝나고 나서 친구의 훈수를 듣고 느낀 게 많았다. 훈수 몇 개를 좀 요약하자면, 기능에 대한 이해를 잘못하고 있다. 예외에 대한 기능 목록은 어디 갔냐? 무의미한 테스트 코드가 많다. 일관성을 지켜라. Util 클래스로 뺄 수 있는 것들은 객체 생성 말고 빼는 게 낫지 않냐. 예외를 구체화시켜라. 클래스 기능에 안 맞는 메소드들이 있다. ..
문제 문제를 읽고 생각난 건 두 가지였다. 그래프 DFS 그래서 dfs를 구현하고, 전체 정점에 대해서 dfs를 수행했다가 시간 초과로 틀렸다. 입력 vertex의 범위가 2개에서 10만 개였기 때문에, 시간 초과는 당연했다. 한 50분 고민하고, 밥 먹으면서도 고민해도 딱히 좋은 방법이 떠오르지 않아 '질문 검색' 탭에서 글을 보다가 이 글을 보고 해결했다. 처음에는 마지막 댓글을 보고도 갸우뚱 했는데, 조금 생각해보니 이해할 수 있었다. 1에서 X까지의 거리가 1에서 갈 수 있는 최대 거리 max_distance 라고 하자. 그렇다면 X에서 출발하면 1을 거쳐 다른 곳으로 또 이동이 가능하기 때문에 이는 max_distance 보다 크다. 라고 이해했다. 코드 #include #include std:..
