Algorithm/Basic7 [Algorithm] LCS (Longest Common Substring / Subsequence) 알고리즘 LCS란? LCS는 최장 공통 문자열(Lognest Common Substring) 또는 최장 공통 부분 수열(Longest Common Subsequence)을 의미한다. 전자는 연속된 문자열에 대한 것을 뜻하고 후자는 연속되지 않은 문자열이 포함될 수 있다. 최장 공통 문자열 (Longest Common Substring) 최장 공통 문자열을 구하는 과정은 다음과 같다. 문자열 A의 i번째 문자와 문자열 B의 j번째 문자를 비교한다. 두 문자가 같다면 ( A[i] == B[j] ) dp[i][j]에 dp[i-1][j-1] + 1을 대입한다. 두 문자가 다르다면 ( A[i] != B[j] ) dp[i][j]의 값을 0으로 설정한다. 과정중에 구한 최댓값이 최장 공통 문자열의 길이가 된다. 공통 문자열은.. 2022. 5. 1. [Algorithm] 세그먼트 트리 (Segment Tree) 세그먼트 트리란? 세그먼트 트리는 완전 이진 트리를 기반으로 주어진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조이다. 각 노드는 구간, 혹은 그 구간의 정보(구간합, 구간의 최솟값 등에 대한)를 저장하고 있는 자료구조이다. 리프 노드들은 길이가 1인 각각의 구간을 갖고 있고 부모 노드는 자신의 자식들의 구간의 합을 갖고 있으며 모든 구간은 연속적이다. 루트는 전체 구간을 포함하게 된다. 세그먼트 트리의 시간 복잡도 -> O(logN) 세그먼트 트리는 한 번의 연산에 O(logN)의 시간복잡도를 가진다. 만약 0번부터 7번 인덱스까지의 원소의 합을 구한다고 가정해보자. 완전탐색으로 값을 구할 경우 총 7번의 연산이 필요하다. 하지만 세그먼트 트리를 사용하면 루트 노드에 0~7까지의 구간합을 갖고 있고 따.. 2022. 4. 22. [Algorithm] 위상 정렬 (Topology Sort) 위상 정렬이란? 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬의 예시로는 '선수과목을 고려한 학습 순서 결정'이 있다. 어떤 학부의 커리큘럼 상 'A' 과목을 들어야 'B' 과목을 들을 수 있고 'B' 과목을 들어야 'C' 과목을 들을 수 있다고 가정해보자. 이 경우, 'A' -> 'B' -> 'C'와 같이 표현할 수 있다. 즉, 'C' 과목을 수강하기 위해서는 'A' 과목을 먼저 수강하고 다음으로 'B' 과목을 수강해야 하는 것이다. 위상 정렬을 하기 위한 조건은 다음과 같다. 간선이 방향성을 가진 그래프여야 한다. 그래프 내부에 순환(Cycle)이 .. 2022. 4. 11. [Algorithm] 최장 증가 부분 수열 (LIS) 최장 증가 부분 수열이란? 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로 몇 개의 숫자들을 뽑아서 부분수열을 만들 수 있다. 이렇게 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어 [5, 2, 1, 4, 3, 5] 라는 수열이 있다고 가정해보자. 해당 수열에서 최장 증가 부분 수열에 해당하는 수열은 무엇일까? 세번째에 있는 숫자 1을 꺼낸다. 다섯번째에 있는 숫자 3을 꺼낸다. 여섯번째에 있는 숫자 5를 꺼낸다. 이렇게 만들어진 수열 [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이 된다. 이렇게 어떤 수열에서 최장 증가 부분.. 2022. 3. 23. [최단경로 알고리즘 - 3] 벨만 포드 알고리즘 * 벨만 포드 알고리즘이란? 시작 정점으로부터 다른 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 벨만 포드 알고리즘의 특징은 다음과 같다. 1. 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다. 2. 음수 사이클의 존재 여부를 알 수 있다. 음수 사이클 안에서 무한루프를 도는 경우를 알 수 있는 방법은, 그래프 정점의 개수를 V라고 할 때 인접 간선을 검사하고 거리 값을 갱신하는 과정을 V-1 번으로 제한하면 가능해진다. 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거쳐 가는 최대 간선 수는 V-1개이기 때문에 V번째 간선이 추가되는 순간 사이클이라고 판단할 수 있게 된다. 벨만 포드 알고리즘의 시간 복잡도는 O(VE)이다. 매번 모든 간선을 전부 확인하기.. 2021. 11. 14. [최단경로 알고리즘 - 2] 플로이드 워셜 알고리즘 * 플로이드 워셜 알고리즘이란? 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 이번에 알아볼 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점에서 다익스트라 알고리즘과 다르다. 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 플로이드 워셜의 총 시간 복잡도는 O.. 2021. 11. 11. 이전 1 2 다음
