Python/자료구조 내용 정리

자료구조 7장 - 문자열 검색

문자열 검색 이란 ? 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함돼 있다면 어디에 위치하였는지 찾아내는 것 문자열에서 부분 문자열을 검색하는 방법은 브루트 포스법, KMP법, 보이어, 무어법 등이 있다. 브루트 포스법 O(N*M) N-문자열 M-패턴 문자열 검색 방식에서 가장 기초적이고 단순한 알고리즘 선형 검색을 단순하게 확장시킨 알고리즘 txt : 문자열 pat : 찾을 문자열 (패턴) * (pt=pt-pp+1) : txt배열에서 찾다가 패턴이 다르면 다음 인덱스로 돌아간다 ex) 3번째 부터 5번째까지 패턴이 같지만 6번째에 다르면 4번째 인덱스로 돌아감 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def bf_match(txt,pat): pt..

자료구조 6장 - 정렬 알고리즘

정렬 알고리즘 이란 ? 1. 안정적인 알고리즘 - 값이 같은 원소의 순서가 정렬 후에도 유지. 2. 안정적이지 않는 알고리즘 - 정렬 후에도 원래의 순서가 유지되는 보장이 없다. 1. 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 2. 외부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘 정렬 알고리즘의 핵심 : 교환, 선택, 삽입 시간복잡도 속도 : O(1) > O(logN) > O(N) > O(NlogN) > O(N2) > O(2N) > O(N!) 1. 버블 정렬 버블 정렬은 이웃한 두 원소를 비교하여 필요에 따라 교환을 반복하는 알고리즘 비교 , 교환하는 과정을 pass 라고 한다. 1 2 3 4 5 6 def bub..

자료구조 5장 - 재귀 알고리즘

재귀 란 ? 1. 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 재정의하는 경우를 말한다. 2. 자가 증식의 종료를 명확하게 해야한다. (무한증식 오류) 1. 팩토리얼 (양의 정수를 순서대로 곱하는 순차 곱셈) 1 2 3 4 5 6 7 def factorial(n): if n>0: return n* factorial(n-1) else: return 1 print(factorial(5)) n이 0보다 크면 n-1 팩토리얼 값을 구하게 되며 0보다 작을 때까지 반복된다. n이 0보다 작으면 1이 리턴된다. cs -> math 모듈을 통해 math.factorial() 함수를 사용하여 간편히 구할 수 있다. 2. 유클레드 호제법 (x,y의 최대 공약수 , 큰 값을 작은 값으로 나누어 떨어질..

자료구조 4장- 스택과 큐

스택 이란 ? 스택은 데이터를 임시 저장할 때 사용하는 자료구조 후입선출 방식 FILO 이다 (가장 나중에 넣은 데이터를 가장 먼저 꺼냄) 스택에 데이터를 넣는 작업을 푸시, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다. 스택 배열 : stk (푸시한 데이터를 저장하는 스택 본체인 리스트형 배열), stk[0]은 스택의 바닥 스택 크기 : capacity (스택의 최대 크기) , equal len(stk) 스택 포인터 : ptr (스택에 쌓여있는 데이터의 개수) * 예외처리 : 오류를 복구하여 프로그램이 중단되는 것을 피함 - 원래 처리하는 코드와 오류가 발생할 때 대처하는 코드를 분리 * raise : 일부러 오류 발생 -스택 클래스 정의 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

자료구조 - 3장 검색 알고리즘

- 검색의 종류 1. 배열 검색 2. 연결 리스트 검색 3. 이진 검색 트리 검색 - 배열 검색 ( 해당 조건에 맞게 알맞게 선택) 1. 선형 검색 2. 이진 검색 - 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색 수행 3. 해시법 - 추가 및 삭제가 빈번히 일어나는 데이터 집합에서 빠른 검색 수행 1. 선형 검색 (가장 기본적인 알고리즘) - 원하는 값을 찾을때까지 맨 앞부터 순서대로 검색하는 알고리즘 - 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법 1) arr=[.....] i=0 while True: if i == len(arr): return -1 // 검색 실패 시 if arr[i]== key: return i // 검색 성공 시 해당 인덱스 번호 반환 i+=1 2) for i ..