문자열 알고리즘 - KMP 알고리즘 KMP(Knuth-Morris-Pratt) 알고리즘 불일치가 발생한 텍스트 문자열의 앞 부분은 다시 비교하지 않고 일치하는 부분 문자열부터 매칭을 수행함으로써 문자열 비교 횟수를 대폭 감소시킨 알고리즘 타겟 문자열을 대상으로 을 작성하여 타겟 문자열 내부에서 중복되는 문자열을 빠르게 찾음 타겟 문자열의 1번 인덱스 문자부터 마지막 인덱스 문자까지 확인하며 각 인덱스 문자를 추가한 부분문자열의 접두사와 접미사가 일치하는 최대 길이를 저장 부분 일치 테이블을 이용해 주어진 문자열과 타겟 문자열을 비교해 매칭이 실패했을 때 타겟 문자열 포인터가 돌아갈 인덱스를 찾을 수 있음 주어진 문자열…

희소 배열(Sparse Table) 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 데이터가 저장되지 않은 경우가 더 많은 희소 행렬과 같이, 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열을 말함 이러한 희소배열의 특징을 이용해 그래프의 사이클을 탐색해나가는 문제를 풀 수 있다. 희소 배열 알고리즘 다음과 같이 사이클이 있는 그래프가 존재하고, 특정 정점(v)에서 시작해 n개의 간선을 이동해 도착할 수 있는 정점을 구한다고 생각해보자. 일반적으로는 간선 1개를 n번씩 이동하여 도착하는 정점을 찾는 방법을 떠올릴 것이다. 하지만 위의 문제를 반복적으로 풀어야 한다면? 모든 v정점에 대해 n개의 …

구간 트리(Segment Tree) 일차원 배열의 특정 구간에 대한 질문을 빠르게 대답하는 데 활용되는 자료구조 대표적으로 구간 원소들의 합, 구간 원소들의 최솟값(RMQ, Range Minimum Query) 등에 대한 질의를 지원한다. 구간 트리 초기화 배열의 각 구간을 표현하는 이진 트리 형태 구간 트리의 루트는 배열의 전체 구간()을 표현 각 트리(i)의 왼쪽 자식(2i)과 오른쪽 자식(2i+1)은 해당 구간을 반으로 나눈 왼쪽 부분와 오른쪽 부분을 표현 리프 노드는 구간의 크기가 1인 경우 전체 구간 크기가 2의 제곱꼴이라면 노드가 개인 완전 이진 트리가 완성되겠지만, 2의 제곱꼴이 아니더라도 남는 노드는 …

퀵 정렬(Quick Sort)과 듀얼 피봇 퀵 정렬(Dual Pivot Quick Sort) 퀵 정렬의 개념 임의의 피봇(pivot)을 기준으로 해당 피봇 값보다 작은 데이터는 피봇의 왼쪽에, 큰 데이터는 피봇의 오른쪽에 배치한 뒤, 왼쪽 부분과 오른쪽 부분을 다시 퀵 정렬 방법으로 정렬하는 알고리즘 전체 데이터를 2개의 부분으로 분할한 뒤, 각각의 부분을 다시 퀵정렬하는 전형적인 원리 피봇을 기준으로 분할하기 퀵 정렬 구현의 핵심은 위 알고리즘의 부분인 전체 배열을 피봇을 기준으로 두 부분으로 분할하는 것이다. 분할의 원리는 다음과 같다. 배열의 임의의 원소를 , 가장 첫번째 원소를 , 가장 마지막 원소를 이라고…

트라이(Trie) 키와 값을 쌍으로 갖는 연관 배열 데이터를 저장하는 트리 자료 구조 주로 자연어 처리(NLP) 분야에서 문자열 탐색을 위해 사용한다. 문자열의 각각의 문자 단위로 색인을 구축한 형태이다. 트라이 원리 트라이를 이용한 문자열 저장 각 노드가 배열로 구성된 트리를 생성한다. 저장하려는 문자열의 모든 문자들을 확인하며 아래 과정을 시행한다. 루트 노드(문자 배열)에서 문자열의 첫번째 문자에 해당하는 인덱스로 이동한다. 해당 인덱스에 연결된 자식 노드가 존재하지 않는다면 새로운 노드(문자 배열)를 할당한다. 이후 새로운 노드에서 두번째 문자에 해당하는 인덱스로 이동한다. 해당 인덱스에 연결된 자식 노드가…

모든 쌍 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall) 알고리즘 그래프의 모든 정점에서 다른 정점으로의 최단 경로를 구하는 문제 가중치(양의 가중치, 음의 가중치)가 포함되어 있으며, 방향이 있는 그래프에서 최단 경로 찾기 모든 정점에 대해 다익스트라 알고리즘을 적용하여 풀 수도 있지만, 플로이드 워샬 알고리즘은 DP를 이용하여 문제를 더욱 쉽고 효율적이게 해결한다. 플로이드 워셜(Floyd-Warshall) 알고리즘 에서 까지의 최단 경로는 i에서 j로의 직접 비용과, i와 j가 아닌 다른 정점을 거치는 간접 비용을 비교하여 비용이 더 적은 값이 된다. 이때, 모든 쌍 최단 경로를 구하기 위해서는…

최단 경로 알고리즘 - 다익스트라(Dijkstra) 알고리즘 최단 경로란? 간선의 가중치가 있는 그래프에서 두 정점 사이 경로들 중 간선의 가중치 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로를 구하는 알고리즘으로는 다익스트라(Dijkstra) 알고리즘과 벨만-포드(Bellman-Ford) 알고리즘이 있음 모든 정점들에 대한 최단 경로를 구하는 알고리즘으로는 플로이드-워샬(Floyd-Warshall) 알고리즘이 있음 가중치가 없는 그래프의 탐색으로는 DFS, BFS 방법이 존재한다. 그 중 두 정점 사이 경로 중 최단 경로를 구하기 위해서는 BFS를 이용할 수 있다. 가중치가 없는 그래프에서 …

최소 신장 트리(MST)와 Kruskal 알고리즘, Prim 알고리즘 최소 신장 트리(Mimimum Spanning Tree) 신장 트리 : n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 Kruskal 알고리즘 간선을 기준으로 가중치가 작은 간선을 우선적으로 선택하며 MST를 찾는 알고리즘 로직 👇 최초에 모든 간선을 가중치를 기준으로 오름차순 정렬한다. 가중치가 가장 낮은 간선부터 선택해가며 트리를 증가시킨다.(이때, 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한…

서로소 집합(Disjoint Set)과 Union-Find 알고리즘 서로소 집합(Disjoint Set) 서로소 집합(상호배타 집합)은 서로 중복되어 포함된 원소가 없는 집합을 의미함. 다시 말해 교집합이 없는 집합! 따라서 집합에 속한 하나의 특정 원소를 통해 각 집합을 구별할 수 있고, 이 원소를 대표자(representative)라고 함. 서로소란? 수학에서의 서로소는 정수나 다항식 간 최대 공약수가 1인 관계를 말함 서로소 집합의 표현 연결 리스트 같은 집합 원소들을 연결 리스트로 관리 연결 리스트의 가장 앞에 위치한 원소를 대표자로 설정 각 원소는 집합의 대표 원소를 가리키는 링크를 가짐 트리 하나의 집합을 …

그래프(Graph) 자료구조와 탐색 그래프(Graph) 비선형 자료구조 원소들 간 의 관계를 가지는 자료구조 사물 혹은 사람, 추상적 개념 등의 관계성을 표현한 자료구조 정점(vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 차수(Degree) : 정점에 연결된 간선의 수 그래프의 유형 무향 그래프(Undirected Graph) : 간선에 방향이 없어 정점 간 연결관계만 나타낸 그래프 유향 그래프(Directed Graph) : 간선에 방향이 있어 출발 정점과 도착 정점을 나타낸 그래프 가중치 그래프(Weighted Graph) : 간선에 가중치가 부여되어 특정 정점 간 거리, 이…

트리(Tree) 자료구조와 탐색 트리(Tree) 비선형 자료구조 원소들 간 의 관계를 가지는 자료구조 원소들 간 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가며 확장되는 트리(나무) 모양의 구조 회사의 조직도, 파일 디렉토리 구조, 기계 학습에서의 결정 트리(decision tree) 등을 표현 트리의 구성 요소 및 용어 정리 구성 요소 노드(Node) : 트리의 원소 루트 노드(root node) : 트리의 시작 노드인 최상위 노드 리프 노드(leaf node) : 차수가 0인 노드, 자식 노드가 없는 노드 형제 노드(sibling node) : 같은 부모 노드를 갖는 자식 노드들 조상 노드…

Bit Masking 비트 마스킹 비트 연산자와 비트열을 이용해 자리수, 방문 여부를 체크할 수 있다 순열과 부분집합 생성에 사용되는 비트 연산자 << 연산자 : 비트로 표현된 수인 N의 비트열을 왼쪽으로 R칸만큼 이동 & 연산자 : 비트로 표현된 수인 V1 과 V2의 비트열을 각각 비교하여 두 수에 표현된 비트가 모두 1이면 1, 아니면 0 | 연산자 : 비트로 표현된 수인 V1 과 V2의 비트열을 각각 비교하여 두 수에 표현된 비트가 모두 0이면 0, 아니면 1 << 연산자를 이용하여 원하는 자리로 원소의 자리를 이동시켜 자리수, 방문 여부 마킹처리하는 용도롤 사용 가능 & 연산자를 이용하여 현재 원소가 해당…

Next Permutation 다음 순열 현 순열에서 사전순으로 다음에 올 순열을 찾는 알고리즘 알고리즘 배열을 오름차순으로 정렬 배열의 맨 뒤 원소부터 탐색하여 최초로 값이 작아지는 순간의 인덱스 찾기( : 꼭대기, i 이후로 최초로 값이 작아지는 인덱스를 타겟으로 선정) 배열의 맨 뒤 원소부터 탐색하여 타겟 원소인 이후 원소들 중, 타겟 원소보다 크되 가장 작은 원소()를 찾기 인덱스 원소와 인덱스 원소를 교환 타겟 원소 이후 꼭대기인 인덱스부터 마지막 인덱스까지의 원소를 오름차순 정렬 Next Permutation을 이용한 순열 구현 응용 - Next Permutation을 이용한 조합 구현 Next P…

완전 탐색의 삼총사 - 순열, 조합, 부분집합 완전탐색 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열하고 확인 Brute-Force / Generate & Test 경우의 수가 작을 때 유용 수행 속도는 느리지만, 해답 찾기를 실패할 확률이 낮음 순열 서로 다른 것들 중 몇 개를 뽑아 순서가 있게 나열 TSP(Traveling Salesman Problem) 등 의 시간복잡도 순열의 재귀적 구현 중복 순열의 재귀적 구현 조합 서로 다른 것들 중 몇 개를 단순히 뽑기 의 시간복잡도 조합의 재귀적 구현 중복 조합의 재귀적 구현 부분 집합 집합에 포함된 원소들을 선택 집합 원소가 n개일 때 공집합을 포함한 부분집합…