LCS란? LCS는 최장 공통부분 수열(Longest Common Subsequence)이다. 이번 문제 해결기법 중간고사 5번 문제였다. 수업시간에는 DP를 생각하지 못하고 if와 절차 지향적으로 풀려고 했다. 당연히 풀지 못했다. 생각해야 할 조건이 너무 많았다. 집에 와서 알고리즘을 배워보니 간단하게 DP로 풀 수 있는 문제였다. LCS의 최장 길이 찾는 알고리즘 최장 공통 부분수열은 비교하는 두 배열을 index로 가지는 2차원 배열을 만들고 하나씩 비교해 나가는 것이다. 만약 abcde와 abcfg를 비교한다고 했을 때, 2차원 배열의 행을 abcde 열을 abcfg라고 한다. 행을 기준으로 첫 번째 문자부터 다른 문자와 모두 비교해 같은지 안 같은지 검사한다. 아래의 코드 처럼 같으면 그 전 ..

네트워크 유량 문제를 해결하기 위해서는 에드몬드 카프 알고리즘을 공부했다. BFS를 이용해 문제를 해결핬다. 하지만 에드몬드 카프 알고리즘의 시간복답도는 O(V*E^2)이다. 이럴 경우 간선이 많아지면 문제 해결 시간이 오래걸린다는 단점이 있다. 그래서 디닉 알고리즘이라는 시간 복잡도가 O(V^2*E)의 알고리즘이 있다. 오늘은 이 알고리즘을 공부해 볼려고 한다. 디닉 알고리즘(Dinic’s Algorithm) 설명 위 그래프는 동아리 시간에 배운 그래프이다. 디닉 알고리즘을 수행 하기 위해서는 먼저 레벨 그래프 부터 만들어야 한다. 레벨 그래프 시작 정점은 언제나 0이고 그와 인접한 정점은 1 또 인접한 정점은 2 로 만 들어진다. 해당 정점은 아직 레벨을 부여 받지 않은 정점이어야 한다. 현재에서 다..

네트워크 플로우 네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다. 이런 문제를 사용하는 곳은 도로망의 교통 흐름을 분석, 전자 회로의 전류, 배수관을 흐르는 유체, 유량등을 연구하는데 사용된다. 유량 : 현재 흐르고 있는 데이터의 양 용량 : 간선에 흐를 수 있는 최대 데이터의 양 이 문제를 빠르게 해결하기 위해 사용하는 알고리즘이 에드몬드 카프 알고리즘과 디닉 알고리즘이 있다. 이 중 에드몬드 카프 알고리즘 부터 공부했다. 에드몬드 카프(Edmonds-Karp algorithm) 설명 위 그래프는 동아리 스터디 시간에 애드몬드 카프 알고리즘을 배울 때 쓴 예시 그래프이다. A에서 D로 갈 때 0/3 이라는 소리는 현재 유량이 0 용량이 3이라는..

일단 알고리즘을 설명하기전 강한 결합 요소부터 설명할려 한다. 강한 결합요소 즉, SCC는 그래프에서 하나의 노드에서 시작해 다른 노드까지 갔다가 다시 자신의 노드로 되돌아 올 수 있는 최대 컴포넌트의 모임이다. 이 그래프를 보면 9에서 시작해 (4,5,7)과 (3,6,8) 과 9로 나눌 수 있다는 것을 알 수 있다. 즉, 여기서 SCC는 3개가 나온다. SCC를 찾는 알고리즘은 2가지가 있다. 그 중 한가지인 코사리주의 알고리즘은 학교 알고리즘 시간에 배웠다. 그 때 교수님께서 다른 방법인 타잔 알고리즘이 있다고 한 것이 기억에 난다. 운이 좋게도 이번 동아리 스터디에서 타잔 알고리즘에 대해 알려줘 공부해 보았다. 코사리주 알고리즘 코사리주 알고리즘은 dfs를 2번하여 강한 결합 요소를 찾는 것이다. ..

학교 동아리에서 매주 배우는 알고리즘을 정리해 볼 것이다. 그 뒤 동아리에서 추천해준 백준문제를 풀어 볼 것 이다. 사용하는 경우 수열에서 임의의 구간에 대한 최대값, 최소값, 합, 곱 등을 빠르게 구할 때 (세그먼트 트리) 수열에서 임의의 구간에 대한 업데이트를 빠르게 할 때 (레이지 세그먼트 트리) 세그먼트 트리 모습 수열 [5,7,3,2,9,8] 을 합의 세그먼트 트리 모습으로 나타내면 이런 모습으로 보여진다. 리프 노드가 수열이고 다른 노드가 합을 나타탠다. 트리는 배열로 나타낼 수 있다. 인덱스 1 의 왼쪽 자식이 2 오른쪽 자식이 3 이런 식이다. 즉, node x의 왼쪽 자식 노드는 2x, 오른쪽 자식 노드는 2x+1이다. 위 트리를 배열로 나타내면 이렇게 나타낼 수 있다. 세그먼트 트리 사..