체뚱로그

풀이 시간: 43분 시간 복잡도: O(n^3) 공간 복잡도: O(n^2) 참고 자료: https://ongveloper.tistory.com/181 문제 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다. 예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5, 6은 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다. 이로부터 얻어내야 하는 경로표는 다음과 같다. 경로표는 한 집하장에서 다른 집하장으로 최..

풀이 시간: 35:02 시간 복잡도: O(n^3) 공간 복잡도: O(n^2) 참고 자료: https://velog.io/@yoohoo030/%EB%B0%B1%EC%A4%8011562-%EB%B0%B1%EC%96%91%EB%A1%9C-%EB%B8%8C%EB%A0%88%EC%9D%B4%ED%81%AC 문제 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공사가 진행되면서 어떻게 한 건진 알 수 없지만 일방통행만 가능한 길이 많이 늘고 말았다. 컴퓨터과학과 학생 남규는 전공 수업을 듣고 교양 수업을 들으러 가던 중 길을 잃어 3일 밤낮을 헤매다가 공학관에서 종합관으로 가는 길..

풀이 시간: 1:32:14 시간 복잡도: O(N^2) 공간 복잡도: O(N^2) 참고 자료: https://blog.naver.com/PostView.naver?blogId=gustn3964&logNo=222330297504 문제 엄청난 벼락을 맞아 많은 전선들이 끊어져 현재 전력 공급이 중단된 상태이다. 가장 심각한 문제는 1번 발전소에서 N번 발전소로 가는 중간의 전선이 끊어진 것이기에 일단 이 두 발전소를 다시 연결하는게 현재 해결해야할 첫 번째 과제이다. 발전소는 1번부터 N번까지 번호로 매겨져 2차원 격자 좌표 위에 있다. 그리고 몇몇 전선은 보존된 채 몇몇 발전소를 잇고 있다. 문제는 현재 전선과 발전소의 위치가 주어졌을 때 최소의 전선 길이를 추가로 사용하여 1번 발전소와 N번 발전소를 연결..

풀이 시간: 2:15:06 시간 복잡도: O(n^3 + n^2) = O(n^3) // floyd_warshall()의 3중 for문 + main()의 2중 for문 공간 복잡도: O(n^2 + n) = O(n^2) // dist 공간 복잡도 O(n^2) + item 공간 복잡도 O(n) 참고 자료: https://velog.io/@yyj8771/Python-백준-14938번-서강그라운드 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못..

풀이 시간: 30:46 시간 복잡도: O(N+M+N^3) = O(N^3) // floyd_warshall()의 O(N^3) 공간 복잡도: O(N^2) // party_hall의 공간 복잡도 참고 자료: https://chanhuiseok.github.io/posts/algo-50/ 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io 문제 파티를 좋아하는 민호는 끝없이 파티가 열리는 놀이동산 "민호월드"를 세웠다. 처음에는 한개의 파티장만을 가지고 있는 작은 놀이동산이었지만, 사람들의 점점 많이 찾아와 파티장을 증축했고 현재는 N개의 파티장을 가진 큰 놀이동산이 되었다. 민호는 파티장을 증축할때마다 편의를 위해 새로운 파..

풀이 시간: 01:38:37 시간 복잡도: O(M+N*N+N) = O(N^2) 단방향 경로 추가 O(M) + while문은 큐가 비어있을 때까지 반복하므로, 최악의 경우 모든 도시를 방문 O(N) * for문은 현재 도시와 연결된 도시 확인, 최악의 경우 한 도시에 모든 도시가 연결 O(N) + result 값 출력, 최대 N이므로 O(N) 공간 복잡도: O(N*M+N) = O(NM) one_way_route 크기 O(M) + result의 최대 크기는 N이므로 O(N) + shortest_route 크기 O(N) 참고 자료: https://kimjingo.tistory.com/57 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 ..