yoongrammer

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

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

목차문자열 검색 알고리즘 : 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 HeuristicGood Suffix H..

목차문자열 검색 알고리즘 : 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 T[], 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 strateg..

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