여느 날처럼 에줍사 스터디를 진행하다가 그래프 탐색 문제에 대해 논의를 하던 중 나머지 스터디원들은 BFS로 접근을 했지만, 혼자 다익스트라로 접근을 했던 적이 있습니다. "왜 다익스트라를 떠올렸을까?"라는 생각을 한 결과, 다음과 같은 잘못된 기저가 깔려있다는 것을 알 수 있었습니다.시간복잡도 : Dijkstra BFS 또한 완전탐색으로 최단 거리를 찾는데 시간이 오래 걸릴 것이라 생각함알고리즘 특성 차이이번 회고를 통해 아래와 같이 잘못된 정보들을 바로잡으려합니다.추상적인 시간복잡도두 알고리즘의 동작 방식조건에 따른 수행 방식 BFS와 Dijkstra에 대한 정리는 이전에 정리해 두었던 글이 있으니 참조용으로 링크만 올려두겠습니다.https://infinitecode.tistory.com/13 [알고..

문제 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 풀이 3차원 방문체크를 활용한 Dijkstra 풀이 문제이해 문제를 읽고 예제를 보고 이해를 하려는데 개인적으로 상당히 난해했음. 일단 동작과정은 아래와 같음. #이라는 문에 대해서 어느 방향에서든 출발해도 상관없음. 빈칸 ‘.’에 대해 진행방향 그대로 직진만 가능. ‘!’ 칸은 거울 설치 가능한 곳으로써 해당 자리에 거울을 45도 설치 가능. 거울을 설치하게 되면 빛은 직진이 ..

문제 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이 모든 정점으로부터 다른 모든 정점까지의 거리를 구하는 문제로써 플로이드 워셜 풀이가 가능 하지만 나는 데이크스트라로 풀이함 최초 접근 주어지는 K개의 노드를 출발점으로 하여금 데이크스트라를 수행하면서 전역 dp배열에 최대 비용을 기록 후 갈 수 있는 노드들에 대해 탐색하여 왕복시간을 구하려함. 하지만 이렇게 풀이하게 될 경우 왕복시간을 구할수가 없기 때문에 잘못된 풀이. 접근법 주어지는 K로부터 모든 노드에 대해 왕복시간을 구하고 모두..

Concept그리디 알고리즘의 한 분류다이나믹 프로그래밍 메모이제이션 기법 활용부분 문제 : 한 정점까지의 최단거리는 방문하는 여러개의 정점들의 최단거리로 이루어져있음.주어지는 그래프에서 시작 정점으로부터 각 정점까지의 최단경로를 찾는 알고리즘Feature우선순위 큐와 거리배열(DP)을 활용하여 로직 구성.한 정점 V까지의 최단거리를 구할 때 V까지로 가는 여러 정점들의 최단 거리 정보를 활용한다는 특징을 가짐.가중치를 가진 그래프에서 최단거리를 구할 때 쓰이는 알고리즘음수 가중치를 가진 그래프에서는 사용불가.우선순위 큐를 활용함으로써 시간복잡도 : O(N * NlogN)Implement인접 리스트를 통한 구현우선 데이크스트라 소스코드를 보자.private static int dijkstra(int st..