안녕하세요! 최단 경로 알고리즘으로 다익스트라 알고리즘과 플로이드 워셜알고리즘이 많이 알려져 있습니다. 오늘은 또다른 최단 경로 알고리즘인 벨만 포드 알고리즘을 소개시켜 드리고자 이번 포스팅을 하게되었습니다. 벨만 포드 알고리즘을 소개하기 이전에, 다익스트라 알고리즘 및 플로이드 워셜 알고리즘의 한계점을 먼저 알고가면, 벨만 포드 알고리즘을 이해하는데 큰 도움이 되기 때문에 이 부분부터 먼저 살펴보도록 하겠습니다! 다익스트라 알고리즘의 한계 이번 포스팅에서는 다익스트라 및 플로이드 워셜 알고리즘에 대한 설명을 따로 하지 않고, 다음에 기회가 되면 이 두가지 알고리즘에 대해 따로 포스팅하도록 하겠습니다. 다익스트라 알고리즘은 그리디(Greedy) 알고리즘을 기반으로 구현합니다. 시작점을 기준으로 연결된 노..

안녕하세요! 오늘은 알고리즘 문제에서 자주 볼 수 있는 순열과 조합을 구현하는 방법에 대해 간단히 소개시켜 드리고자 합니다🤗 순열(Permutation) 순열이란? n개의 숫자 중에서 r개의 숫자를 순서대로 뽑는 경우를 의미합니다. 예를 들어, [1, 2, 3] 배열 중 2개의 숫자를 순서대로 뽑은 결과는 아래와 같습니다. [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 위와 같은 순열은 각각 Swap과 백트래킹을 이용하여 구현할 수 있습니다! Swap // Swap class Permutation { private int n; private int r; private int[] now; // 현재 순열 private ArrayList result; // 모든 순열 public..

- DFS(깊이 우선 탐색, Depth-First Search) : 루트노드나 다른 임의노드에서 다음 분기로 넘어가긴 전에, 해당 분기를 모두 탐색하는 방법으로 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다. 자기 자신을 호출하는 순환 알고리즘의 형태입니다. -> 재귀나 스택을 이용 (컴퓨터 자체가 스택구조 이기때문에 재귀만으로 가능) 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 받드시 검사해야합니다. (만약 검사하지 않을 경우 무한루프의 위험이 있습니다.) ex) visited[index] = true; // 방문 미로탐색에서 해당 분기에서 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게되면 다시 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법..