두's 스토리

다익스트라 한 정점에서 다른 끝점 까지 가는 최단거리를 구할 때 사용 플로이드 워셜 알고리즘은 정점 전부에 관한 정보를 업데이트하여 N^3이란 시간복잡도를 가진다. (=AllPairShortest) 그러나, 다익스트라는 시작점을 고정하고 DP배열을 업데이트 하는 방식을 통해 n^2이란 시간복잡도를 가짐. 다익스트라에서 최종적으로 나온 DP 배열은 시작점에서 그 점까지의 거리를 의미 NODE 1 2 3 4 5 DP 0 3 5 INF 8 다음 표처럼 시작점을 정해주고 모든 점에 대해 DP를 업데이트하면 최단거리를 구할 수 있음 1에서 3까지의 거리는 5, 1에서 4까지의 거리는 INF를 의미 백준 1753 최단경로 일반적으로 인접행렬 W 을 이용하여 DP를 업데이트 방문노드 1 2 3 4 5 INF INF ..

알고리즘에서 DP를 배울 때 유명한 문제. 0/1 배낭 채우기 알고리즘 백준 1535 안녕 풀이 DP 0 1 2 ... 21 22 ... 79 80 {1} 0 20 20 20 20 20 20 20 20 {1, 21} 0 20 20 20 30 (Max(dp[21], dp[0]+W[21]) 50 (Max(dp[22], dp[1]+W[21]) 50 50 50 {1, 21, 79} 0 20 20 20 30 50 50 50 50 1만 들어왔을 때 고려, 21 들어왔을 때 고려, 79 들어왔을 때 고려하는 방식을 통해 dp배열을 업데이트한다. 새롭게 고려하는 항목이 21이라고 했을 때 W[21]이 플러스 되는 부분이다 뒤에서부터 업데이트를 해야 제대로 해결 import java.util.Arrays; import ..

순열 & 조합 (Permutation & combination) 수를 나열함에 있어서 순서를 생각하느냐 아니냐에 따라 순열과 조합을 구분할 수 있다. 순열(nPr) ​ n개의 수에서 r개의 수를 뽑아 순서를 생각하고 나열하는 방법 반복문을 이용한 순열 public class Permutation { public static void main(String[] args) { int arr[] = {1,2,3}; for (int i = 0; i < arr.length; i++) { // int i1=arr[i]; for (int j = 0; j < arr.length; j++) { // int i2 = arr[j]; if(i!=j) { for (int k = 0; k < arr.length; k++) { if..

이진검색(Binary Search) 자료의 가운데부터 검색하고 가운데 값보다 값이 작으면 왼쪽으로 크면 오른쪽으로 탐색 이진검색을 하기 위해서는 자료가 정렬된 상태이어야 함 #include using namespace std; int target = 7; int f(int* arr, int front, int end); int main(){ int arr[] = { 2, 4, 7, 9, 11, 19, 23 }; int n = sizeof(arr) / sizeof(int); int ans = f(arr, 0, n - 1); if (ans != -1){ cout