💻

다이나믹 프로그래밍(Dynamic Programming) => 큰 문제를 작은 문제로 나누서 푸는 알고리즘 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. Optimal Substructure 를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다. 따라서, 정답을 한 번 구했으면 어딘가에 메모해놓는다. 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다. 메모를 한다고 해서 영어로 Memoization 이라고 한다. 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다. 1. Overlapping Subproblem (문제를 작은 문제로 나눠서 푸는데, 이때 문제들끼리 겹쳐야한다.) 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. 문제를 작은 문제로 ..

다익스트라 if(dist[to] > dist[from] + cost){ dist[to] = dist[from] + cost; } - D[i] = 시작 -> i 로 가는 최단 거리 - C[i] = i가 체크되어 있으면 true, 아니면 false 1. 체크되어 있지 않는 정점 중에서 D의 값이 가장 작은 정점 x를 선택한다. 2. x를 체크한다. 3. x와 연결된 모든 정점을 검사한다. 간선을 (x,y,z)라고 했을 때 d[y] > d[x] + z 이면 갱신해준다. 1, 2, 3단계를 모든 정점을 체크할 때까지 계속한다. - 모든정점 선택하므로(V-1) X 선택을 하는 데 걸리는 시간 O(V) = O(V^2) 인접행렬을 이용한 구현 for(int i=1; i

이전글 ) 2020/02/29 - [알고리즘/기본기 다지기] - [알고리즘][DFS와BFS 완전정복] 그래프의 표현 [알고리즘][DFS와BFS 완전정복] 그래프의 표현 어느정도 알고리즘 문제 풀이를 해 본 사람이라면 알겠지만 모든 코딩테스트에 거의 단골로 출제되는 문제가 바로 DFS, BFS 이다. 백준 문제풀이를 하면서 가장 나를 힘들게 했던 것도 바로 DFS와BFS!! 그래서 나.. hyonee.tistory.com 2. 그래프 탐색 DFS:깊이 우선 탐색 -> 최대한 깊숙히 많이 BFS:너비 우선 탐색 -> 최대한 넓게 가는 것 모든가중치가 1인경우 최단거리 탐색 - 위의 2가지 탐색 모두 목적은 모든 정점을 1번씩 방문하는 것 DFS - 스택을 이용해서 갈 수 있을 만큼 최대한 많이 가고 갈 수 ..

어느정도 알고리즘 문제 풀이를 해 본 사람이라면 알겠지만 모든 코딩테스트에 거의 단골로 출제되는 문제가 바로 DFS, BFS 이다. 백준 문제풀이를 하면서 가장 나를 힘들게 했던 것도 바로 DFS와BFS!! 그래서 나와 같이 알고리즘 문제풀이 새내기 왕초보들을 위해 완전 정복이라는 카테고리로 올리고자 한다. 글을 쓰면서 나도 공부하고, 자료가 부디 도움이 되길 바라는 마음입니다 :) 1. 그래프 표현 인접 행렬 - 양방향 그래프 일 때 A[i][j], A[j][i] - 인접 행렬은 없는 간선도 저장하기 때문에 자주 쓰이지는 않는다. 쉬운 문제를 풀 때 주로 사용한다. - 인접 행렬의 공간 복잡도는 O(V^2)이다. 가중치가 없는 경우) #include #include int a[10][10]; int m..

이항계수 분할 정복법을 이용한 이항계수 알고리즘 int binary(int n, int k){ if(k==0 || n == k) return 1; else return binary(n-1, k-1) + bin(n-1, k); } 동적프로그래밍을 이용한 이항계수 알고리즘 int binary(int n, int k){ int B[n][k]; for(int i=0; i

탐욕적 알고리즘이란? 어떤 선택을 해야할 때 그 당시에 가장 최선의 선택을 하여 문제를 해결하는 알고리즘을 말한다. - 순간의 선택은 그 당시의 최적의 선택이다. 이런 선택들이 모여 최종적인 해답을 얻는다고 하여 최종 해답이 최적이라는 보장은 없다. 따라서, 탐욕적 알고리즘은 해답을 얻은 후에 이 해답이 최적인지 검사해야 한다. - 알고리즘 설계 절차 1단계) 선정과정(selection procedure) : 현재 상태에서 가장 좋은 선택이라고 생각되는 해답을 찾아서 해답모음(solution set)에 포함시킨다. 2단계) 적정성검사(feasibility test) : 새로 얻은 해답모음이 적절한지를 결정한다. 3단계) 해답 검사(solution check) : 새로 얻은 해답모음이 최적의 해인지 결정한..

이분 탐색(이진탐색) 알고리즘 은 찾을 범위를 반으로 나눠서 탐색하는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 키값의 크고 작음을 비교하는 방식이다. 처음 선택한 중간값이 만약 찾는 값보다 크면 최댓값이 되고, 작으면 최솟값이 된다. - 분할 정복 알고리즘에 속하는 알고리즘이다. - 단, 이미 정렬된 경우에만 적용할 수 있다. - 최악의 경우는 찾으려는 키값이 배열에 존재하지 않을 때이다. - 시간복잡도는 O(logN) 이다. 반복문을 사용하는 경우 int BinarySearch(int arr[], int length, int key){ int first = 0; int last = length - 1; int mid = 0; while(first key){ // 중간값이 찾으려..

분할 정복법이란? 문제의 사례를 2개 이상의 더 작은 사례로 나누어(divide) 각 작은 사례에 대한 해답(conquer)을 쉽게 얻을 수 있으면 이들의 해답을 결합(combine)하여 원문제의 해답을 얻는 방식. - 문제를 나누는 과정은 해답을 쉽게 얻을 때까지 반복적으로 적용한다. - 하향식(top-down) 접근 방법이다. 분할(Divide) : 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer): 나눈 작은 문제를 각각 해결한다. 통합(Combine): (필요하다면) 해결된 해답을 모은다. - 보통 재귀 프로시저로 먼저 해결한 다음에 보다 효율적인 반복 프로시저가 없는지 검토한다. - 대표적인 알고리즘 이진 검색(BinarySearch) 합병 정렬(MergeSort) ..