HappyTomatoLife

보이어 무어법 알아보기 -> 가장 효율적인 문자열 알고리즘이다. 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행함 #보이어 무어법으로 문자열 검색하기 def bm_match(txt:str, pat:str) -> int: skip = [None] * 256 for pt in range(256): skip[pt] = len(pat) for pt in range(len(pat)): skip[ord(pat[pt])] = len(pat) - pt - 1 while pt < len(txt): pp = len(pat) - 1 while txt[pt] == pat[pp]: if pp == 0: return pt pt -= 1 pp -= 1 pt += skip[ord(txt[pt])] if skip[ord(txt[..

KMP법 알아보기 브루트 포스법보다 효율적이다. 검사했던 결과를 버리지 않고 활용하기 때문이다. '몇 번째 문자부터 다시 검색할 것인지'를 표로 만들어 문제를 해결한다. KMP법에서 사용하는 표 만들기 skip table #KMP법으로 문자열 검색하기 def kmp_match(txt:str, pat:str) -> int: pt = 1 pp = 0 skip = [0] * (len(pat)+1) skip[pt] = 0 while pt != len(pat): if pat[pt] == pat[pp]: pt += 1 pp += 1 skip[pt] = pp elif pp == 0: pt += 1 skip[pt] = pp else: pp = skip[pp] pt = pp = 0 while pt != len(txt) ..

문자열 검색이란? string searching - text에서 pattern의 위치를 찾아내는 것 브루트 포스법 알아보기 brute force method - 선형 검색을 확장한 '단순법' 알고리즘이다. #브루트 포스법으로 문자열 검색하기 def bf_match(txt:str, pat:str) -> int: pt = 0 pp = 0 while pt != len(txt) and pp != len(pat): if txt[pt] == pat[pp]: pt += 1 pp += 1 else: pt = pt - pp + 1 pp = 0 return pt - pp if pp == len(pat) else -1 print(bf_match('youngjupark', 'park')) 멤버십 연산자와 표준 라이브러리를 사..

핵심 19 [설정] -> [계정] 사용자 정보 - 이름, 계정 유형, 사진 표시 로그인 옵션 - 자동 잠금, 계정 정보 표시 여부 지정 가족 및 다른 사용자 - 가족 구성원 추가(성인/Not), 다른 사용자 추가, 관리자 계정, 표준 사용자 계정(앱 설치/삭제 불가) 핵심 20 [설정] -> [장치] -> [마우스]/[입력] 마우스 - 오른손잡이/왼손, 스크롤 설정, 추가마우스 - 마우스 속성 입력 - 추천 단어, 자동 고침, 텍스트 제안 표시 핵심 21 [설정] -> [업데이트 및 보안] 윈도우 업데이트 - 직접 업데이트 가능, 7일 동안 중지 가능, 재부팅 않하도록 지정 가능 윈도우 보안 - 백신, 방화벽 등, 바이러스 위협 ㅈ방지, 계정 보호, 방화벽, 네트워크 보호, 앱 및 브라우저 컨트롤, 장치..

counting sort - 원소의 대소관계를 판단하지 않고 정렬하는 알고리즘 [도수 정렬 알아보기] step 1. 도수 분포표 만들기 도수 분포표 - 등급으로 나누고, 각 등급에 속하는 도수(자료의 개수)를 나타낸 표 step 2. 누적 도수 분포표 만들기 0부터 n점까지 몇 명이 있는지 누적된 값을 나타내도록 도수 분포표를 만든다 step 3. 작업용 배열 만들기 step 4. 배열 복사하기 #도수 정렬 알고리즘 구현하기 from typing import MutableSequence def fsort(a:MutableSequence, max:int) -> None: n = len(a) f = [0] * (max+1) b = [0] * n for i in range(n): f[a[i]] += 1 for..

[힙 정렬heap sort 알아보기] -> 선택 정렬 응용 heap - 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 부분 이진 트리 * 부분 : 형재의 대소 관계가 정해져 있지 않다 트리 - 노드node가 연결된 계층 구조 - root (젤 윗값) / parent node > child node = sibling node / leaf (가장 말단 노드) - 완전 이진 상태 : 완전 - 부모는 왼쪽 자식부터 추가하여 모양을 유지한다. - 이진 : 자식은 최대 2개 [힙 정렬의 특징] 힙에서 최댓값은 루트에 위치한다 (부모 >= 자식이므로) 알고리즘 step 1. 최댓값인 루트를 꺼낸다 step 2. 루트가 사라진 나머지 부분을 다시 힙으로 만든다. -> 반복 [루트를 삭제한 힙의 재구성] [힙 ..

병합 정렬 merge sort - 앞부분, 뒷부분 두 그룹으로 나누어 각각 정렬한 후 병합하는 알고리즘 정렬을 마친 배열의 병합 from typing import Sequence def merge_sorted_list(a:Sequence, b:Sequence) -> None: c = [None] * (len(a) + len(b)) pa, pb, pc= 0, 0, 0 na, nb = len(a), len(b) while pa < na and pb < nb: if a[pa] < b[pb]: c[pc] = a[pa] pa += 1 else: c[pc] = b[pb] pb += 1 pc += 1 while pa < na: c[pc] = a[pa] pa += 1 pc += 1 while pb < nb: c[pc]..

비재귀적인 퀵 정렬 만들기 from for_class import Stack from typing import MutableSequence def qsort(a:MutableSequence, left:int, right:int)-> None: range = Stack(right - left + 1) range.push((left, right)) while not range.is_empty(): pl, pr = left, right = range.pop() x = a[(left + right) // 2] while pl x: pr -= 1 if pl None: self.capacity = maxlen self.__stk = deque([], maxlen) def __len__(self) -> int: re..

퀵 정렬 quick sort 퀵 정렬 알아보기 피봇 pivot - 기준을 정하고 그룹을 나눈다. 그룹에 1명씩 남으면 정렬이 완료된다. 배열을 두 그룹으로 나누기 - pl 왼쪽 커서, pr 오른쪽 커서로 설정해놓고, 피벗을 정한다. - pl을 오른쪽 방향으로 스캔하여 -> a[pl] > a[pivot]인 pl값을 찾는다. - pr을 왼쪽 방향으로 스캔하여 -> a[pr] = pr이 될 때까지 반복한다. 두 그룹으로 나누는 걸 어떻게 구현해야 하나~ 우선 while 구문에 들어가기 전에 n, pl, pr, pivot을 할당해주었다. while문 안에서 - pl >= pr이 되면 그만하고.. - a[pl] > a[pivot], a[pr] <..

06-5 셸 정렬 셸 정렬 shell sort 단순 삽입 정렬의 문제 삽입 위치가 멀리 떨어져 있으면 이동 횟수가 많아짐 셸 정렬 알아보기 shell sort 알고리즘 - 정렬할 배열의 우너소를 그룹으로 나눔. 그룹별로 정렬 수행. 정렬된 그룹을 합치는 작업을 반복함. 4정렬 -> 2정렬 -> 1정렬을 적용하면 정렬이 완료된다. 'h-정렬' from typing import MutableSequence def shell_sort(a:MutableSequence) -> None: n = len(a) h = n//2 while h > 0: for i in range(h, n): j = i - h tmp = a[i] while j >= 0 and a[j] > tmp: a[j+h ] = a[j] j -= h a..