CS/자료구조,알고리즘 (19) 썸네일형 리스트형 방향 그래프에서 사이클 찾기 Cycle? 사이클은 모두 알다시피 그래프에서 시작과 끝이 같은 형태를 말한다. 그래프에서 사이클은 언제나 성가신 존재인데, 무한루프를 발생 시킬 수도 있고, 쓸 대 없이 몇 번 돌다가 나와서 성능이 안 좋아질 수도 있다. 이것은 현업에서도 골치이고 PS에도 자주 등장하는 문제이다. 이것을 어떻게 판별할 수 있을까 방향 그래프에서 싸이클 판별 방향 그래프에서 사이클을 판별할 수 있는 방법은 가장 익숙한 DFS 이다. dfs는 방향이 계속 같기 때문에 다음 노드를 판별하기 용이하기 때문이다. 그리고 방향 그래프에서의 사이클이란 Back Edge가 존재하는 것과 같다. 이제 문제는 Back Edge를 판별하는 것으로 바뀌게 된다. void dfs(int NowNode) { visited[NowNode] = .. 벨만-포드 알고리즘 (Bellman-Ford Algorithm) Bellman-Ford Algorithm 벨만 포드 알고리즘은 음수 간선이 존재하고 그것이 사이클을 만들어낸다고 해도 최단거리를 만들 수 있는 알고리즘이다. 다익스트라 알고리즘은 익히 알다시피, 음수 간선이 존재하면 사용할 수 없는 것을 알고 있을 것이다. 다익스트라와 벨만 포드의 차이 다익스트라와 벨만 포드는 둘 다 1차원 dist 배열을 갱신하며 최소치를 기록하는 스킬은 똑같다. 그러나, 다익스트라는 모든 노드를 살펴보지 않는다. 가능한 경우에만 다음 노드로 이동하기 때문이다. 그러나 이 효율적인 방식 때문에 음수 간선이 있으면 다익스트라를 사용할 수 없다. 그러나 벨만 포드는 효율적이지 않게도 모든 노드를 살펴본다. 그래서 시간복잡도가 N*M이다. 그리고 음수간선이 있어도 사용이 가능하다. 바로 아.. 플로이드-워셜 알고리즘 플로이드-워셜 알고리즘은 그래프 이론에서 모든 정점간의 최단 경로를 찾기 위한 알고리즘이다. 이 알고리즘은 두 개의 단계로 이루어진다. 위 그래프를 예로 들어 초기 배열을 만들어보자. 그리고 각 노드를 경유지로 지정한다. 즉 지금은 인접노드만 가지고 있지만 1 → 2 → 3 이러한 경우도 계산한다는 뜻이다. 먼저 1번 노드를 경유한다고 가정하자. 그렇다면 1행은 스킵하고 2행을 진행한다. DP[4][2] = DP[4][1] + DP[1][2] 이므로 다음과 같은 점화식을 얻을 수 있다. DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]) 위 점화식을 해석하면 정점 i 와 j의 최소 거리는 원래 지정되어 있던 값과 노드 k를 경유했을 때의 최소값이다. 그러므로 k도 1부터 N.. 최소 공통 조상 LCA: Lowest Common Ancestor LCA: Lowest Common Ancestor 트리의 노드들 중 공통 조상을 찾는 알고리즘이다. DFS, BFS를 통해 한 노드에서 시작해 모든 간선을 확인해볼수도 있겠지만 이 방법을 사용하면 더 빠르게 찾아낼 수 있다. 위의 상황에서 12번노드와 6번노드의 최소 공통 조상을 찾아보자. 최소 공통 조상은 누가봐도 3이다. 그렇다면 알고리즘으로 어떻게 풀어낼 수 있을까? 레벨을 맞춘다. LCA에서 중요한 것은 레벨을 맞춰야한다. 즉 LCA(6, 12) = LCA(6, 7) 과 같다. 이처럼 레벨(깊이)를 맞춰준 후 동시에 하나씩 조상을 탐색하는 것이 LCA이다. DFS 전처리 LCA를 위해서는 각 노드가 조상의 정보와 레벨의 정보를 가지고 있어야한다. 이를 위해 dfs 전처리가 필요하다. 만들어진 노드.. 이분 탐색의 이해 이분탐색은 간단하게 절반씩 줄여나가며 값을 찾는 방법이다. 논리는 중학생도 이해할 수 있는 간단한 로직이다. 그러나 문제를 풀다보면 lo < hi 인지 lo 문자열 관리 자료구조 - 트라이(Trie) 개념/구현 C++로 PS를 공부할 때나 코딩테스트를 볼 때 문자열 문제가 나오면 일단 짜증이난다. 파이썬은 문자열 다루기가 편하다는데 C++는 아무래도 문자열을 다룰때 힘든 면이 많다. 문자열 문제가 나오면 파이썬을 쓰고 다른 문제에선 C++을 쓰는 사람도 있을 정도다. 아무튼, 트라이는 문자열을 다루는 방식 중에서도 특히 문자검색을 할 때 가장 유용하고 효과적인 자료구조가 바로 트라이 이다. 먼저 트라이는 문자열로 트리를 만든다고 보면 된다. AB, ABC, BCD, ABD 라는 단어가 들어온다고 치자. 그렇다면 root / \ A B / \ B* C / \ \ C * D* D* 이런식으로 트리를 구성한다. 이렇게 하고 단어가 끝나는 글자들에는 표시를 해둔다. 즉 , 단어를 찾을 때 표시가 되어있는 글자라면 끝났.. DFS를 활용한 순열 이전에 dfs를 활용한 조합을 봤습니다. 순열도 비슷한 방식으로 백트래킹을 사용합니다. 조합과 순열의 가장 큰 차이는 순서입니다. 조합은 1 2 3, 1 3 2 가 같지만 순열은 다르다고 봅니다. 때문에 조합은 idx라는 인수를 갱신하면서 1 2 3 에서 2개를 뽑는다고 치면 1 2, 1 3 하고 끝! 이었습니다. 그러나 순열은 순서를 중요시 생각하기 때문에 2 부터 시작하는 순서도 2 1 가 나와줘야합니다. 이를 이해해야합니다. #include #include #define MAX 4 using namespace std; vector num; vector result; bool visited[5] = { false, }; void dfs(int cnt) { if (cnt == MAX) { for (in.. 유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 나눕니다. 2로 나누겠죠. 그럼 2 4 가 되고 이를 또 2로 나누면 1 2 가 되며 이때 마지막으로 더 나누어지는 수가 없으면 지금까지 나눈 수들을 곱한 값이 최대공약수 입니다. 이는 사람머리로는 간단하지만 알고리즘적으로 생각하면 복잡합니다. 이를 타개하기 위해 무려 기원전 유클리드라는 천재가 발명한 것이 유클리드 호제법 입니다. 먼저 유클리드 호제법의 원리는 다음과 같습니다. 1980 , 168 의 최대공약수를 구한다면 1980 % 168 = 132 -> 나누어 떨어지지 않습니다. 즉 최대공약수는 168이 아닌.. 이전 1 2 3 다음
