CS/Data Structure

연결 리스트(LinkedList)

연결 리스트 리스트는 데이터에 순서를 매겨놓은 자료구조이다. (단일)연결리스트는 리스트의 한 종류이다.여기서는 포인터를 이용해서 연결리스트를 만들어보겠다. 연결리스트는 위의 그림처럼 각 노드들이 연결되어있는 형태를 나타낸다.각 노드 안에는 데이터와 다음노드를 참조하는 포인터로 이루어져 있다.A, B, C 의 노드가 있다고 하면 첫번째 노드 안에는 A라는 데이터와 B를 참조하는 포인터가 있다.두번째 노드 안에는 B라는 데이터와 C를 참조하는 포인터가 있다.세번재 노드 안에는 C라는 데이터와 다음이 없으므로 참조하는 포인터는 없다. 여기서 첫번째 노드를 머리 노드, 마지막 노드를 꼬리 노드라고 한다. 연결리스트의 장점은 원하는 만큼의 노드를 동적으로 추가/삭제 할 수 있다.단점은 배열처럼 메모리공간에 정렬되..

큐(queue)

큐 스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택과 반대로 가정 먼저 넣은 데이를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 구조를 가진다.예: 놀이공원에서 보통 줄 서는 구조 큐에 데이터를 넣을 떄는 인큐(enqueue), 큐에서 데이터를 꺼낼 때는 디큐(dequeue) 함수를 정의 데이터를 직접 꺼내는 것이 아니라 두개의 포인터(front, rear) 를 사용해서 위치를 나타낸다. 코드 # 고정 길이 큐 구현하기 with 링 버퍼. # 기존의 리스트로 dequeue 구현 시 시간 복잡도가 O(n) 으로 상당히 비효율적이다. # 이를 해결하기 위해 링 버퍼를 사용. from typing import Any class FixedQueue: class Empt..

스택(Stack)

스택 데이터를 임시 저장할 때 사용하는 자료구조, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다. 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조로 되어있다.데이터를 넣을 때는 push, 데이터를 꺼낼 때는 pop을 사용한다. 파이썬에서는 보통 스택을 구현하지 않고 리스트로 만들고 append 해서 데이터를 넣거나 pop으로 데이터를 꺼낸다.아래의 코드는 스택을 클래스로 구현해본 것이다. 코드 class Stack: class Empty(Exception): """스택이 비어있을 때 pop 또는 peek 를 수행할 때 예외 처리""" print("야") pass class Full(Exception): """스택이 가득일 때 push 를 수행할 때 예외 처리""" pass def __in..

[python] 이진 탐색 트리 (binary Search tree) - 4. 삭제

📗 이진 트리 (binary Search tree) - 삭제 노드 삭제 노드를 하나 삭제해보자. 노드를 삭제하는 경우는 3가지가 있다. 자식 노드가 없은 경우, 자식 노드가 하나인 경우, 자식노드가 둘인경우로 나눌 수 있다. 🔵 자식 노드가 없는 경우 자식 노드가 없는 경우는 그냥 삭제하면 된다. 🔵 자식 노드가 하나인 경우 자식 노드가 하나인 경우는 삭제할 노드를 삭제하고, 그 자식 노드를 할아버지 노드에 붙이면 된다. 🔵 자식 노드가 둘인 경우 자식 노드가 둘인 경우는 삭제할 노드를 삭제하고, 그 노드의 오른쪽 자식의 가장 왼쪽 자손을 가져와서 삭제한 노드의 부모 노드에 붙여준다. 🔵 전체 코드 # 노드 만들기 # A(val) # / \ # B(left) C(right) class Node: def ..

[python] 이진 탐색 트리 (binary Search tree) - 3. 순회

📗 이진 트리 (binary Search tree) - 순회 트리 순회 트리 순회는 트리에 저장된 값을 모두 확인할 때 사용한다. 순회 방법에 따라 값을 확인하는 순서가 다르다.순회의 종류로는 전위 순회 (preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)이 있다. 🔵 전위 순회 (preorder traversal) 💨 완성되어 있는 트리를 다른 서버에 리스트 형태로 보내서 그 서버에서 다시 트리를 구성할 때 사용 노드 > 왼쪽 서브트리 > 오른쪽 서브트리 순으로 순회한다. 구현 방법은 다음과 같다. 노드 방문 왼쪽 서브트리 방문 오른쪽 서브트리 방문 전위 순회 결과: F, B, A, D, C, E, G, I, H def p..

[python] 이진 탐색 트리 (binary Search tree) - 2. 탐색

📗 이진 트리 (binary Search tree) 🔵 이진 탐색 트리 탐색 [python] 이진 탐색 트리 (binary Search tree) - 1. 클래스 정의, 초기화, 노드 추가 📗 이진 트리 (binary Search tree) 🔵 이진 탐색 트리 클래스 정의 및 초기화 먼저 Node 클래스를 정의해 보자. Node 클래스는 노드값인 self.val 와 왼쪽 노드 self.left 오른쪽 노드 self.right 의.. deok2kim.tistory.com 🔺 클래스 정의 및 초기화는 앞에서 다뤘다. 이진 탐색 트리에 찾고자하는 값이 있는지를 확인하는 것이다. 값이 있으면 True, 없으면 False를 반환한다. 맨 위의 이미지를 보면 원하는 값인 27을 찾는 과정이다. 먼저 최상위 노드인 ..