꾸준히 개발하자

보이어-무어 (Boyer-Moore) 보이어-무어 알고리즘은 문자열 검색 알고리즘의 하나이다. 이전 글에서 봤던 것까지 생각해보면 문자열 검색 알고리즘은 다음 3가지가 있다. 1. 브루트포스 2. KMP 3. 보이어-무어 문자열의 길이가 n, 패턴 문자열의 길이가 m일때 각각의 알고리즘의 시간복잡도를 비교해보면 다음과 같다. 1. 브루트포스는 가장 단순한 알고리즘이지만 시간복잡도가 O(mn)으로 3개 중에 가장 느린 알고리즘이다. 2. KMP는 최악의경우에도 시간복잡도가 O(n)으로 매우 빠르지만 패턴안에 반복하는 요소가 없으면 효율이 떨어진다. 3. 보이어-무어는 최악의 경우 시간복잡도가 O(mn)이지만 평균적으로 O(n)보다 빠른 시간복잡도를 갖는다. 이번에 보이어-무어까지 배우고 각각의 장단점에 따..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 6. 20:52

KMP 알고리즘 KMP알고리즘이란 문자열 "ABCABCD"가 있을때 그 안에서 문자열 "ABCD"를 찾는 알고리즘이다. 우리가 잘 알고있는 브루트포스로도 찾을 수 있지만 브루트포스는 ABCABCD에서 ABCD를 찾을때 다음과 같이 비효율 적으로 탐색을 한다. (1) ABCABCD ABCD (2) ABCABCD AABCD (3) ABCABCD AAABCD (4) ABCABCD AAAABCD 하지만 우리는 (1)에서 첫번째 문자가 'A', 두번쨰 문자가 'B', 세번째 문자가 'C'라는 것을 탐색을 통해 알았기에 굳이 (2), (3)의 경우를 탐색할 필요없이 (4)로 넘어가도 된다. 즉 우리가 탐색한 부분의 정보를 최대한 효율적으로 이용하자는 말이다. 굳이 탐색했던 'B', 'C'를 다시 탐색할 필요 없이 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 5. 04:40

다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘이란 어떤 하나의 노드에서 다른 노드들까지 가는 최단경로를 전부 찾아내는 알고리즘이다. (출발지 고정) 백준 1753번 최단경로 문제를 풀면서 공부했다. (https://www.acmicpc.net/problem/1753) 우선 알고리즘을 간략하게 보자. (문제에서 노드간의 가중치를 알려줬다는 전제에서 시작) 배열을 만들어서 모든 노드의 cost(가중치)를 INT_MAX값으로 만든다. 그리고 출발지의 cost만 0으로 바꿔주고 출발지를 방문한다. '방문한 노드에 연결된 각각의 노드들의 cost'를 '방문한 노드와 연결된 노드 사이의 cost + 방문한 노드의 cost'와 비교하여 더 작은 값을 연결된 노드의 cost로 바꿔준다. 그리고 cost의 값..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 31. 17:14

플로이드-워셜 알고리즘 다익스트라가 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이라면 플로이드-워셜 알고리즘은 모든 노드 간의 최단 경로를 구하는 알고리즘이다. 그리고 다익스트라와 다르게 음의 간선도 사용이 가능하다. 플로이드-워셜이 어떤 알고리즘인지 간단하게 보자. 노드가 a ~ e까지 5개가 있다 하고 노드를 연결하는 간선의 가중치가 각각 다르다고 하자. 만약 a -> b의 가중치가 k라 할때 플로이드-워셜 알고리즘은 a에서 b로가는 경로의 최솟값을 찾기 위해 a -> (경유지) -> b의 경우의 가중치를 k와 비교하여 최솟값을 구한다. 예를들면 여기서는 경유지에 a ~ e까지 5개를 넣어서 비교하는데 (경유지가 a 또는 b인 경우는 a -> b와 같음) 만약 a -> d -> b의 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 31. 14:55

TreeMap 우리가 쓰던 HashMap에 이진트리의 기능을 더한 자료구조이다. HashMap처럼 key와 value를 갖는 요소들로 이루어져 있고 key값을 기준으로 이진 탐색 트리처럼 정렬이 이루어진다. 그래서 key값을 기준으로 최솟값과 최댓값을 탐색할 때 시간복잡도 O(logN)으로 탐색이 가능하다. 그러나 이진 탐색 트리에서는 루트값을 기준으로 나머지 요소들이 전부 크거나 전부 작으면 탐색의 시간이 O(N)까지 늘어난다.(트리의 높이만큼의 시간 복잡도가 걸린다) 그래서 TreeMap에서는 이진 탐색 트리의 단점을 보완한 레드-블랙 트리의 자료구조를 이용한다. 레드-블랙 트리는 루트노드를 기준으로 균등하게 트리가 완성될 수 있게 규칙에 따라 트리가 만들어진다. (규칙은 https://zeddios..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 22. 21:04

래퍼 클래스 자바의 자료형은 primitive type과 reference type으로 나눠지고 primitive type에는 char, int, float, double, boolean 등이 있고 reference type에는 class, interface 등이 있다. primitive type은 Object로 다룰 수 없기 때문에 다음과 같이 Object의 하위 클래스들인 wrapper class들을 사용하여 primitive type들을 Object로 다룬다. 그리고 각각의 primitive type에 대응되는 wrapper class들은 다음과 같다. 기본타입(primitive type) 래퍼클래스(wrapper class) byte Byte char Character int Integer flo..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 16. 20:30

팀 정렬(Tim Sort) 우리가 아는 O(NlogN)의 시간복잡도를 갖는 힙 정렬, 병합 정렬, 퀵 정렬들은 같은 시간복잡도를 같지만 상황에 따라 다른 속도를 보여준다. 시간 복잡도는 실제로 C×nlogn+α 이고 상대적으로 무시할 수 있는 부분인 α를 제외하고 C에 따라 속도가 달라질 수 있다. 여기서 C는 지역성에 따라 달라지는 값으로 지역성이 좋으면 메모리를 참조할때 cache hit가 자주 발생해 속도가 빨라져 속도가 빨라지므로 이 부분이 C에 영향을 준다. 힙 정렬은 퀵 정렬에 비해 지역성이 떨어지고 불필요한 교환이 많아 보통 퀵 정렬보다 느리고 퀵 정렬은 빠른 정렬 방법이지만 최악의 경우 O(N^2)의 시간복잡도를 갖기 때문에 늘 좋은 정렬 방법은 아니다. 마지막으로 병합 정렬은 퀵 정렬에 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 3. 16. 20:16

기수 정렬 (Radix sort) 기수 정렬은 정렬 알고리즘 3에 나온 도수 정렬과 같이 데이터를 비교, 교환하지 않는 알고리즘이다. 기수란 데이터를 구성하는 기본 요소로 10진수에서는 0 ~ 9, 2진수에서는 0과 1, 알파벳 소문자의 경우 a ~ z가 기수가 된다. 기수 정렬에서는 기수의 개수만큼 Queue를 만들어 데이터들의 낮은 자릿수부터 높은 자릿수까지 순서대로 기준을 잡아 정렬하는 방법이 있다. (문자열은 가장 오른쪽 문자부터 왼쪽 문자의 순서로 기준을 잡음) 이것이 기수 정렬의 가장 전형적인 방법으로 필요에 따라 기준을 잡는 순서를 바꾸는 방법들도 있다. 하지만 우리는 처음 배우는 것이므로 앞에서 말한 전형적인 방법인 가장 작은 자릿수부터 높은 자릿수로 기준을 잡는 LSD(Least Sign..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 20. 10:03