여름의 서재

- 백트랙킹 해결책에 대한 후보를 구축해 나아가다 가능성(promising)이 없다고 판단되는 즉시 후보를 포기하고 다른 후보군으로 넘어가며 정답을 찾아가는 알고리즘 DFS + Pruning(가지치기). 보통 DFS의 재귀로 구현함. 안 되는 조건은 없애면서 탐색하기 때문에 시간복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간복잡도를 줄일 수 있음. - 절차 1. *상태 공간 트리의 깊이우선 검색 실시 2. 각 노드가 유망한지 점검 3. 유망하지 않으면 , 그 노드의 부모 노드로 돌아가서 검색 계속 *상태 공간 트리: 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리 활용 예제 ex) N queen 문제 : NxN 크기의 체스판에 N개의 퀸을 서로 공격할수 없도록 배치하는 문제 -..

- 동적 계획법 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있음. ( Memoization: 메모이제이션 ) 완전 검색을 좀 더 효율적으로 하는 방법 분할 정복은 하향식인 반면 동적 계획법은 상향식으로 접근해야 함 🔍 동적 계획법 적용 문제 조건 1. 중복 부분문제 구조 : 동적 계획법은 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제 해결 2. 최적 부분문제 구조 : 주어진 문제가 최적화의 원..

- 투포인터 리스트에 순차적으로 접근해야 할 때 시작점과 끝점 위치를 기록하면서 접근 N개의 원소를 가진 배열에서 특정 조건을 만족하는 연속적인 원소들의 집합을 구하는 알고리즘 시간 복잡도: O(N) 📄 활용예제 - 특정 합을 가지는 부분 연속 수열 찾기 - 정렬되어 있는 두 리스트의 합집합 def two_pointer(lst, target): left, right = 0,0 cnt = 0 total = 0 while left target or right >= len(lst): # 이 부분율 유심히 보길 바란다. total -= lst[left] left +..

- DFS (Depth-first Search) : 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 ex) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식. 1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함 2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림 - stack을 통해서 구현 가능 def DFS(graph, root): visited = [] stack = [root] while stack: ..

- 보이어-무어 알고리즘 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘 패턴에 오른쪽 끝 문자부터 검사하고 불일치하면 패턴에서 일차는 문자를 찾아서 이동함. 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우 , 이동거리는 무려 패턴의 길이 만큼이 된다. def boyer_moore(pattern, text): M = len(pattern) N = len(text) i = 0 #반복은 최대 긴텍스트 길이 - 작은텍스트 길이 while i = 0: if pattern[j] != text[i+j]: move = find(pattern, text[i + M - 1]) # 제일 마지막 문자부터 찾기 break j = j - 1 if j == -1: # 인덱스가 -1이라는 뜻..

- KMP 알고리즘 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불이리가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함 * next[M] : 불일치가 발생했을 경우 이동할 다음 위치 시간 복잡도 : O(M +N) def getPI(pattern): pi = [0 for x in range(len(pattern))] j = 0 for i in range(1, len(pattern)): while j > 0 and pattern[i] != pattern[j]: j = pi[j - 1] if pattern[i] == pattern[j]: j += 1 pi[i] = j return pi de..

- 브루트 포스 패턴 매칭에 사용되는 알고리즘 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 시간 복잡도 : O(MN) # 1. def bruteforce(p, t): M = len(p) # 찾을 패턴의 길이 N = len(t) # 전체 텍스트의 길이 for i in range(N-M): for j in range(M): if p[i+j] == t[j]: j+=1 else: break if j == M: return i # 검색 성공 return -1 # 검색 실패 # 2. def bruteforce(p, t): M = len(p) # 찾을 패턴의 길이 N = len(t) # 전체 텍스트의 길이 i = 0 # t의 인덱스 j = 0 # p의 인덱스 w..

- 이진 탐색 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 함 def binary_search(a, key): start = 0 end = len(a) - 1 while start key: end = middle - 1 else: start = middle + 1 return False # 검색 실패 ↓재귀 함수 이용 def binary_search(a, start, end, key): if start > end: # 검색 실패 return False else: middle = ..