bereben

트리 트리는 노드와 가지로 구성되어 있다. 각 노드는 가지를 통해 다른 노드와 연결된다.루트 트리의 가장 위에 있는 노드를 루트노드라고 한다. 루트트리는 한개만 존재한다.리프 가장 아래쪽에 있는 노드를 리프라고 한다. 리프는 단말 노드(terminal node), 외부노드(external node)라고도 한다. 리프노드는 더이상 뻗어 나갈 가지가 없는 마지막 노드를 말한다.비단말 노드 리프를 제외한 노드를 비단말 노드(non-terminal node)라고 한다. 다른 말로는 내부 노드(internal node)라고도 불린다.자식 어떤 노드와 가지로 연결되어 있는 아랫쪽 노드를 자식이라 한다. 자식은 여러개 존재할 수 있다. 리프는 자식이 없다.부모 어떤 노드와 가지로 연결되어 있는 위쪽 노드를 부모라고 ..

리스트란? 순서가 있는 데이터를 늘어놓은 자료구조를 말한다. 종류로는 선형리스트와 연결리스트가 있다. 1. 단순 배열 연결리스트 단순 배열로 연결 리스트를 만들 경우 삽입, 삭제할 때마다 뒤에 데이터를 모두 옮겨야 하므로 효율적이지 않다.2. 포인터를 이용한 연결 리스트 연결 리스트에서 각각의 원소를 노드라고 한다. 이 노드는 데이터와 다음 노드를 가르키는 포인터로 이뤄져 있다. 그래서 일반적인 경우 이러한 방법으로 연결 리스트를 구현한다.class Node: def __init__(self, val): self.val = val self.next = None def printNode(node): while node is not None: print(node.val, end = ' ') n..

문자열 검색이란? 어떤 문자열안에 다른 문자열이 있는지 검사하고 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다.1. 브루트 포스법 선형 검색을 단순하게 확장한 알고리즘이라 단순법이라고 한다.원리 만약 텍스트 apple에서 패턴 ple을 검색하는 방법이다. 첫번째 시작부분인 a에서부터 패턴의 총 개수인 3개를 검사한다. 다르다면 한칸 이동하여 반복 수행한다. 만약 패턴이 모두 맞다면 시작하는 인덱스를 출력하며 종료한다. 2. KMP법 브루트 포스법은 틀린 패턴이 있으면 한칸만 이동하고 다시 검색을 한다. 하지만 KMP법은 버리지 않고 활용하는 알고리즘이다.원리 버리지 않고 활용을 하지만 몇번째 문자열부터 다시 검사를 할지 판단하는 표를 만들어 재활용이 가능하다는 장점이 있으나 보이어 무어법보다 느..

5. 셸 정렬 단순 삽입 정렬의 장점을 살리고 단점을 보완하여 더 빠르게 정렬하는 알고리즘기존의 문제점 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다. 개선방법 정렬할 배열의 원소를 그룹으로 나눠서 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다. 원리 4- 정렬, 2- 정렬, 1-정렬 즉, 배열 전체에 적용을 시킨다. 이를 h-정렬이라 한다. 배열에서 h만큼 떨어진 원소를 그룹시켜 각 그룹별로 정렬을 수행한다. h를 4, 2, 1로 감소시키며 정렬을 수행한다. h값을 효율적으로 선택하는 법 h를 효율적으로 선택해야 각 그룹을 선택할 때 보다 충분히 섞일 수 있다. 그렇기에 h값이 서로 배수가 안되도록 선택해야 한다. h의 값을 1부터 선택해..

정렬이란? 값의 대소관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 작은 데이터를 앞쪽부터 늘어놓은 것을 오름차순 큰 데이터를 앞쪽부터 늘어놓은 것을 내림차순이라 한다. 정렬 알고리즘에서 교환, 선택, 삽입은 핵심 개념이다.1. 버블 정렬 이웃한 원소를 비교하여 작은값을 앞으로 큰값을 뒤로 교환하는 정렬을 말한다.코드 구현 arr = [6,4,3,7,1,9,8] for i in range(len(arr)): for j in range(len(arr)-i-1,i,-1): if arr[j-1] > arr[j]: arr[j], arr[j-1] = arr[j-1], arr[j] 2. 세이커 정렬(버블 정렬 개선) 정렬이 거의 완료된 배열을 버블정렬하면 빠르게 완료하기가 어렵다. 가장 큰..

재귀란? 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의하는 경우를 말한다. 특징 : 스택처럼 마지막에 들어간 것이 첫번째로 종료가 된다. 장점 : 재귀를 사용하면 코드가 간결해진다.!!! 단점 : 너무 깊이 들어가면 오류가 날 수도 있다. 처리할게 많아지면 구조가 많이 복잡해진다. 1) 팩토리얼 def fact(n): if n > 0: return n * fact(n - 1) else return 1 fact(5) 순서 fact(5) = 5 * fact(4) ==> fact(4)로 진입 fact(4) = 4 * fact(3) ==> fact(3)로 진입 fact(3) = 3 * fact(2) ==> fact(2)로 진입 fact(2) = 2 * 1 ==> 종료 2 리턴 fact(..

스택(stack) 데이터를 임시 저장할 때 사용하는 자료구조이며 데이터 입력과 출력 순서는 후입선출(LIFO)이다. 스택에서 데이터 입력을 push라 하며 데이터 꺼내는 작업을 pop이라 한다. 고정길이 스택 구현 함수 : len, push, pop, peek, clear, isEmpty, isFull, find, count, contains, dump from typing import Any class Stack: def __init__(self, capacity: int): self.stk = [None] * capacity self.ptr = 0 self.capacity = capacity def __len__(self) -> int: return self.ptr class Empty(Excepti..