우당탕탕 코딩일기

다익스트라(Dijkstra) 알고리즘이란?그래프에서 한 정점에서 다른 정점까지의 최단거리를 구할 때 사용하는 알고리즘이다.다익스트라는 다음과 같은 특징이 있다.다익스트라 알고리즘의 특징1. 하나의 시작 노드에서 모든 노드까지의 최단 거리를 계산한다. 즉, 특정 노드 한 개만 목적지여도 전체 경로를 계산한다는 의미이다.2. 음수 간선이 있는 그래프에는 사용할 수 없다. 이미 처리한 최단거리 경로보다 더 짧은 경로가 나중에 발견될 가능성이 있기 때문이다.3. 매 단계 노드에서 간선의 가중치(weight)를 기준으로 경로를 계산한다. class Graph { int[,] adj = new int[6, 6] { { -1, 15, -1, 35, -1, 0 }, { 15..

DFS(Depth First Search)란? DFS는 깊이 우선 탐색으로 그래프나 트리에서 한 경로를 따라 최대한 깊이 들어갔다가, 더 이상 갈 곳이 없으면 되돌아오며(backtracking) 다른 경로를 탐색하는 알고리즘이다. class Graph{ int[,] adj = new int[6, 6] { { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 1, 0, 0 }, { 0, 1, 0, 0, 0, 0 }, { 1, 1, 0, 0, 1, 0 }, { 0, 0, 0, 1, 0, 1 }, { 0, 0, 0, 0, 1, 0 }, }; List[] adjList = new List[6] { ..

알고리즘의 효율을 측정하려면 Big-O 표기법을 사용한다.Big-O 표기법이 중요한 이유는 어떤 알고리즘이 작은 입력에서는 빠를 수 있지만 입력값이 많아진다면 느려질 경우가 발생하게 된다.시간 복잡도(Time Complexity)시간 복잡도란? 입력 크기에 따라 알고리즘이 얼마나 많은 연산을 수행하는지 나타내는 것이다.위 그래프는 오른쪽 아래로 갈 수록 효율적인 알고리즘, 왼쪽 위로 갈 경우 비효율적인 알고리즘을 나타낸다. Big - O 표기법은 가장 빠르게 증가하는 항만을 남기고 나머지는 무시해서 표현한다.이렇게 표기하는 이유는 함수가 정확히 몇 개의 연산량이 중요한 것이 아닌 데이터가 늘어남에 따라서 어떤 식으로 연산량이 증가하는지가 중요하기 때문이다. 예시: T(N) = 2N^2 + 3N + 5 =..