HappyTomatoLife

트리 구조 : 데이터 사이의 계층 관계를 표현한다 트리의 구조와 관련 용어 tree - node와 edge로 구성됨. root - 가장 상위에 있는 노드 leaf - terminal node = external node non-terminal node = internal node 비단말 노드 자식 - 아래쪽 노드 부모 parent 위쪽에 있는 노드 형제 - sibling 부모가 같은 노드 조상 - ancestor 가지를 따라가면 만나는 노드 자손 - descendant 아래로 내려가면서 만나는 모든 노드 레벨 - 루트에서 얼마나 떨어져 있는지 나타냄 차수 - degree 노드의 자식 수 높이 - height 리프 레벨의 최댓값 서브트리 - subtree - 자손으로 구성된 트리 빈 트리 - null tr..

포인터로 연결 리스트 만들기 # 포인터로 연결 리스트 구현하기 from __future__ import annotations from typing import Any, Type class Node: def __init__(self, data:Any = None, next : Node = None): self.data = data self.next = next class LinkedList: def __init__(self) -> None: self.no = 0 self.head = None self.current = None def __len__(self) -> int: return self.no def search(self, data:Any) -> int: cnt = 0 ptr = self.head w..

포인터로 연결 리스트 만들기 포인터 - 노드node에서 뒤쪽 노드successor node를 가리킨다 노드 클래스 Node 필드 __init__() 함수 연결 리스트 클래스 LinkedList 초기화하는 __init__() 함수 노드 개수를 반환하는 __len__() 함수 검색을 수행하는 search() 함수 데이터가 포함되어 있는지 판단하는 __contains__() 함수 머리에 노드를 삽입하는 add_first() 함수 꼬리에 노드를 삽입하는 add_last() 함수 머리 노드를 삭제하는 remove_fisrt() 함수 꼬리 노드를 삭제하는 remove_last() 함수 임의의 노드를 삭제하는 remove() 함수 주목 노드를 삭제하는 remove_current_node() 함수 모든 노드를 삭제하는..

연결 리스트 알아보기 리스트 list - 데이터에 순서를 매겨 늘어놓은 자료구조 * cf) [1, 2, 3] 리스트 자료형과는 다른 것이다. 연결 리스트 linked list node - 각 element pointer - 노드는 data와 pointer로 구성됨. pointer는 다음 노드를 참조(가리킴)함 head node tail node predecessor node - 앞쪽 노드 successor node - 뒤쪽 노드 배열로 연결 리스트 만들기 비효율적 : 앞에서 제시된 데이터를 옮겨야 한다.

보이어 무어법 알아보기 -> 가장 효율적인 문자열 알고리즘이다. 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행함 #보이어 무어법으로 문자열 검색하기 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')) 멤버십 연산자와 표준 라이브러리를 사..

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]..