알고리즘

문자열 패턴 매칭 알고리즘

고지식한 알고리즘 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식 시간 복잡도 O(MN) 라빈-카프 알고리즘 문자열 검색을 위해 해시 값 함수를 이용 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교 최악의 시간 복잡도 O(MN), 평균적으로 선형에 가까운 빠른 속도 ,대략 O(M+N) 숫자 문자열 : 6843212431 찾으려는 패턴 : 4321 패턴의 해쉬값을 계산 -> 각 자리의 숫자에 자리값을 곱하여 더함 ("4321"은 정수 4321이 됨) 찾고자 하는 문자열에서 4자리씩 해쉬값을 계산 -> (6843, 8432...) 새로 추가되는 문자와 그전에 읽었던 값을 이용해서 해쉬값을 구함 ((6843 % 10..

최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜)

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 단일 출발 최단 경로 : 어떤 하나의 지점에서 나머지 모든 지점으로 경로 단일 도착 최단 경로 : 모든 지점에서 어떤 하나의 지점으로 경로 (간선을 뒤집으면 단일 출발 최단 경로 문제와 같음) 단일쌍 최단 경로 : 모든 지점 쌍들 사이의 최단 경로 BFS 가중치가 없거나 모든 가중치가 동일한 그래프에서 사용 다익스트라 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 에서 사용 벨만-포드 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착에서 사용 플로이드-워셜 전체 쌍 최단 경로에서 사용 다익스트라 최단 경로 ..