KMP 알고리즘이란? KMP 알고리즘은 Knuth, Morris, Pratt 세 사람이 만든 알고리즘으로, 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나이다. 그렇다면 문자열 검색 알고리즘이란 뭘까? 위 사진은 웹 사이트에서 Ctrl+F 를 눌러 특정 문자열을 검색한 결과이다. 문자열 검색 알고리즘이란 말 그대로 문자열에서 특정 패턴을 찾아내는 알고리즘이다. KMP 알고리즘은 문자열에서 특정 패턴을 효율적으로 찾을 수 있다. 살펴볼 문자열의 길이가 N, 찾고 싶은 패턴의 길이가 M이라면 O(N+M)의 시간 복잡도를 가지는 매우 효율적인 알고리즘이다. KMP 알고리즘이 얼마나 효율적인지 알기 전에, 모든 문자열을 일일이 비교하는 경우를 살펴보자. 모든 문자열을 일일이 비교하는 경우(브루트..
투 포인터 알고리즘(Two-Pointers Algorithm)이란? 투 포인터 알고리즘은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻한다. 보통 l(left), r(right)나 s(start), e(end) 같은 식으로 포인터의 이름을 붙인다. 투 포인터 알고리즘을 설명하기 위해 하나의 알고리즘 문제를 소개하겠다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 백준에서 풀어볼 수..
프림 알고리즘(Prim`s Algorithm)이란? 프림 알고리즘은 크루스칼 알고리즘과 더불어 최소 신장 트리를 찾는 대표적인 알고리즘 중 하나이다. 크루스칼 알고리즘과 최소 신장 트리에 대해 잘 모른다면 이전 게시물을 보고 오자. 참고) [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)이란? 크루스칼 알고리즘 C++ 구현, 최소 신장 트리(Mi 최소 신장 트리(Minimum Spanning Tree)란? 크루스칼 알고리즘에 대해 알아보기 위해선 우선 최소 신장 트리에 대해 알아야 한다. 우선, 신장 트리(Spanning Tree)란 무방향(Undirected) 그래프의 최소 연결 부 code-lab1.tistory.com 프림 알고리즘 과정 프림 알고리즘의 과정은 아래와 같이 간단한 편이..
최소 신장 트리(Minimum Spanning Tree)란? 크루스칼 알고리즘에 대해 알아보기 위해선 우선 최소 신장 트리에 대해 알아야 한다. 우선, 신장 트리(Spanning Tree)란 무방향(Undirected) 그래프의 최소 연결 부분 그래프이다. 좀 더 쉽게 설명하자면 N개의 정점을 가지는 그래프 중 최소 간선의 수인 N-1개의 간선으로 연결된 그래프를 뜻한다. N개의 정점이 N-1개의 간선으로 연결되어 있으면 이것은 필연적으로 트리 형태를 이루게 되기 때문에 신장 트리라고 불린다. [그림 1]을 보면 5개의 정점을 가진 그래프를 4개의 간선만을 사용해 연결하면 신장 트리가 되는 것을 볼 수 있다. 신장 트리는 하나의 그래프에서 여러 개가 나올 수 있다. 최소 신장 트리는 이러한 신장 트리들 ..
벨만 포드 알고리즘(Bellman-Ford Algorithm) 벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다. 따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다. 다익스트라 알고리즘에 대해 알고싶다면 다음 포스팅을 참고하자. [알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현 다익스트라(Dijkstra) 알고리즘이란? 다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다..
다익스트라(Dijkstra) 알고리즘이란? 다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다. 다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능) 다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다. 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문) 2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 이해가 잘 가지 않는다면 아래 예시를 보면 이해가 빠를 것이다. 위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자. ..
정렬 알고리즘이란? 정렬 알고리즘은 n개의 숫자가 주어졌을 때 이를 사용자가 지정한 기준에 맞게 정렬하는 알고리즘이다. 아주 간단한 알고리즘부터 조금 복잡한 알고리즘까지, 여러가지 알고리즘을 알아보고 비교해보자. 우선 정렬 알고리즘을 비교하기 전에 stable 과 not stable의 차이, in-place와 not inplace 개념에 대해 알아보자. stable vs not stable stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻한다. 예를 들어, int arr[5] = { 7, 3, 6, 2, 3 } 과 같이 3값이 두 번 들어 있는 배열이 있다고 하자. 이것을 어떠한 정렬 알고리즘으로 정렬 했을 때 중복 된 키 값이 처음 순서대로 정렬 되었다면 stable s..
퀵 정렬(Quick Sort) 퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다. 1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다. 2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다. 3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다. 3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 ..
삽입 정렬(Insertion Sort) 삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 위와 같은 배열을 오름차순으로 정렬한다고 하자. 두 번째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다. 5와 7을 비교해 5가 더 작으므로 7을 한 칸 뒤로 옮기고 그자리에 5를 삽입한다. 세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 1을 비교해 1이 더작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다. 네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 4를..
버블 정렬(Bubble Sort) 버블 정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다. 위와 같은 배열을 오름차순으로 버블 정렬한다고 하자. 처음 7과 5를 비교해 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꿔준다. 다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다. 다시 1과 4를 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이후 4와 3을 비교했을 때 4가 더크므로 위치를 바꿔준다. 1과 3을 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게 하면 버블 정렬이 완료된다. 버블정렬의 특징 버블 ..