개발 블로그

다익스트라 알고리즘이란 무엇인가? 음의 가중치가 없는 그래프의 한 정점(V)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다. 기존에는 O(V^2)의 시간복잡도를 가졌으나, 시간이 지나 우선순위 큐를 이용하여 더욱 개선된 알고리즘이 생겨났으며 O((V+E)logV)(V : 정점의 개수, E : 간선의 개수)의 시간 복잡도를 가질 수 있게 되었습니다. O(VlogV)(각 노드마다 미방문 노드 중 출발점으로 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 걸리는 시간) + O(ElogV) (각 노드마다 이웃한 노드의 최단거리를 갱신할 때 걸리는 시간)으로 보시면 될 것 같습니다. 출처 : https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 이 문제는 0번 스위치를 누를지 말지 결정하고 풀어야 하는 문제입니다. 왜냐하면 모든 스위치를 한 번씩 눌러보는 브루트 포스로는 복잡도 문제로 해결할 수 없습니다. 0번 스위치를 누른다면, 1번 스위치만 신경 쓰면 되고, 1번 스위치가 눌러지면 2번 스위치만 고려하면 되기 때문입니다. 그래서 시간 복잡도 O(N)으로 풀 수 있게 됩니다. #include #include..

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 이 문제는 3*3 행렬을 반대로 (0->1, 1->0) 뒤집어서 주어진 A에서 행렬 B로 만들 수 있는 최소 연산 횟수를 물어보는 문제입니다. 이 문제의 핵심은 (N-2) * (M-2)의 연산을 수행해 보는 것입니다. 왜냐하면 이 연산을 모두 수행했을 때, 주어진 행렬 B와 일치하지 않으면 더 이상 행렬 B를 만들 수 없기 때문입니다. 이러한 연산으로 인해, 어떠한 원소를 두 번 뒤집는 것은 원래대로 돌아오기 ..