yoongrammer

목차 다음 순열(next permutation) 알고리즘 next permutation 은 현재 순열보다 큰 다음 순열을 찾는 알고리즘입니다. [1, 2, 3]이 최초 숫자 배열로 주어진 경우 사전순으로 배열된 모든 가능한 순열은 아래와 같습니다. 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 [1, 2, 3] = 다음으로 큰 순열은 [1, 3, 2]입니다. [1, 3, 2] = 다음으로 큰 순열은 [2, 1, 3]입니다. ... [3, 2, 1] = 가장 큰 순열이기 때문에 다음으로 큰 순열은 없습니다. 동작 방식 다음 순열을 얻으려면 피벗 포인트(Pivot Point)를 사용합니다. 피벗 포인트는 교환, 분할 등의 작업을 수행하기 위한 기준이 되는 위치나 값입니다. next perm..

목차 Lower bound & Upper bound 개념 및 구현 Lower bound와 Upper bound는 경곗값을 찾는 알고리즘입니다. Lower bound와 Upper bound는 이진 탐색을 기반으로 하기 때문에 데이터가 정렬되어 있어야 합니다. 이진 탐색을 기반으로 하기 때문에 두 알고리즘의 시간 복잡도는 O(log n) 입니다. (n: 배열 길이) Lower bound Lower bound는 특정 값의 시작 위치를 찾는 알고리즘입니다. 동작 방식 Lower bound의 동작 방식은 다음과 같습니다. 초기에 left는 배열의 시작 위치로 right는 배열의 길이로 셋팅합니다. 배열의 중간 값(mid)을 가져옵니다. 중간 값과 검색 값을 비교합니다. 중간 값이 검색 값보다 작다면 left 값을..

목차 문자열 검색 알고리즘 : Boyer Moore - Good Suffix Heuristics 알아보기 Bad character heuristics은 한 칸만 이동하는 경우가 있습니다. 이 경우 최대 이동 거리를 도출하기 위한 방법으로 Good Suffix Heuristics를 사용합니다. Good Suffix는 패턴의 문자 일부와 일치하는 텍스트의 부분 문자열을 말합니다. Good Suffix Heuristics는 세 가지 상황이 있으며 각 상황에 맞는 오프셋을 제공합니다. Case1. Good Suffix가 패턴의 다른 곳에도 있는 경우 다른 곳에 있는 일치하는 패턴 문자를 Good Suffix와 일치하도록 패턴을 이동시킵니다. 아래 그림에서 Bad character heuristics를 사용한다면..

목차 문자열 검색 알고리즘 : Boyer Moore - Bad Character Heuristic 알아보기 boyer-moore 알고리즘은 문자열 검색 알고리즘으로써 패턴의 전처리로 얻은 정보를 가지고 패턴을 가능한 많이 이동시켜 텍스트와 비교 횟수를 줄입니다. boyer-moore 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다. 그래서 기존 패턴 검색 알고리즘과 달리 boyer moore 알고리즘은 역방향 접근 방식을 사용합니다. 패턴의 마지막 문자부터 시작하여 오른쪽에서 왼쪽으로 비교를 시작합니다. 이동 위치를 정하기 위해 boyer-moore 알고리즘은 두 가지 휴리스틱을 사용합니다. Bad Character Heuristic Good Su..

목차 문자열 검색 알고리즘 : Rabin-Karp 알아보기 Rabin-Karp 알고리즘은 해시 함수를 사용하여 문자열을 검색하는 알고리즘입니다. 해시 함수를 사용하여 문자열을 숫자 값인 해시 값으로 변경합니다. ex) hash("hello") = 5. 해시 값이 다르다면 두 문자열은 다르다는 것이 보장됩니다. 하지만 문자열이 달라도 해시 값이 같을 수 있습니다. 우리는 이것을 Spurious Hit라고 부릅니다. Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요합니다. 이 특징을 사용하여 Rabin-Karp 알고리즘은 패턴의 해시값을 텍스트의 부분 문자열의 해시 값과 일치하는지 비교하는 작업을 합니다. 따라서 Rabin-Karp 알고리즘은 다음 문자열에 대한..

목차 KMP(Knuth Morris Pratt) 알고리즘 알아보기 navie 알고리즘은 최악의 경우 O(m(n-m+1))의 시간이 걸립니다. (n 패턴의 길이, m 텍스트 길이) 문자 하나하나 씩 비교하기 때문에 불필요한 문자 비교가 있을 수 있습니다. 다음은 navie 알고리즘으로 텍스트 T[]="banananobano"에서 패턴 P[]="nano"를 찾는 과정입니다. 이 동작에서 일부는 낭비입니다. i=2에서 T[3] = 'a', T[4]='n' 이라는 것을 확인했으니 i=3, 4에서 패턴 n과 비교하는 것은 불필요합니다. KMP 알고리즘은 lps(Longest Proper Prefix which is Suffix) 배열을 사용하여 문자열 검색 시 불필요한 문자 간 비교를 없애 성능을 개선시킨 알고리..

목차 Naive Pattern Searching 알아보기 naive pattern searching은 패턴 검색 알고리즘 중에서 가장 간단한 알고리즘입니다. 단순히 문자를 처음부터 끝까지 하나하나 비교해가며 패턴을 찾기 때문에 작은 문자열에서 패턴을 찾을 때 유용합니다. 구현 길이가 n인 텍스트 T안에 모든 위치에서 길이가 m인 패턴 P와 매치 여부를 검토합니다. 패턴의 길이는 텍스트의 길이보다 작거나 같아야 합니다. (m ≤ n) T[0 ... n-1] P[0 ... m-1] 패턴 P는 텍스트 T의 처음부터 n-m+1까지 이동하며 매치가 되는지 검토합니다. 패턴이 발견되면 패턴의 위치를 출력하고 다음 일치 위치를 찾습니다. 구현하면 다음과 같습니다. void naivePatternSearch (char..

목차 플로이드 와셜 알고리즘 (Floyd-Warshall Algorithm) 알아보기 플로이드 와셜 (Floyd-Warshall) 알고리즘은 최단 경로(Shortest path) 문제 중에 모든 정점 쌍(All-pairs)에 대해 최단 거리를 구하는 알고리즘입니다. 플로이드 와셜 알고리즘은 Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, 또는 WFI algorithm 이라고도 합니다. 특징 Dynamic Programming을 사용합니다. 유향 또는 무향 가중 그래프에서 최단 경로를 찾을 수 있으며 음수 사이클이 있는 경우는 찾지 못합니다. 그래프에 음수 사이클 여부를 확인할 수 있습니다. 구현 플로이드 와셜 알고리즘은 각각..

목차 벨만-포드 알고리즘(Bellman-Ford Algorithm) 알아보기 벨만-포드 알고리즘 (Bellman-Ford Algorithm)은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다. https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념 목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로 yoongrammer.tistory.com 특징 brute force str..

목차 다익스트라 알고리즘 (Dijkstra's Algorithm) 알아보기 다익스트라(Dijkstra) 알고리즘은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다. https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념 목차 최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로 yoongrammer.tistory.com 특징 음수 가중치를 가진 간선이 없어야 합니다. 탐욕 알고리즘..