본문 바로가기

알고리즘/분류

 (22)
문자열-KMP 관련 솔루션 [1. 개요] [2. 구현 패턴] 구현 시 헷갈리면, 최초 위치에서 탐색이 어떻게 되는지 떠올리도록 한다. [3. 예제] https://testkernelv2.tistory.com/593 https://testkernelv2.tistory.com/595 https://testkernelv2.tistory.com/596 https://testkernelv2.tistory.com/597 https://testkernelv2.tistory.com/598 https://testkernelv2.tistory.com/599
SCC 관련 솔루션 [1. 개요] SCC 의 특성 방향 그래프에서 정의 된다. 같은 SCC 에 속한 노드들은 Cycle 을 형성한다. => 같은 SCC 에 속한 노드 간 경로는 반드시 존재한다. SCC 를 연결하는 간선들을 모으면 DAG 를 형성한다. SCC 를 응용한 문제 SAT SCC 를 찾는데 사용되는 알고리즘은 아래와 같이 크게 두가지가 있다. 타잔 알고리즘 => 시간 복잡도 O(V+E) 코사라주 알고리즘 타잔 알고리즘은 한번의 DFS 를 통해 모든 SCC 를 찾을 수 있다. 따라서 타잔 알고리즘의 구현 패턴을 익히도록 한다. dfsAll 을 수행한다. 각 dfs 는 프로토 타입은 아래와 같이 작성하며, 동작은 아래와 같다. # int dfs(u int), u 에서 dfs 수행 시 가장 먼저 방문 한 방문 순서를 반..
최소 공통 조상 솔루션 [1. 개요] 최소 공통 조상 문제는 보통 트리에서 임의의 두 노드가 있을 때, 두 노드의 공통 조상을 찾는 문제이다. 트리를 대상으로 하기 때문에, 어떤 노드의 부모노드는 단 하나 만 존재하게 된다. 최소 공통 조상을 찾는 방법은 아래와 같다. 모든 노드의 Height 를 먼저 계산한다. 두 노드의 높이를 맞춘다. 두 노드가 서로 같아 질 때 까지 위로 올라 간다. => 최대 root 까지 갈 수 있다. 먼저 height 를 계산해야 한다. root 노드를 선택한다. => root 노드는 임의의 아무 노드나 선택해도 된다. => 그 이유는 아래 그림 참조 root 노드로 부터 DFS 와 같은 그래프 탐색을 이용하여, 모든 노드를 방문한다. 이 과정에서 각 노드의 height 를 계산 할 수 있다. 위 ..
위상 정렬 솔루션 [1. 개요] 사이클이 없는 연결 그래프에서 위상 정렬이 가능하다. Cycle 이 있다면 위상 정렬을 할 수 없다. DFS 로 구현하는 방법과 BFS 로 구현하는 방법이 있지만, 보통 BFS 로 구현하는 편이 좀 더 쉬운 것 같음 BFS 방식의 위상 정렬 구현 패턴을 정하도록 한다. 구현 상 그 차이점을 단순하게 정리하면 아래와 같다. DFS 로 구현 DFS 이므로 재귀로 구현 가장 먼저 방문 하는 것이 제일 첫번째로 해야 할 작업이며, 가장 마지막에 방문하는 것이 마지막으로 해야 할 작업이라 볼 수 있음 방문 순서는 vector 에 push_back() 으로 저장 시, vector 를 reverse 해야 함 => 혹은 reverse iterator 를 통해. BFS 로 구현 재귀로 구현 할 필요 없음 ..
최소신장트리 솔루션 [1. 개요] 최소 신장 트리는 아래와 같은 특징이 있다. 트리라는 자료구조의 특성이 그대로 있다. 모든 노드가 연결되어 있으며, 최소 weight 이다. 트리 형태이므로, N-1 개의 edge 를 갖는다. https://testkernelv2.tistory.com/471 최소 신장 트리를 구하기 위해 크루스칼 알고리즘과 프림 알고리즘 두가지가 있으며, 이 중, 한가지 알고리즘의 구현 패턴을 익히도록 한다. 크루스칼 알고리즘 구현 패턴 최소 힙이 필요하다. weight 가 작은 edge 부터 트리에 추가해본다. => 최소힙에서 pop() 한다. => 언어 별 최소 힙 사용 패턴을 알아야 한다. => https://testkernelv2.tistory.com/476 트리 추가시 Cycle 이 발생하면, 이..
플로이드-워셜 솔루션 [1. 개요] 일관 된 구현 패턴을 유지하도록 한다. 경유지 (k) 출발지 (u) 목적지 (v) 덧셈 간 자료형 내 오버플로우가 발생하지 않는 값을 MAX weight 로 설정하도록 한다. 경로 복원 u -> v 에서 경유지 k 가 사용 된 경우 이를 별도 배열에 저장한다. path[u][v] = k 이 후, 재귀 함수를 이용하여 u ~~~ v 경로를 구하도록 한다. => u ~~~ v => u ~~~ k ~~~ v => u ~ k 에 대한 부분 문제를 해결 => k ~ v 에 대한 부분 문제를 해결 => ... [2. 예제] https://testkernelv2.tistory.com/491 b c d e g
최단 경로(벨만-포드) 문제 솔루션 [1. 개요] 시간 복잡도 O(VE) 모든 Edge 의 relax 를 |V| 번 만큼 반복, 마지막 |V| 번째에서 relax 가 발생한다면, 음수 사이클이 있다는 것이다. 함정 벨만-포드 수행 후 어떤 노드 u 까지 가는 경로가 존재하는가? upper[u] != INF 가 아니라고 판단하면 안된다. 그래프가 아래와 같이, 완전히 연결되지 않았다면, 시작점과 연결되지 않은 상태에서, 음수 사이클이 있다면, 적당히 큰 값 M 에 대한 어떤 연산 결과가 참이라면 u 까지 가는 경로가 있다고 판단해야함. => 이 값은 문제 조건에 따라 다름... => weight 조건이 [0, K] 이고 (음수 weight 와 별개로.. 양수 weight 에 대해서만), => 전체 edge 개수가, L 개라면, => M=KL..
최단 경로(다익스트라) 문제 솔루션 [1. 개요] dfs, bfs 등과 달리 visit 여부가 필요 없다. 음수 사이클이 없다는 것이 보장된다면, 음수 weight 를 갖는 edge 에 대해서 최단 경로를 찾을 수 있다. [2. 예제] https://testkernelv2.tistory.com/486 b c d e
그래프 탐색 솔루션 [1. DFS 개요] 재귀를 이용한 구현 재귀 호출 전 방문처리를 하도록 한다. [2. BFS 개요] 큐에 푸쉬하는 순간 바로 방문처리를 바로 하도록 한다. bfs 탐색 특성 최단 경로. a b c [3. 예제] https://testkernelv2.tistory.com/478 https://testkernelv2.tistory.com/483 https://testkernelv2.tistory.com/575 https://testkernelv2.tistory.com/577 === bfs === https://testkernelv2.tistory.com/579 https://testkernelv2.tistory.com/580 https://testkernelv2.tistory.com/581 https://..
유니온 파인드 솔루션 [1. 개요] "상호 배타적 집합 == 유니온 파인드 == 분리집합" 전부 같은 표현이며, 보통 "유니온 파인드" 라는 명칭이 고유 명사 처럼 사용된다고 한다. 유니온 파인드 자료구조 구현을 위해서는 세가지 연산이 필요하다. 초기화를 제외한 연산의 시간복잡도는 거의 상수시간이 되도록 작성해야 한다. 초기화 => 각 원소가 각각의 집합에 포함되도록 한다. union => 두 원소를 하나의 집합을 합친다. find => 원소가 속한 집합을 반환한다. 위 자료구조 구현 패턴을 정의하도록 한다. 초기화 구현 패턴 int parents[] => 각 원소에 대해서 parents[i] = i 로 초기화 한다. => 자신의 부모가 자기 자신 => root int ranks[] => 각 원소가 속한 집합(트리)의 높이로..

티스토리툴바