728x90 반응형 분류 전체보기148 (Brute Force) 브루트포스 알고리즘 - 문자열 패턴 매칭 포스팅에서 다룰 브루트 포스 Brute Force 알고리즘은 비교 대상 문자열을 처음부터 끝까지 모두 순회하면서 비교하기 때문에 고지식한 알고리즘이라고도 불리는 문자열 패턴 매칭 알고리즘입니다. Brute Force 시간 복잡도, 장단점, 알고리즘 파이썬 구현에 대해 알아보겠습니다. 브루트 포스란? (Brute Force) 검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회하며 문자들을 일일이 비교하는 방식의 고지식한 알고리즘입니다. 비교하고자 하는 문자열과 패턴을 한 칸씩 이동하면서 비교하여 일치 여부를 확인합니다. Brute Force 비교 과정 T: 원본 문자열 / P: 찾고자 하는 문자열 패턴 T, P 모두 첫 문자부터 비교를 시작하므로 검색 인덱스를 맨 처음 인덱스로 설정합니다. 각각.. 2021. 8. 2. (Boyer Moore) 보이어 무어 알고리즘 - 문자열 패턴 매칭 이번 포스팅에서 다룰 보이어 무어 Boyer Moore 알고리즘은 패턴 문자열의 오른쪽에서 왼쪽으로 비교하고, 불일치할 경우 정해진 이동거리만큼 점프해가며 비교하는 문자열 패턴 매칭 알고리즘입니다. 보이어 무어 알고리즘 시간 복잡도, 장단점, 파이썬 예제에 대해 알아보겠습니다. 보이어 무어 알고리즘이란? (Boyer Moore) 패턴 문자열의 오른쪽 끝 부분에서부터 왼쪽 앞부분 방향으로 문자를 비교하는 방식입니다. 보통 상황에서 문자열 앞부분보다 뒷부분이 불일치가 일어날 확률이 높다는 성질을 이용한 알고리즘입니다. 패턴 문자열에 대한 이동거리 skip 테이블을 만들어놓고 적절한 이동 거리만큼 점프해가며 비교합니다. Boyer Moore 비교 과정 찾을 패턴 : bye 탐색할 문자열 : heyhibye 1.. 2021. 8. 1. 선택 정렬(Selection Sort), 셀렉션 알고리즘 이번 포스팅에서 다룰 주제인 선택 정렬(Selection Sort)은 최솟값을 선택하여 위치를 교환하여 정렬하는 방법으로 셀렉션 알고리즘을 적용한 방식입니다. 선택 정렬 예제, 시간 복잡도, 장단점, 셀렉션 알고리즘, 선택 정렬 알고리즘 파이썬 구현에 대해 알아보겠습니다. 선택 정렬이란? (Selection Sort) 가장 작은 값의 원소부터 차례로 선택하여 위치를 교환하여 정렬하는 방법입니다. 셀렉션 알고리즘을 전체 자료에 적용한 것입니다. 셀렉션 알고리즘이란? (Selection Algorithm) 자료들 중 k번째로 크거나 작은 원소를 찾는 방법으로 최솟값, 최댓값, 중간값 등을 찾을 때 사용하기도 합니다. 정렬 알고리즘을 이용하여 자료를 정렬하고, 원하는 순서에 있는 원소를 가져오는 과정을 거칩니.. 2021. 8. 1. 카운팅 정렬 알고리즘 (Counting Sort / 계수 정렬) 포스팅에서 다룰 계수 정렬이라고도 하는 카운팅 정렬(Counting Sort)은 각 항목의 개수를 세어 저장해 두고, 그에 따라서 적절한 위치에 정렬하는 효율적인 알고리즘입니다. 오름, 내림차순 정렬 과정, 시간 복잡도, 장단점, 카운팅 정렬 파이썬 알고리즘 구현에 대해 알아보겠습니다. 카운팅 정렬이란? (Counting Sort) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세어서 적절한 위치에 선형 시간에 정렬하는 방법입니다. 각 항목의 개수를 기록하기 위해 정수로 인덱스 되는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있는 정렬 알고리즘입니다. 카운트 리스트를 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 합니다. 카운팅 .. 2021. 7. 31. 이전 1 ··· 29 30 31 32 33 34 35 ··· 37 다음 728x90 반응형
