728x90 ALGORITHM/개념 정리15 [Algorithm] DFS, BFS 그래프 탐색 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 두 가지 방법 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) DFS (깊이우선탐색) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법 마지막에 만났던 갈림길의 정점으로 되돌아가서 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 DFS 알고리즘 시작 정점 v를 결정하여 반문 정점 v에 인접한 정점 중에서 방문하지 않는 정점 .. 2021. 10. 3. [Algorithm] DP (Dynamic Programming) 동적 계획 (DP; Dynamic Programming) 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결 Memoization 피보나치 수열을 재귀함수로 구현하는 경우 '엄청난 중복 호출이 존재한다'는 문제점이 있음 def fibo(n): if n < 2: return 2 else: return fibo(n-1) + fibo(n-2) 메모이제이션 (Memoization) 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 동적 계획법의 핵심이 되는 기술 앞의 예에서 fibo(n)의 값을 계산하자마자 저장하면(.. 2021. 10. 3. [Algorithm] 스택(Stack), 큐(queue) 스택 (Stack) 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 자료는 선형 구조를 가짐 선형 구조 : 자료 간의 관계가 1대 1 비선형 구조 : 자료 간의 관계가 1대 N (예: 트리) 후입선출구조 (LIFO; Last-In-Firsh-Out) 스택 연산 삽입 : 저장소에 자료 저장 (push) 삭제 : 저장소에서 자료를 꺼냄, 꺼낸 자료는 삽입한 자료의 역순 (pop) 스택이 공백인지 아닌지 확인 : isEmpty 스택에 원소가 있는지가 궁금하다면 연산을 새롭게 정의하지 않고 !isEmpty와 같이 사용 스택의 top에 있는 item(원소)을 반환 : peek 스택의 삽입/삭제 과정 스택 크기 이상의 자료를 push하는 경우 : overflow 자료가 없을 때 pop하는 경우 .. 2021. 10. 3. [Algorithm] 패턴 매칭 알고리즘 - KMP, 보이어-무어 고지식한 패턴 검색 알고리즘 (Brute Force) 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교 시간 복잡도 O(MN) -> 최악의 경우 텍스트의 모든 위치 패턴 비교해야하므로 p = 'is' # 찾을 패턴 (target) M = len(p) t = 'This is a book~!' # 전체 텍스트 N = len(t) def BruteForce(p, t): i = 0 # t의 인덱스 j = 0 # p의 인덱스 while j < M and i < N: if t[i] != p[j]: i -= j j = -1 i += 1 j += 1 if j == M: return i - M # 검색성공 else: return -1 # 검색실패 카프-라빈 알고리즘 고지식한 패턴 검색 알.. 2021. 8. 22. 이전 1 2 3 4 다음 728x90
