푸으름

Algorithm 공부 #27 - KMP알고리즘 ✏️ 단순 문자열 비교 알고리즘 말 그대로 단순히 for문을 돌리면서 문자열을 하나하나씩 비교하는 알고리즘 하지만 이렇게 돌리게 되면 두 문자열의 길이를 n과 m이라고 했을 때 시간복잡도가 O(n*m)이고 n과 m이 1,000,000이상만 넘어가도 많은 시간이 걸리게 되는 단점이 있음 먼저 긴 문자열을 parent(BCDEF)라 하고 찾을 문자열을 DE라고 하면 가장 먼저 찾을 문자열을 parent맨 앞에 위치시키고 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 정답 이런 식으로 비교를 하게 되면 짧은 문자열은 상관이 없지만 문자열이 길어질수록 시간이 오래 걸리게 됨 ✏️ KMP 알..

Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알고리즘 이분 그래프는 두 개의 정점 그룹이 존재할 때 모든 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프 이러한 이분 그래프에서 예를 들어, 한 그룹은 X그룹, 다른 한 그룹은 Y그룹이고 간선의 방향은 X->Y라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것 ✏️예시 먼저 알파벳 그룹과 숫자 그룹이 있다고 가정을 하면 A에서 갈 수 있는 숫자는 1과 3 B에서 갈 수 있는 숫자는 1과 2 C에서 갈 수 있는 숫자는 5 D에서 갈 수 잇는 숫자는 3 E에서 갈 수 있는 숫자는 2 A부터 매칭을 시작하면 각 점에서는 한 개의 숫자만 갈 수 있으므로 A는 1과 연결(총..

Algorithm 공부 #22 - 최소 공통 조상(Lowest Common Ancestor) 최소 공통 조상(lowest common ancestor) ● 최소 공통 조상 : 임의의 두 노드를 선택 후, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드 ● 선택된 누 노드의 깊이가 다른 경우: 더 깊은 노드를 부모 노드로 1개씩 올려 주면서 깊이를 맞춰줌 이때, 두 노드가 같다면 해당 노드가 최소 공통 조상이므로 탐색 종료 최소 공통 조상 빠르게 구하기 ● 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에는 한 단계씩 올려 주는 방식이었다면 이 방식은 2^k씩 올라가면서 맞춰주는 방식 ● 기존에 자신의 부모 노드만 저장해 놓던 방식에서 ..

Algorithm 공부 #15 - 그래프(위상 정렬) 위상 정렬(Topology Sort) ● 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 ● 항상 유일한 값으로 정렬되지 않음 ● 진입 차수 : 자기 자신을 가리키는 에지의 개수 ● 원리 파악하기 노드는 5개이고 각 노드는 1,2,3,4,5 1번 노드는 2번과 3번 노드를 / 2번 노드는 4번과 5번 노드를 / 3번 노드는 4번 노드를 4번 노드는 5번 노드를 가리키는 그래프가 있다고 가정하기 진입차수 배열 D[N] 1 2 3 4 5 0 1 1 2 2 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하기 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼주기 이 과정을 모든 노드의 ..