반응형 언어별 개념 정리19 [파이썬] 자료찾기 알고리즘 - 검색 방법(순차 검색, 이진 검색) 검색 방법(Search) 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 순차 검색 (sequential search) 이진 검색 (binary search) 정렬되어 있지 않은 경우의 검색 과정 첫 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾음 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환 자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패 ex) [4, 9, 2, 7, 21] 에서 7을 검색하는경우 앞에서부터 체크 4≠7 → 9≠7 → 2≠7 ≠ 7 = 7 def search(a, key): x = 0 n = len(a) while x < n and a[x] != key : x += 1 if x 2023. 2. 12. [파이썬] 부분집합을 구하는 방법 부분집합 구하는 방법 부분집합의 수 각 원소가 n개 일 때, 공집합을 포함한 부분집합의 수는 2^n개 ex) [1,2,3,4,5] —> 2^5 = 32개 각 원소가 부분 집합에 포함되었는지 확인하는 방법 arr = [1,2,3,4,5] for i in range(2) : arr[0] = i for j in range(2) : arr[1] = j for k in range(2) : arr[2] = k for l in range(2) : arr[3] = l for n in range(2) : arr[4] = n print(arr) 부분집합을 for문을 이용하는 방법(비트 연산자 활용) 비트연산자 & : 비트 단위로 and 연산 | : 비트 단위로 or 연산 >피트연산자의 비트 열을 오른쪽으로 이동 arr =.. 2023. 2. 12. [파이썬] 정렬 알고리즘 - 버블 정렬 & 카운팅 정렬 버블 정렬 특징 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지로 이동하는 정렬 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬됨 (시간 복잡도 O(n^2)) 실제로 알고리즘 풀이에는 잘 쓸일 없음(시간 복잡도 때문) 정렬 과정 7, 6, 4 를 정렬한다고 해보자. Step 맨 앞의 7과 6의 자리를 서로 바꿔준다. 다시 반복해서 7과 4의 자리를 바꿔준다. (숫자가 더 많을 경우) 계속해서 반복해서 바꿔준다. 1번의 싸이클이 돌고 난 후 다시 처음부터 같은 작업을 반복한다 버블 정렬 코드 def Bubblesort(List): #정렬할 list, 원소 수 N for i in range(len(List)-1, 0.. 2023. 2. 12. [파이썬] 스택(Stack) 알고리즘 정리 - 계산기 구현하기 stack으로 계산기 구현하기 why 계산기 구현? 중위 표기법 수식을 스택을 이용하여 후위 표기법으로 변경할 수 있음 계산기 입장에서 계산이 쉬워져 속도 ↑ 중위 표기법 연산자를 피연산자의 가운데에 표기하는 일반적인 방법 ex) A+B , 2+3*4, 인간에게 친숙한 표현법 후위 표기법 컴퓨터의 입장에서 중위 표기법보다 후위 표기법이 더 쉬움 연산자가 나오면 이전 숫자 2개와 연산을 하는 방식 ex) 2 3 4*+ → 2 12 + → 14의 과정으로 계산 A*B-C/D을 후위 표기법으로 변환 방법 ((A*B)-(C/D)) // 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현 ((AB)*(CD)/)- // 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동 AB*CD/- // 괄호 .. 2023. 2. 8. [파이썬] 문자열(String) 알고리즘 정리 - 보이어 무어(Boyer-moore) 알고리즘 보이어 무어(Boyer-moore) 알고리즘 참고 자료 링크 https://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf 정의 Boyer-Moore 알고리즘은 패턴의 마지막 문자부터 역순으로 검사를 진행하면서 비교하는 알고리즘 기존의 방법이 왼쪽에서 오른쪽으로 했다면, 보이어-무어 알고리즘은 오른쪽에서 왼쪽으로 비교 (단, 이동(skip) 할 때는 왼쪽에서 오른쪽) 대표적으로 Bad Character Rule과 Good shuffix Rule BAD Character Rule 방법 Step1 문자열과 패턴을 오른쪽에서 왼쪽으로 문자가 일치하는지 확인 문자열과 패턴의 문자가 b 부분에서 다른 것을 확인 (C / T) 이때의 Bad char.. 2023. 2. 7. [파이썬] 문자열(String) 알고리즘 정리 - 브루트 포스(brute force) 정의 무식하게 진행 한다는 의미로 brute force 알고리즘이라 불리며 가능한 모든 경우의 수를 모두 탐색하기에 완전 탐색 알고리즘이라고도 불린다. 일반적으로 문제 해결을 위해서 모든 자료를 탐색해야 하기에 특정 구조를 전체적으로 탐색할 수 있는 방법 요구 선형 구조로 탐색하는 순차 탐색, 비선형 구조로 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 가장 기본적인 방법 → 브루트 포스와 가장 관련이 깊은 방법은 BFS 비밀번호 자물쇠를 생각하면 이해하기 쉽다 (단순히 무식하게 4자리 자물쇠를 확인하더라도 총 10^4번의 확인이 필요하다) 장점 알고리즘 설계와 구현이 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현이 가능하다 단점 알고리즘의 실행 시간이 매우 오래 걸린다 메모리 효율면에서.. 2023. 2. 6. 이전 1 2 3 4 다음 반응형
