본문 바로가기

전체 글61

트리(Tree)의 순회 (전위/중위/후위 순회) 트리의 순회 트리의 순회는 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회가 있다. ※ 여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉, 왼쪽 서브 트리, 노드 방문, 오른쪽 서브 트리를 의미한다. 중위 순회(inorder traversal) 중위 순회는 LVR 탐색이 이루어진다. 즉, 왼쪽 서브 트리-루트 노드-오른쪽 서브 트리 탐색이 재귀적으로 이루어진다. 가장 먼저 루트 노드를 기준으로 왼쪽 서브 트리로의 탐색이 시작된다. 즉, 왼쪽 서브 트리에서 또다시 중위 순회가 재귀적으로 이루어진다. B노드가 루트 노드인 것처럼 되고, 왼쪽 서브 트리인 A노드로의 중위 탐색이 진행된다. 이후 A노드는 왼쪽 서브 트리(Left)가.. 2023. 8. 10.
여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리) 트리의 개념 - 노드로 이루어진 자료구조로 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조이다. - 계층적 관계를 표현하는 자료구조이다. 트리의 특성 - 하나의 루트 노드를 갖는다. - 루트 노드는 0개 이상의 자식 노드를 갖는다. - 자식 노드 또한 0개 이상의 자식 노드를 갖는다. - 노드들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. - 사이클(Cycle)이 존재할 수 없다. 트리는 사이클이 없는 하나의 연결 그래프라고 할 수 있다. ★사이클이란? 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있는 구조를 말함한다. - 트리의 노드는 self-loop가 존재해서는 안된다. - N개의 노드를 갖는 트리는 항상 N-1개의 간선을 갖는다. - 모든 자식 노드는 한 개의.. 2023. 8. 9.
힙(Heap)이란? 특징 - 완전이진트리의 일종이다. - 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. - 중복된 값을 허용한다. - Max Heap은 가장 큰 값을 빠르게 찾기 위한 것이고, Min Heap은 가장 작은 값을 빠르게 찾기 위한 것이다. ※ 완전 이진 트리란? 여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐 트리의 개념 - 노드로 이루어진 자료구조로 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조임. - 계층적 관계를 표현하는 자료구조임. 트리의 특성 - 하나의 루트 노드를 갖음. - 루트 노드 hyolls100.tistory.com Map Heap - Max Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거.. 2023. 8. 9.
큐(Queue) 두 개로 스택(Stack) 구현하기 Push - queue1의 enqueue()를 통하여 데이터를 저장 Pop a. queue1의 데이터 갯수가 1개 이하로 남을 때까지 dequeue를 한 후, 해당 데이터를 queue2에 enqueue()하여 옮김. 이 결과로 가장 나중에 들어온 데이터를 제외한 모든 데이터가 queue2로 옮겨짐. b. queue1에 남아있는 하나의 데이터를 dequeue()하여 가장 최근에 저장된 데이터를 반환(LIFO) c. ★ 다음에 진행될 pop()을 마찬가지로 진행하기 위해 queue1과 queue2를 swap 코드 작성 import queue class Stack(object): def __init__(self): self.q1 = queue.Queue() self.q2 = queue.Queue() def p.. 2023. 8. 8.
스택(Stack) 두 개로 큐(Queue) 구현하기 구현방법 큐를 입력할 때에는 하나의 스택의 push()를 통하여 데이터를 넣고, 큐를 추출할 때에는 다른 스택의 pop()를 통하여 선입선출을 만족시키는 방법 Enqueue - 첫번째 스택 stack1에 push를 하여 데이터 저장 Dequeue - 두번째 스택 stack2 이용 a. stack2가 비어있다면 stack1이 비어질 때까지 pop()하여 모든 데이터를 옮겨넣음. 이 결과로 stack1에서 가장 먼저 있었던 데이터는 stack2의 top에 위치하게 됨 b. stack2.pop()을 하면 가장 먼저 있었던 데이터가 가장 먼저 추출됨(FIFO) 코드 작성 class Queue(object): def __init__(self): self.instack=[] self.outstack=[] def e.. 2023. 8. 8.
원형큐(Circular Queue)란? 탄생계기 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없다는 선형 큐의 문제점을 보완하기 위한 자료구조이다. 기본 동작 - 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다. Enqueue - rear+1이 배열의 끝이고 포화상태가 아니라면 데이터 삽입을 진행한다. - (rear+1)%arraysize == front 라면 배열이 포화상태이다. (포화상태 여부를 판단하기 위해 배열의 1칸은 비워둠) Dequeue - front+1의 위치의 데이터를 배열에서 가지고온다. - 배열이 공백상태가 아니라면 데이터 삭제를 진행한다. - rear==.. 2023. 8. 7.

티스토리툴바