minkylee

서론  String Matching (문자열 매칭) 알고리즘은 주어진 텍스트에서 특정 패턴을 찾을 때 사용하는 알고리즘이다.  대표적인 문자열 매칭 알고리즘에는  브루트 포스 알고리즘KMP 알고리즘Rabin-Karp 알고리즘Boyer-Moore 알고리즘Sunday 알고리즘등이 있으며 여기서는 KMP 알고리즘에 대해 알아보려고 한다. KMP 알고리즘은 Knuth , Morris, Pratt 3명의 사람이 설계한 알고리즘으로, 전체 문자열에서 특정 문자열을 찾는 알고리즘이다. 시간 복잡도는 N(전체 문자열 길이) + M(패턴 문자열 길이) 가 나온다. 결과값으로는 다음과 같이 나올 수 있으며 필요한 값을 반환시키면 된다!인덱스 리스트 : 패턴이 텍스트 내에서 발견된 모든 시작 위치를 반환불리언 값 : 패턴이..

유전학 알고리즘이란? 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아가는 최적화 방법 수학적으로 명확하게 정의되지 않은 문제에도 적용할 수 있어 다양한 응용에서 매우 활발히 이용되고 있음 염색체 : 하나의 해유전자 : 염색체 구성 요소적합도 : 어떠한 염색체가 갖고 있는 고유값으로 치환하여 유전학 분야 뿐만 아니라 TSP, Knapsack 에도 응용 가능하다. 알고리즘의 구조현재 존재하는 염색체들의 집합으로부터 적합도가 가장 좋은 염색체를 선택하고, Solution space에서 선택된 염색체가 나타내는 방향으로 탐색을 반복하면서 최적해를 찾아간다. 초기 염색체 집합 생성적합도 계산자손 생성자손들 적합도종료조건 판별종료조건에 맞지 않을 경우 : 3번으로 돌아간다.종료조건일 경우 : 가..

개념다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다. 드론이나 로봇 차량의 인공지능을 위해 개발되었다.  A* 알고리즘은 현재 상태의 비용을 $ g(x) $  현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 $ h(x) $ 라고 할 때, 둘을 더한$ f(x) = g(x) + h(x) $ 가 최소가 되는 지점을 우선적으로 탐색하는 방법이다.  $ f(x) $ 가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다.  휴리스틱 함수 $ h(x) $ 에 따라 성능이 극명하게 갈리며, $ f(x) = g(x) $ 일 때는 다익스트라 알고리즘과 동일하다.  다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘A* : 가중치 그래프, 시작 노드에서 ..

그리디 알고리즘 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자. 예를 들어 5개의 도시를 모두 한 번씩만 거쳐서 여행한다고 가정하자, 기름값을 아끼기 위해 가장 짧은 경로를 선택해야한다고 하면, 이 문제를 해결하기 위해 여러 방법을 사용할 수 있다. 모든 경로를 검사하는 브루트 포스를 이용해 답을 구하거나, 외판원 순회같은 복잡한 전략을 쓸 수도 있고 " 지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다 " 는 방법, 즉 그리디 알고리즘을 쓸 수도 있다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 전혀 없다. 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될..

행렬 곱셈 정사각 행렬 A, B를 가지고 곱셈을 한다고 생각해보자. 행렬곱 C = AB는 다음과 함께 정의된다. 이 때 i = 1, ... ,m, j = 1, ..., p에 대해 C의 성분은 다음과 같이 정의된다. 이는 곧 A의 i번째 행과 B의 j번째 열의 성분들을 각각 곱해 더한 것과 같은데, A의 i번째 행과 B의 j번째 열의 스칼라곱인 것이다. 그런고로 AB는 다음과 같이 쓸 수도 있다. 3중 반복문이 행렬의 크기 n만큼 돌기 때문에 n x n 크기의 두 행렬을 곱하면 O(n^3) 의 시간이 소요된다. 줄이는 방법이 없을까? Strassen algorithm (슈트라센 알고리즘) 행렬의 덧셈이 곱셈보다 더 빠른 점을 이용하기 위해 쪼갠 행렬들의 곱셈 횟수를 줄이고 덧셈 횟수를 늘린다. 곱셈은 $ ..

d-차원 안의 n개의 점이 주어질 때 서로 거리가 가장 짧은 두 점을 구하는 문제이다. 많은 응용 프로그램의 근본적인 문제이며 많은 알고리즘의 핵심 단계이다. 1-Dimension Problem 정렬을 통해 O(nlogn)의 시간 복잡도로 풀이가 가능하다. 그러나 정렬하는 것은 더 높은 차원일 때 문제를 풀 수 없다. 1D를 통한 분할과 정복을 개발해보자 모든 p ∈ S1, q ∈ S2에 대해 p < q가 되도록 점 S를 두 세트로 나눈다. S1에서 가장 가까운 쌍 (p1, p2)를 재귀적으로 계산하고 S2에서 (q1, q2) 를 계산한다. 그리고 S1에서 한개의 점, S2에서 한개의 점을 사용하여 중간영역까지 고려해준다. (p3, q3) δ이지금까지 발견된 가장 가까운 쌍이라고 했을 때 δ = min(..

분할 정복이란? 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음, 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합 정렬이 있다. 그림에서와 같이 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화 할 수 있다. 분할 : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. 마스터 정리 점화식을 해결하기 위한 일반적인 방법 중 하나로, 분할 정복 알고리즘에서 주로 사용된다. 점화식이 특정한 ..

알고리즘이란? 컴퓨터 프로그램 특정 작업 (ex. 정렬)을 해결하는 개별 모듈로 구성된다. 문제를 해결하기 위한 절차나 방법, 더 정확한 정의로는 모든 입력값에 대해 튜링머신이 정지하게 하는 명령 표현 방법 implementation 슈도 코드 (pseudo code) Natural Language(영어, 한국어) 알고리즘 이름, Input, Outpu, 방법이 나오도록 명시 용어 정리 Correctness : 맞는 답을 찾아가는 과정 ex. n개의 도시가 있고 도시간의 거리가 포함되어 있을 때 모든 도시를 방문하고 다시 내 도시로 돌아왔을 때 이동한 거리가 최소가 되는 값을 구해라 맞는 접근법을 찾아보자! 가장 가까운 도시부터 접근해서 돌아오기 모든 방법을 검사해서 최소값을 찾기 이런식으로 맞는 답을 ..