Bellman-Ford 알고리즘 이란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능 시간복잡도 : O(NE) (N:노드의 수, E: 엣지의 수) 다음과 같은 그래프가 있다고 가정 다익스트라로 노드 1에서 모든 노드로의 거리를 구하면 1 -> 2 = 1 1 -> 2 -> 3 = 2 1 -> 2 -> 3 -> 4 = 4 가 되고 노드 2는 이미 방문했기 때문에 4 -> 2 경로는 고려하지 않음 결과적으로 1 -> 2의 최단경로는 1이 됨 하지만 실제 1 -> 2의 최단경로는 -∞ 임 이를 해결하기 위해 벨만포드 알고리즘 탄생 Bellman-Ford 원리 엣지는 1->2, 4->2, 2->3, 3->..

Dijkstra 란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 단, 가중치에 음수가 있으면 사용할 수 없음 시간복잡도 : O(E logN) (N:노드의 수, E: 간선의 수) 다음과 같은 그래프가 있다고 가정 1번 노드에서 2, 3, 4, 5번 노드까지의 최단거리를 모두 구해야 함 dist[1~5] = [0, ∞, ∞, ∞, ∞]로 초기화 후 시작 1번 노드에서 갈 수 있는 노드 = 2, 3, 4 1(시작노드) -> 2로 갈 때 드는 비용 ( = dist[1] + (1->2) )과 지금까지 2로가는 최소 비용 (=dist[2])를 비교해서 지금까지 2로가는 최소비용이 더 크다면 dist[2] = dist[1] + (1->2)로 갱신 이 방식으로 1번노드에서 갈 수 있는 노드들에 대한 ..

DFS, BFS 란? DFS : Depth First Search의 줄임말로 깊이 우선 탐색을 뜻함 BFS : Breadth First Search의 줄임말로 너비 우선 탐색을 뜻함 다음과 같은 그래프를 탐색한다고 가정 DFS 수행 과정 1번 노드에서 시작 2, 5번 노드로 갈 수 있음 숫자가 더 작은 2번 노드로 감 (전략은 마음대로 설정) 3, 4번 노드로 갈 수 있음 3번 노드로 감 3번 노드에서는 갈 수 있는 곳이 없음 2번노드로 돌아감 4번 노드로 감 4번 노드에서 갈 수 있는 곳이 없음 2번 노드로 돌아감 2번 노드에서도 더 이상 갈 수 있는 곳이 없음 1번 노드로 감 .... 이런 식으로 탐색을 진행 결과 : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 BFS ..

정렬 알고리즘 별 시간 복잡도 정렬 알고리즘 시간 복잡도 Bubble Sort (버블 정렬) O(n^2) Selection Sort (선택 정렬) O(n^2) Insertion Sort (삽입 정렬) O(n^2) Quick Sort (퀵 정렬) 평균 : O(nlogn) / 최악 : O(n^2) Merge Sort (병합 정렬) O(nlogn) Radix Sort (기수 정렬) O(kn) / k : 최대 데이터의 자릿수 Arrays.sort() 평균 : O(nlogn) / 최악 : O(n^2) Collections.sort() O(nlogn) 위 표를 보면 병합정렬이 퀵정렬보다 빠르다고 생각할 수 있음 최악의 상황에선 퀵정렬이 느리지만, 보통은 퀵정렬이 더 빠르고, 병합 정렬은 메모리를 더 많이 차지함 이..

재귀함수 : 함수가 자기자신을 다시 호출하여 문제를 해결하는 함수 팩토리얼 문제를 통해 재귀함수 정리 팩토리얼이란? 팩토리얼 : 어떤 수 이하의 모든 양의 정수의 곱 기호는 !를 사용한다. ex) 5! = 5 * 4 * 3 * 2 * 1 = 120 재귀함수를 이용한 팩토리얼 (개념) fact라는 메서드에 파라미터 x를 넘겨줌 x값이 1이 될 때 까지 x * fact(x-1)을 return x값이 1이되면 1 return fact(5) = 5 * fact(4) return fact(4) = 4 * fact(3) return fact(3) = 3 * fact(2) return fact(2) = 2 * fact(1) return fact(1) = 1 return => fact(5) = 5 * fact(4) =..