[Algorithm] - 문자열 탐색 알고리즘 : KMP
2022. 11. 7. 00:43
Problem Solving/Algorithm
이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열을 검색할 때, 특정 단어를 검색엔진에서 검색할때도 사용될 수 있다. 해당 알고리즘의 시간복잡도는 O(N+M)을 가진다. 구현 KMP 알고리즘은 접두사(prefix)와 접미사(suffix)의 개념을 활용하여 실패함수 테이블을 만들고, 테이블을 활용하여 반복되는 문자열을 건너뛰면서 패턴을 찾는 알고리즘이다. 접두사와 접미사에 대해 간단하게 정리해보고자 예를 들어보겠다. "abacabab"라는 문자열이 있다고 가정하자. 우리는 각 문자의 길이에 따라 접두사와 접미사가 일치하는 최대 길이를 테이블에 저장할 것이다. 실패함수 테이블을..
[Algorithm] - 문자열 검색 알고리즘 : Naive String Search
2022. 10. 21. 05:54
Problem Solving/Algorithm
이론 문자열 검색 알고리즘이란, 어떤 문자열 S에서 패턴 P가 있는지 찾아내는 알고리즘이다. Naive String Search 알고리즘은 문자열 검색 알고리즘 중에 효율이 좋지 않지만, 가장 구현하기 쉽고 작은 입력이라면 충분히 고려해볼만 한 알고리즘이다. 전체 문자열 S의 길이를 N, 찾고자하는 패턴 P의 길이가 M이라고 할때, 최악의 경우 O((N-M)*M)의 시간 복잡도를 갖는다. 구현 전체적인 흐름은 아래와 같다. 1. 문자열 S의 첫번째 문자와 패턴 P의 첫번째 문자를 비교하여 같다면 다음 문자를 비교한다. 2-1 다음 문자가 같다면 그 다음 문자를 비교한다. 2-2 다음 문자가 같지 않다면, 패턴 P를 한칸 밀어서 문자열 S의 두번째 문자와 패턴 P의 첫번째 문자를 비교한다. 3. 위와 같은..
[Algorithm] - Topology Sort(위상정렬)
2022. 10. 12. 08:41
Problem Solving/Algorithm
위상정렬(Topology Sort) 란 ? 위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 그래프를 방향을 거스르지 않도록 나열하는 것이다. 아래 그림을 참고하자. 위상정렬을 가장 잘 설명해줄수 있는 예로 대학교의 선수과목 구조를 예로 들 수 있다. 만약, 특정 과목을 듣기위해 필요한 선수 과목이 있다면, 그 선수과목부터 수강해야 한다. 이때 위상정렬을 사용하면 올바른 강의 순서를 찾아 낼 수 있다. 그래프의 구조에 따라 여러개의 정렬이 나타날 수도 있다. 위상정렬을 사용하기 위해선 시작노드를 특정하기 위해 DAG(Directed Acyclic Graph)여야만 한다. DAG는 사이클이 존재하지 않고, 하나의 방향만을 가지는 그..
[Algorithm] - Dijkstra(다익스트라) 알고리즘
2022. 10. 2. 04:52
Problem Solving/Algorithm
이론 Dijkstra(다익스트라) 알고리즘이란, 그래프의 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘(최단경로 문제)이다. 처음 작성된 알고리즘은 시간복잡도 O(N^2)을 가지는데, 이후 우선순위큐(=힙트리)를 이용한 개선 알고리즘이 나오면서 O(NlogN)으로 개선되었다. 다익스트라의 특징은 음의 가중치가 없다는 점이다. 따라서 현실세계에 적용할 수 있는 효율적인 알고리즘이라고 할 수 있다. 그래프의 방향은 상관없으나, 가중치가 하나라도 음수라면 다익스트라 알고리즘을 사용할 수 없다. 이때는 조건에따라 벨만-포드 알고리즘을 사용하여 최단거리를 구할 수 있다. 또한, 다익스트라 알고리즘은 하나의 노드로부터 최단 경로를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍..
[Algorithm] - Kruskal's Algorithm(최소 스패닝 트리)
2022. 9. 13. 23:46
Problem Solving/Algorithm
이론 크러스컬 알고리즘은 Union-Find 알고리즘을 사용하기때문에 만약 Union-Find에 대해 잘 모른다면 [Algorithm] - Union-Find(Disjoint-set) 이론 여러개의 집합이 존재 할때, 두개의 집합을 선택해서 같은 그래프에 속하는지 판단하는 알고리즘이다. 간단하게 이야기 하자면, 교집합이 있다면 한개의 집합으로 보게 하겠다는 의미이다 mocha-bro.tistory.com 위 포스트를 한번 읽고 오면 이해하는데 수월 할 수 있다. 크러스컬 알고리즘? 크루스칼 알고리즘?을 정리해보려고 한다. 위 알고리즘의 이론은 최소 비용으로 신장 부분 트리(Spanning SubTree)를 찾는 알고리즘이다. 아래 나무위키에 크러스컬 알고리즘의 단계 별 예제가 있어서 가져왔다. 간단하고 ..
[Algorithm] - Union-Find(Disjoint-set)
2022. 9. 13. 23:24
Problem Solving/Algorithm
이론 여러개의 집합이 존재 할때, 두개의 집합을 선택해서 같은 그래프에 속하는지 판단하는 알고리즘이다. 간단하게 이야기 하자면, 교집합이 있다면 한개의 집합으로 보게 하겠다는 의미이다. 예를들어, A,B 집합이 다음과 같이 있다고 했을때 A = {1,2} , B = {2,3} 2라는 교집합이 있으므로 {1,2,3} 한개의 집합으로 보겠다는 것이다. 이때 집합을 병합하는 부분이 Union, 집합에 속해있는지 확인하는부분이 Find로 볼 수 있다. 두개가 함께 사용되어 Union-Find라는 이름이 붙었다. Disjoint-Set이라고도 불린다. 이름만 다르고, 동일한 알고리즘으로 볼 수 있다. 구현 다음과 같이 노드들의 간선이 주어졌다고 예를들어 설명하겠다. {1,2}, {2,3}, {3,4}, {1,5}..
[Algorithm] - LIS(Longest Increasing Subsequence)
2022. 8. 19. 13:45
Problem Solving/Algorithm
Algorithm - LIS(Longest Increasing Subsequence) 코딩테스트 문제를 풀다보면 자주 마주치는 문제 알고리즘 유형에 대해 정리해보려고 한다. 첫번째로 정리할 내용은 **LIS(Longest Increasing Subsequence)**이다. LIS(최장 증가 부분 수열) 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. LIS 란 LIS라는것은 한국말로 번역하면 최장 증가 부분수열이라고 할 수 있다. 말로만 하면 제대로 이해가 안될 수 있다. 예를 들어 설명하도록 하겠다. 아래와 같이 임의의 수열이 주어졌다고 하자. 위 수열에서 숫자 몇 개를 제거해서 아래와 같이 부분 수열을 만들 수 있다. 2 6 8 3 3 4 5 1 2 3 4 5 등등.. 위와 같은 수열들..