본문 바로가기

전체 글

 (125)
11779 최소비용 구하기 2 이 문제는 처음에 플로이드로 풀려했으나, 접근이 틀렸다. 왜냐하면 플로이드는 O(V^3)이기 때문에 정점이 최대 1000개 이면 당연히 시간초과가 난다.. 따라서 O(VlgE)의 시간복잡도를 갖는 다익스트라를 사용하여 접근해야 한다. 일반적인 다익스트라는 최소비용을 구하는 로직이 대부분이지만 문제에서는 경로도 출력하는걸 요구하고 있다. 다익스트라에서 경로를 출력하기 위해서는 다음 vertex로 가는 최단경로를 업데이트할 때 기록해두고 역추적 방식으로 구현할 수 있다! 정답 코드에선 path라는 vector 타입으로 사용하였다. 정답코드 더보기 #include #include #include #include #define INF 987654321 #define MAX_V 1001 using namespac..
13549 숨바꼭질 3 꽤 고민한 문제였고, 질문 검색으로 힌트를 얻을 수 있었는데 문제가 된 부분은 다음과 같다. BFS를 통한 최단거리를 구하려 했으나, 오답이라고 뜸 문제에서 순간이동하는 경우에 시간이 0초가 걸리기 때문에 가중치를 고려해야 함 BFS 최단거리는 가중치가 동일하다는 가정하에 정상 동작하기 때문에 오답 조금 더 생각해보면, 반복문에서 N == K일 때 종료되기 때문에 순간이동으로 도달하지 않은 경우 최단거리가 아님을 알 수 있다. 가중치를 적용하여 우선순위 큐를 돌리면 시간이 오래걸림 디버깅한 결과, 연산 개수가 많아서 시간이 오래걸리는 걸로 보여, 다음과 같이 수정했다. 우선순위 큐 대신 덱(deque)를 사용하여 순간이동 하면 push_front를 하도록 했다. N > K인 경우, *2 +1 연산이 무의..
11399 ATM 문제의 조건 맨 뒷 줄의 대기자는 앞 줄의 대기자들의 인출시간을 다 더한 값 + 자기가 걸리는 시간만큼 걸리게 된다. 모든 대기자들의 인출 시간 중 최솟값을 구해야 함 접근 단순하게 풀기 단순하게 더하여 구할 수 있다. 정답코드 더보기 #include #include #include using namespace std; int N; int GetWaitingTime(vector& v) { int sum = 0; for (int i = 0; i > N; vector v(N, 0); for (int i = 0; ..

티스토리툴바