1. 접미어 배열 텍스트의 접미어들을 사전식으로 나열한 배열 파이썬에서는 리스트로 구현한다. 접미어 트리보다 메모리를 효율적으로 사용하지만 다소 느리다. 텍스트 인덱싱, 데이터 압축, bio-informatics등의 다양한 분야에서 사용한다. 예시) s = abab b, ab, bab,b abab => 접미어 사전순 정렬 : ab, abab, b, bab => 접비어 배열 : [3, 1, 4, 2] 2. 접미어 배열 복잡도 O(n)의 메모리 크기 O(nlogn) 시잔에 생성 텍스트 T에 패턴 P의 존재를 O(|P| + logn) 시간에 계산 3. 접미어 배열 장점 생성 방법이 접미어 트리에 간단하다. 적은 메모리로 구현 가능 2개의 선형 크기의 리스트로 구성 전형적으로 접미어 트리에 비해 1/4크기의 메..

1. 접미어 트리 하나의 문자열의 모든 접미어들을 포함하는 트라이(Trie)의 압축된 표현 문자열 연산에 필요한 알고리즘을 빠르게 구현할 수 있다. 응용 문자열 매칭(Exact string matching) 부분 문자열 매칭(Substring matching) 최장 공통 부분 문자열(Longest common substring of 2 strings) 예시) 문자열 S = {xabxac}에 대한 접미어 트리 길이가 6이므로 6개의 접미어가 존재 단말노드에는 접미어의 시작위치를 저장한다. 루트를 제외한 내부 노드는 최소 2개의 자식을 갖는다. 각 간선은 문자열 S의 부분문자열 라벨(label)이 부여된다. 한 노드에서 나가는 두개의 간선이 같은 문자열 라벨을 가질 수 없다. 루트에서 단말노드 i까지 경로에..

1. 트라이 정보 검색에 사용된 자료구조 문자열의 집합을 표현하는 트리 다음 5개의 문자를 하나의 트라이로 표현. 각 간선은 하나의 문자에 대응 같은 노드에 나오는 간선들은 같은 레벨을 갖지않는다. 각 문자열을 단말 노드에 대응하고 문자열의 개수만큼 단말 노드가 존재한다. 2. 접미어 트라이 문자열의 모든 접미어를 Trie로 표현 길이가 n인 문자열 A = a0 a1 a2 ... an-1 ai ai+1 ai+2 an-1인 n개의 접미어 접미어 트라이를 이용한 문자열 연산 부분 문자열 검사 두 접미어의 최장 공통 접두어 찾기 사전적 순서로 정렬된 k번째 접미어 찾기 부분 문자열 검사 'abac' 문자열 접미어 트라이가 있을 때, 어떤 문자열이 부분 문자열인지 검사하는 방법은 한 문자씩 루트에서 대응되는 간..

1. 문자열 처리 예제) 다음 중 x안에 y가 존재하는지 찾아보자. 2. 문자열 매칭(패턴 매칭) 텍스트 문자열(t)에서 패턴 문자열(p) 포함 여부를 찾는 것. 고지식한 패턴 검색 알고리즘 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 파이썬의 패턴 매칭 3. 고지식한 알고리즘(Brute Force) 텍스트 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 # t : 텍스트 # p : 패턴 # N : 텍스트의 길이 # M : 패턴의 길이 def BruteForce(t, p): N = len(t); M = len(p) i = 0 # 텍스트 인덱스 j = 0 # 패턴 인덱스 while i < N and j < M: if t[i] != p[i]: # 다..

자주 수행되는 작업들 디렉토리 경로 따라가기 디렉토리 내에 존재하는 파일들 나열하기 특정 파일의 존재 유무 판별하기 해당 작업들은 시스템의 성능 저하의 원인이 된다. 이 작업들은 검색에 기반해서 수행되는 작업들이므로 어떻게 해결해야할까. 1. 해싱 특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 방법이다. O(1) 시간 복잡도 1. 직접 번지 테이블 직접 번지 테이블(배열)에 저장하는 경우 전체 키(key)들의 집합(U)이 작은 경우에 효율적이다. 키 k가 테이블(T)에서 위치 k에 저장 테이블(배열)의 크기 = 집합 U의 크기 그러나 전체 키 값들의 집합 U가 클 때, 현실적인 컴퓨터 메모리 공간에서 테이블 T를 생성하는 것은 불가능하다. 또한 실제 저장되..

1. 백트래킹 2. 그래프의 기본과 탐색 3. 그래프의 최소 비용 문제 1. 백트래킹 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는다. 2. 그래프의 기본과 탐색 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 1) 깊이 우선 탐색(DFS) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 너비 우선 탐색(BFS) 시작 정점에서 인접한 정점을 먼저 모두 차례로 방문 3. 그래프의 최소 비용 문제 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 다익스트라 알고리즘..

3주차 스터디 계획 https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 주 공부할 내용은 문자열 탐색입니다! 파이썬은 타 언어에 비해서 문자열을 다루는데 굉장히 강력한 언어입니다. 그러면 이러한 파이썬의 특성을 이용해서 문자열 탐색을 공부해봅시다. 1. 문자열 탐색 1) 학습 목표 1. 해싱에 대한 기본 개념에 대해 이해한다. 2. 문자열에서 패턴을 탐색하는 주요한 알고리즘에 대해 이해한다. 3. 트라이, 접미어 트리, 접미어 배열에 대해 학습하고 문자열 ..

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 최단 경로 간선의 가중치가 있는 directed graph가 있을 때, 두 정점 사이의 경로들 중 간선의 가중치가 합이 최소인 경로 단일 시작점 최단 경로 문제 출발점에서 다른 모든 정점들에 이르는 최단경로를 구하는 문제 다익스트라 알고리즘 : 음의 가중치 허용 안함. 밸만 포드 알고리즘 : 음의 가중치 허용, 음의 사이클은 허용 안함 모든 쌍 최단 경로 문제 모든 정점 쌍 간의 최단 경로를 구하는 문제 플로이드-워샬 알고리즘 : 동적계획..

1. 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 정점이 n개인 그래프에서 n-1개의 간선을 선택하는 방식 초기 상태는 n개의 정점들이 하나의 트리가 된다. 하나의 정점을 포함하는 n개의 상호 배타 집합이 존재 간선을 선택하면 간선의 두 정점이 속한 트리가 연결되고 하나의 집합으로 합쳐진다. 사이클이 생기면 안된다. 두 정점이 같은 집합의 원소인지 검사해야한다. 동작과정 최초, 모든 간선을 가중치에 따라 오름차순 정렬 최소 가중치 간선부터 선택하면서 트리 증가 사이클이 존재하면 다음 가중치 낮은 간선 선택 n-1개의 간선이 선택될 때 까지 (2) 반복 소스코드 # G : 그래프 def mst_kruskal(G): mst = [] # 선택된 간선 집합, 공집합으로 ..

1. 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 임의의 정점을 하나 선택해서 시작 선택한 정점들과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 (2) 반복 두 종류의 상호 배타 집합(disjoint set)이 필요 트리 정점 : 최소 신장 트리에 선택된 정점들 비트리 정점 : 선택되지 않은 정점들 소스코드 # G : 그래프 # s : 시작 정점 def mst_prim(G, s): key = [INF] * N # 가중치를 무한대로 초기화 pi = [None] * N # 트리에서 연결될 부모 정점 초기화 visited = [False] * N # 방문 여부 초기화 key[s] = 0 # 시작 정점의 가중치를 0으로 ..