SMALL CS study/Algorithm9 9. 문자열 매칭 (패턴 매칭) 문자열 매칭(패턴 매칭) 텍스트 문자열 t에 패턴 문자열 p 포함 여부를 찾는것 알고리즘 부르트 포스 검색 알고리즘 O(MN) 카프-라빈 알고리즘 O(M+N) KMP 알고리즘 O(M+N) 보이어-무어 알고리즘 O(N), 최악 O(MN) 파이썬의 패턴 매칭 부르트 포스 검색 알고리즘 텍스트 문자열을 처음부터 끝까지 차례대로 순회하면서 일일이 비교 알고리즘 # t : 텍스트 # N : 텍스트의 길이 def BruteForce(t, p): N = len(t) M = len(p) i, j = 0, 0 while i 보이어-무어 알고리즘 text.find(pattern) 2021. 9. 7. 8. TSP 문제 비트마스크 + DP로 풀기 TSP 외판원 순회 문제 TSP 외판원 순회 문제는 대표적인 NP문제로, 완전검색으로 풀 수 있다. 이럴 경우 N!의 경우의 수가 발생하는데 N=12이상부터 폭발적으로 증가한다. 그런데 비트마스크와 DP를 활용하면 N=16까지 답을 구할 수 있다. 1. 비트마스크 비트마스크는 특정 도시를 방문했는지 여부를 저장한다. 예를 들어 도시가 3개 라면, 비트마스크가 11-일 때 뒤에서부터 인덱스를 시작하여 2, 3번 도시는 방문, 1번 도시는 미방문 상태가 된다. 비트마스크 십진수 3번 도시 2번 도시 1번 도시 1 000 0 x x x 2 001 1 x x o 3 010 2 x o x 4 011 3 x o o 5 100 4 o x x 6 101 5 o x o 7 110 6 o o x 8 111 7 o o o .. 2021. 9. 6. 7. 동적 계획법 동적 계획법 탐욕 기법과 같이 최적화 문제(최대나 최소를 찾는)를 해결하는 알고리즘 완전검색을 좀 더 효율적으로 하는 방법 재귀 + 메모이제이션 점화식을 찾으면 됨!! 작은 부분 문제들의 해들을 구함 > 해를 이용하여 보다 큰 크기의 부분 문제들 해결 > 최종적으로 문제 해결 동적 계획법 적용 문제의 요건 중복 부분문제 구조 최적 부분문제 구조 부분 문제들 사이에 의존적 관계가 존재 분할 정복과의 차이점 피보나치 수열에 DP 적용 피보나치 수열은 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있음 문제를 부분 문제로 분할 점화식으로 정의 가장 작은 부분 문제부터 해를 구함 - 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구함.. 2021. 9. 6. 6. 그래프 탐색 - DFS,BFS 그래프란? 객체와 객체 간의 연결 관계 표현 vertex + edge 로 구성 선형 자료구조나 트리 자료구조로 표현하기 힘든 N : N 관계를 가지는 구조를 표현하기에 용이 그래프의 종류 무향 그래프(Undirected Graph) 유향 그래프 (Directed Graph) 가중치 그래프 (Weighted Graph) 그래프를 표현하는 방법 인접행렬 : 두 정점을 연결하는 간선의 유무를 행렬로 표현 단점 - 정점의 개수가 커지면 인접 행렬에 필요한 메모리 크기는 n^2에 비례해서 커짐 인접 리스트 : 각 정점마다 인접 정점으로 나가는 간선의 정보 저장 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장 파이썬에서는 dictionary를 사용! key 값이 하나의 vertex가 되고, .. 2021. 9. 1. 5. 그리디 알고리즘 2021.07.22 - [Coding Test/SWEA] - [Advanced] 3. 탐욕 알고리즘 - 이론편 그리디 알고리즘 여러 경우 중 하나를 선택 → 최적이라고 생각되는 것을 선택 → 최종 해답에 도달 해 선택 현재 상태에서 부분 문제의 최적해를 구한 뒤, 부분 해 집합에 추가 실행가능성 검사 새로운 부분 해 집합의 실행가능 여부 확인, 문제의 제약 조건 위반 검사 해 검사 새로운 부분 해 집합이 문제의 해가 되는지 확인 전체 문제의 해가 완성되지 않았다면 1로 돌아가 다시 시작 최적화 문제를 해결할 수 있음 각 선택 시점에서의 결정은 지역적으로 최적의 값임 But, 최종적 해답이 최적이라는 보장은 없음! 따라서 문제 풀 때 오래 고민하고 선택해야함 탐욕 알고리즘과 동적 계획법의 비교 탐욕 알고리.. 2021. 8. 30. 4. 백트래킹 백트래킹 해를 찾는 도중에 막히면 되돌아가서 해를 다시 찾는 기법 상태 공간 트리에 대한 깊이 우선 탐색 실시 방문하는 노드가 유망한지 여부 점검 만일 선택한 노드가 유망하지 않을 경우, 해당 노드의 부모 노드로 돌아가서 검색 계속 진행 최적화 문제와 결정 문제를 해결할 수 있음 결정 문제 문제의 조건을 만족하는 해가 존재하는지를 yes/no로 답하는 문제 미로찾기, n-Queen, Map coloring, 부분 집합의 합 문제 등 최적화 문제 문제의 조건을 만족하는 최대/최소 해를 찾는 문제 미로찾기에서 최단경로 문제, 원소의 개수가 최대인 부분 집합을 찾는 문제 상태 공간 트리 해를 찾기 위한 선택의 과정을 트리로 표현 트리의 내부 노드는 최종 상태로 가는 중간 상태를 나타냄 트리의 단말 노드는 하나.. 2021. 8. 27. 이전 1 2 다음 LIST
