코딩 테스트/자료구조 & 알고리즘

백트래킹 알고리즘이란?백트래킹(Back Tracking) 알고리즘은 탐색 알고리즘 중 하나로 가능성이 없는 곳은 되돌아가고 가능성이 있는 곳은 탐색하는 알고리즘이다. 집에서 나왔는데 지갑을 두고 나와 다시 돌아간다고 한다면우선 아파트로 갈것 이다.그런 다음 우리는 자연스럽게 내 호수에 해당하는 집으로 향할 것이다.지갑은 내 집, 내 방에 있기 때문에 굳이 다른 집을 들어가 방을 찾지 않아도 된다.이것이 바로 백트래킹의 원리이다. 가능성이 없는 건 하지 않는다.  백트래킹 알고리즘은 일반적으로 재귀를 통해 구현되며 모든 경우의 수를 시도해보는 완전탐색 기법 중 하나다.하지만 가능한 해가 아닌 경우를 미리 배제함으로써 탐색 공간을 줄이고, 문제를 효율적으로 해결할 수 있도록 한다.따라서 너비 우선 탐색이나 ..

벨만 포드 알고리즘이란?다익스트라 알고리즘과 벨만 포드 알고리즘 모두 가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘이다.하지만 벨만포드가 다익스트라에 비해 갖는 특징이 있다.바로 위와 같은 음의 가중치가 있는 그래프에서도 작동한다는 것이다.더불어 음의 사이클도 감지가 가능하다. 음의 사이클이란? 음의 사이클이란 경로의 합이 음수가 되는 사이클을 말한다.위의 사례에 경우 B에서 C를 거쳐 다시 B로 돌아오는 사이클이 존재하는데 이 경우 -3의 비용이 발생한다. 이렇게 되면 최단 거리가 무한대로 줄어들게 된다.벨만포드 알고리즘은 이러한 음의 사이클까지 감지가 가능하다.  다익스트라 벨만 포드음의 가중치 그래프 적용 가능XO음의 사이클 감지 가능XO 정리하자면 벨만포드 알고리즘은 가중치가 있는 그래프에..

다익스트라 알고리즘(Dijkstra Algorithm)이란?다익스트라 알고리즘이란 에츠허르 다익스트라가 제안한 최단 거리 알고리즘이다.다익스트라 알고리즘은 위와 같이 가중치가 존재하는 그래프에서 특정 노드에서 다른 노드까지의 최단경로 및 최단거리(최소비용)를 구할 때 사용된다.  다익스트라 알고리즘 동작 방식다익스트라 동작방식은 다음과 같다. 1. 시작 노드를 정하고 테이블을 초기화한다. 테이블에는 시작 노드에서 각 노드까지의 최소 비용과 직전 노드를 저장한다.      1-1. 시작 노드의 경우 최소 비용을 0, 직전 노드를 자기 자신으로 초기화 한다.     1-2. 나머지 노드의 경우 최소 비용을 무수히 큰 값, 직전 노드를 임의의 더미 값으로 초기화한다.2. 다음을 수행한다.    2-1. 방문하..

그래프의 탐색그래프를 탐색한다는 것은 그래프의 정점들을 탐색한다는 의미이다.이때 정점을 탐색하는 순서가 중요한데 크게 두 가지로 나눌 수 있다. 바로 깊이 우선 탐색과 너비 우선 탐색이다. 깊이 우선 탐색(DFS: Depth First Search)말 그대로 깊이를 우선적으로 탐색한다.한 정점을 기준으로 더 이상 탐색할 정점이 없을 때까지 가보고 없으면 최근에 방문했던 노드로 되돌아가 다음 가지 않은 노드를 방문한다. 너비 우선 탐색(BFS: Breadth First Search)말 그대로 너비를 우선적으로 탐색한다.한 정점을 기준으로 가장 가까운 정점을 모두 방문하고 다음 정점으로 넘어간다.그 정점에서 가장 가까운 정점부터 모두 방문한다. 지금부터 각각에 대해 자세히 알아보도록 하자. 깊이 우선 탐색(..