CODE/Algorithm and Data Structure

[Doit! Python] 검색 알고리즘

교재: Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬편 검색 알고리즘 검색 알고리즘이란? 검색과 키 대부분의 키는 데이터의 일부 검색의 종류 배열 검색 선형 검색 무작위 데이터 집합에서 검색 수행 이진 검색 일정 규칙을 늘어놓은 데이터 집합에서 빠름 해시법 추가/삭제가 자주 일어나는 데이터 집합에서 빠름 체인법 - 같은 해시값 데이터를 연결 리스트로 연결하는 방법 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시하는 방법 연결 리스트 검색(8장) 이진 검색 트리 검색(7장) 따라서, 용도/목적/실행 속도/자료구조 등 여러 사항을 고려해서 알고리즘을 선택해야한다. 선형 검색 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘 배열에 원하는 값이 존재할 때..

[Do it! Python] 문자열 검색

해당 글은 Do it! Python으로 배우는 자료구조와 알고리즘을 기반으로 작성했습니다. 문자열 검색 어떤 문자열 안에 다른 문자열(패턴)이 포함되어 있는지 검사 포함되어 있다면 어디에 위치하는지 찾아내는 것 브루트 포스법(단순법, 완전 탐색) 완전 탐색 선형 검색을 단순히 확장한 알고리즘 이미 검사한 위치를 기억하지 못 한다. ⇒ "일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검사 수행" 코드 def bf_match(txt, pat): pt = 0 # txt를 스캔하는 커서 pp = 0 # 패턴을 저장하는 pat을 스캔하는 커서 while pt != len(txt) and pp != len(pat): if txt[pt] == pat[pp]: pt += 1 pp += 1 else: pt = p..