본문 바로가기

알고리즘, 자료구조/알고리즘 개념11

[GCD 알고리즘] 최대공약수 알고리즘 GCD 알고리즘 GCD(Greatest Common Divider, 최대공약수)를 구하는 방법 중 하나로 유클리드 호제법(유클리드 알고리즘, Euclidean algorithm)이 있습니다. 유클리드 호제법은 간단합니다. a, b의 최대 공약수를 (a, b)라고 정의하면 다음과 같은 관계가 성립합니다. $$ \begin{align}(a, b) = (b, r) \newline &where, a \geq b, 0 \leq r < b\end{align} $$ 단, a, b는 정수이고, a를 b로 나눈 나머지는 r 입니다. 증명은 비교적 간단하지만, 수식이 조금 복잡할 수 있습니다. 따라서 최대한 핵심 수식만 쓰고, 나머지는 말로 풀었습니다. 증명은 다음과 같습니다. 1) $$ (a, b) = d, a = d .. 2019. 10. 18.
[최단경로] 다익스트라(Dijstra) 알고리즘 30. 최단 경로 알고리즘 BFS와 구현방법이 상당히 비슷하다. 다익스트라 알고리즘 다익스트라(Dijstra, 데이크스트라) 알고리즘은 다음과 같다. d[v]는 시작점 s로 부터 그래프의 모든 점까지의 최단거리이다. 아이디어는 BFS와 비슷한데, 가중치가 붙어있는 그래프를 다루므로, queue에 넣을 때는 (지금까지 누적 cost, 다음점)을 넣어준다. 매번 while문의 처음에서 cost가 최소인 점을 선택하는 이유는, 최단 거리가 되는 가능성이 있는 점들을 먼저 탐색하고 d[v]를 기록해주기 위함이다. 이렇게 해서 S 안에 다른 원소가 뽑혀 이미 기록된 d[v] 과 비교하여 더 크다면, 무시해주면 된다! 그래프를 직접 그려보면서, 알고리즘을 이해하는 것이 효율적인 것 같다. 이렇게 해서 직접 코드를 .. 2019. 9. 27.
[BFS] 너비 우선 탐색 BFS (너비 우선 탐색) 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 각 정점을 방문할 때마다 모든 인접 정점을 검사합니다. 처음 보는 정점을 발견하면 이 점을 방문 예정(discoverd)이라고 기록한 뒤, 별도의 위치(queue)에 저장합니다. 인접한 정점을 모두 검사하고 나면, 저장한 목록에서 다음 정점을 꺼내서 방문합니다. BFS (너비 우선 탐색)에서 새 정점을 발견하는데 사용했던 간선을 모은 트리를 BFS Spanning Tree(너비 우선 탐색 신장 트리) 라고 부릅니다. #include #include using namespace std; // Adjacent List vector adj; vector order; /* start 노드로부터 시작하여 너비 우선 탐색하여 각 .. 2019. 9. 9.
[DFS] 깊이 우선 탐색 DFS (깊이 우선 탐색) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법. 현재 정점과 인접한 간선들을 하나씩 검사가하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있으면 그 간선을 따라간다. dfs(edge) 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. dfs 종료 #include using namespace std; // adjacent list vector adj; vector visited; /* Depth First Search node u --> v */ void dfs(int u){ visited[u] = true; // 모든 인접 정점을 순회하면서 for (int i = 0; i < adj[u].size(); ++i){ int v = adj.. 2019. 9. 8.
[DP] LIS (최장 공통 부분 수열) LIS (Longest Increasing Subsequence) 수열 안에 있는 증가 하는 부분 수열 중 가장 긴 것을 찾는 문제 Idea1 완전탐색입니다. 1) 수열을 처음부터 하나씩 증가하면서 (a[]의 모든 원소마다), 각 경우마다는 첫번째 수 a[i]를 정하고, 인덱스를 1씩 늘려가면서(a[i+1] ... ) 첫번째 수보다 큰 숫자들을 컨테이너(sub_a[])에 담습니다. 2) sub_a를 1)번 과정을 되풀이하는 재귀함수를 구현합니다. a[] = {3, 2, 1, 7, 5, 4, 2, 6} 첫번째 원소 3을 기준으로, 그 다음 가능한 7 5 4 6 중 다시 재귀적으로 LIS를 뽑습니다. #include #include using namespace std; /* LIS의 길이를 반환 */ int.. 2019. 9. 6.
[Sort] 대표적인 정렬의 모든 것 정렬(Sort) 비교정렬(Comparision Sort) 비교하여 정렬하는 방법은, 아무리 알고리즘을 잘 짜도 O(NlogN)보다 크다. 그렇지만, O(NlogN)도 충분히 빠른 정렬이고, 일반적인 경우에 대해 정렬할 수 있는 방법이기 때문에 이를 공부하는 것은 중요하다. O(N2) 정렬 1. 버블 정렬(Bubble sort) 장점 : "순서대로 대소 비교 후 큰 것을 뒤로 보낸다."를 그대로 구현하면 되기 때문에, 코드가 보기에 직관적이므로 구현이 쉽다. stable 정렬이다. 단점 : 최악이든 최선이든 O(N2)이기 때문에 굉장히 비효율적이다. 2. 선택 정렬(Selection sort) 장점 : "최댓값을 찾고, 맨 뒤의 원소와 바꾸어준다"를 그대로 구현하면 된다. 구현이 쉽다. 원소 교환 횟수가 .. 2019. 8. 31.
[KMP] 문자열 알고리즘 KMP algorithm KMP (Knuth-Morris-Pratt) 알고리즘 문자열 검색, 짚더미(Haystack, H 문자열)에서 바늘(Needle, N 문자열)을 찾아봅시다! 불일치가 일어났을 때 지금까지 일치한 글자 수를 이용해 다음으로 시도해야 할 시작 위치를 빠르게 찾아냅니다. 필요한 것: 부분 일치 테이블(partial match table) p[i] 를 만듭니다. pi[i]는 문자열 N[...i] (문자열 처음부터 i번째 까지 문자열)의 접두사도 되고 접미사도 되는 문자열의 최대 길이입니다. 예를들면 "aabaaba"에서 aaba는 접두사도 되고 접미사도 되는 최대 길이 문자열이므로, pi[6] = 4 입니다. KMP 알고리즘의 전체 반복문 수행 횟수는 O(|H|) 입니다. #include.. 2019. 8. 30.
16. 비트마스크 (bitmask) 장점 - 더 빠른 수행 시간을 보장합니다. - 더 간결한 코드를 제공합니다. - 메모리 사용량을 줄일 수 있습니다. 즉, 더 많은 데이터를 미리 계산해서 저장해 둘 수 있습니다. 비트마스크를 자료 구조로 이용하는 방법 및 각종 트랙을 소개합니다. 용어정리 8bit를 예로들자면, 최솟값은 0이고, 최댓값은 1111 1111(2) = 255입니다. 20을 나타내는 비트를 최하위 비트(LSB, Least Significant Bit), 2N-1을 나타내는 비트를 최상위 비트(MSB, Most Significant, Bit) 라고 합니다. 어떤 비트의 위치가 1이면 해당 비트가 "켜져 있다"고 하고, 0이면 "꺼져 있다"라고 합니다. 연산 코드 두 정수 a, b를 비트 별로 AND 연산 a & b OR a XO.. 2019. 8. 12.
6. 브루트포스(brute-force) part 2 6.7 최적화 문제(Optimization problem) 문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 &#39;좋은&#39; 답을 찾아 내는 문제 ex) n개의 사과 중에서 r개를 골라 무게의 합을 최대화 하는 문제 최적화 문제를 해결하는 방법 중 기초적인 것은 완전 탐색 이다. 가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 되기 때문에, 가장 직관적인 방법이기도 하다. 다른 방법으로는 동적계획법(DP), 조합탐색, 결정문제 등으로 문제를 더욱 빠르게 풀 수 있다. ex) 여행하는 외판원 문제 (Traveling Salesman Problem, TSP) 6.10 많이 등장하는 완전 탐색 유형 모든 순열 만들기 가능한 순열의 수 N!, N이 10을 넘어간다면 .. 2019. 7. 15.
6. 브루트포스(brute-force) part 1 브루트 포스 - 무식하게 풀기 6.2 재귀호출과 완전 탐색 재귀호출 재귀호출시 쪼개지지 않는 가장 작은 작업에서 함수를 return 하여 종료시켜야 한다. 가장 작은 단위를 기저 사례 (base case)라 한다. 중첩 반복문 대체 완전 탐색 구현 ex) 모든 조합의 경우의 수 찾기 #include #include /* 모든 조합의 경우를 출력한다. 재귀호출을 이용한다. 다중 for문을 대체할 때 유용하다. */ using namespace std; int cnt = 0; void printVector(vector v){ for (auto i : v) printf("%d ", i); printf("\n"); } // nCm void combination(int n, vector & v, int m){ i.. 2019. 7. 14.
728x90