Data Structure10

• 

  [파이썬(Python)] 그래프(Graph) 2개 이상의 데이터의 관계를 표현하는 데 효과적인 자료구조입니다. 노드(node, 정점)와 에지(edge, 간선)으로 구성되며, 방향이 있는 그래프와 방향이 없는 그래프로 구분됩니다. 그래프로 다음과 같은 탐색 알고리즘을 사용할 수 있습니다. 이번 포스트에서는 그래프와 관련된 알고리즘은 가볍게 다루겠습니다. 깊이 우선 탐색(DFS; Depth First Search) 시작 정점에서 한 방향으로만 탐색하다가 더 이상 갈 곳이 없으면 왔던 경로를 되돌아가며, 다른 노드와 연결된 노드 중 가장 마지막에 만났던 노드로 돌아가서 다른 방향으로 탐색을 시작합니다. 너비 우선 탐색(BFS; Breadth First Search) 시작 정점에서 갈 수 있는 모든 정점을 탐색한 후, 인접 정점에서 같은 방식으로 계속 탐.. Data Structure 2023. 2. 20.

• 

  [파이썬(Python)] 힙(Heap) 힙(heap)은 동적 배열인 완전 이진 트리이다. 그래프 알고리즘을 구현하는 데 필요한 우선순위 큐(priority queue)를 구현할 수 있다. 최대 힙(max heap)과 최소 힙(min heap)이 있다. 최소 힙 밑에서 최대 힙을 최대 트리라고 설명하는데, 이상하게도 최소 트리라는 용어는 쓰지 않는 것 같다. 자식 노드가 부모 노드의 키보다 작지 않고, 완전 이진 트리인 힙을 최소 트리라고 한다. 이번 포스트에서는 최대 힙을 기준으로 설명하는데, 최소 힙은 순서가 다를 뿐 나머지는 똑같이 이해하면 된다. 최대 힙 최대 트리이며 완전 이진 트리이다. 최대 트리: 부모 노드는 자식 노드의 키보다 작지 않은 트리 완전 이진 트리: 이진 트리의 마지막 레벨을 제외한 나머지 레벨이 노드로 가득 차 있고,.. Data Structure 2023. 2. 17.

• 

  [파이썬(Python)] 이진 트리(Binary Tree) 어떤 트리의 노드가 왼쪽 자식(left child)과 오른쪽 자식(right child), 최대 두 자식만을 가지면 이진 트리이다. 자식이 없거나 하나만 갖는 노드도 허용된다. 완전 이진 트리(Complete Binary Tree) 이진 트리의 마지막 레벨을 제외한 나머지 레벨이 노드로 가득 차 있고, 마지막 레벨의 노드가 왼쪽부터 차례대로 채워져 있으면 완전 이진 트리이다. 한 레벨 당 최대 개수는 2의 거듭제곱꼴이므로, 높이가 k인 완전 이진 트리가 가질 수 있는 노드의 수는 최대 2^(k+1) - 1 개이고, n개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 log n이다. 이진 검색 트리(Binary Search Tree) 왼쪽 서브트리 노드의 키 값은 자신의 노드 키 값보다 항상 작아야하고.. Data Structure 2023. 2. 16.

• 

  [파이썬(Python)] 트리(Tree) 트리는 노드(node)와 노드를 잇는 가지(edge)로 구성된다. 루트(root): 트리에 단 하나만 존재하는 최상단에 위치한 노드 리프(leaf): 하단으로 뻗은 가지가 없는 노드 비단말 노드(non-terminal node): 리프를 제외한 모든 노드. 내부 노드 부모: 연결된 두 노드 중 상단에 위치한 노드 자식: 연결된 두 노드 중 하단에 위치한 노드 형제: 부모가 같은 노드 조상: 특정 노드에서 위쪽으로 가지를 따라가며 만나는 모든 노드 자손: 특정 노드에서 아래쪽으로 가지를 따라가며 만나는 모든 노드 레벨: 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 정도. 루트의 레벨은 0 차수: 각 노드가 갖는 자식의 수 - (이진트리: 차수 2, 삼진트리: 차수 3) 서브트리: 특정 노드를 루트로 삼아.. Data Structure 2023. 2. 16.

• [파이썬(Python)] 덱(Deque) 덱은 double-ended-queue의 약어이다. 스택은 top에서 입, 출력을 하고, 큐는 rear에서 입력, front에서 출력하는 것과 달리, 덱은 front와 rear 양쪽에서 데이터 입, 출력이 가능하다. 파이썬에서는 collections 모듈에서 덱을 제공하고 있어서 직접 덱을 구현할 필요 없이 바로 사용 가능하다. 코드 출처: 파이썬으로 배우는 자료 구조 핵심 원리 - 양태환 from collections import deque print('*' * 20 + 'Stack' + '*' * 20) stack = deque() for i in range(1, 6): stack.append(i) print(stack) for i in range(5): print(stack.pop()) print(.. Data Structure 2023. 2. 16.

• [파이썬(Python)] 큐(Queue) 줄을 설 때 온 사람 순으로 차례 대로 들어가는 것 처럼 데이터가 입력된 순서대로 출력되는 선입선출(First In First Out)형이다. 배열이나 연결 리스트를 이용해서 구현한다. 다음과 같은 용어가 큐에 관련하여 사용된다. 인큐(enqueue): 큐에 데이터를 추가하는 작업 디큐(dequeue): 큐에서 데이터를 꺼내는 작업 프런트(front): 데이터를 꺼내는 쪽 리어(rear): 데이터를 넣는 쪽 큐 구현 방법 배열로 구현하기 인큐할 때는 맨 끝의 데이터 다음 원소에 새로운 데이터를 저장하면 되므로, 이때의 복잡도는 O(1)이다. 그러나, 디큐를 위해서는 맨 첫 번째 원소를 꺼내고 나머지 원소를 하나씩 앞쪽으로 당겨야 한다. 복잡도는 O(n)이다. 좀 더 효율적인 방법이 필요하다. 링 버퍼로 .. Data Structure 2023. 2. 15.

• [파이썬(Python)] 스택(Stack) 물건을 쌓는 것 처럼, 데이터가 입력된 순서대로 데이터를 쌓아서 나중에 들어온 데이터부터 출력하는 자료구조이다. 이처럼 나중에 들어온 데이터 부터 출력하는 것을 후입선출(Last In First Out)이라고 한다. 배열 또는 연결 리스트로 구현할 수 있다. Push: 스택에 데이터를 넣는 것 Pop: 스택에서 데이터를 꺼내는 것. 가장 마지막에 push한 데이터를 반환한다. 코드 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 from typing import Any class FixedStack: # 고정 길이 스택 클래스 class Empty(Exception): # 비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리 pass class Full(Exception): #.. Data Structure 2023. 2. 15.

• [파이썬(Python)] 연결 리스트(Linked List) 기본 자료형, 배열, 구조체, 클래스 등 데이터 외에 전, 후 데이터를 가리키는 정보(포인터 pointer)를 갖는 자료구조이다. 장점 데이터를 중간에 삽입하거나 삭제할 경우, 해당 데이터의 앞, 뒤 데이터의 포인터를 조작하는 방식으로 쉽게 처리가 가능하다. 단점 O(1)로 조회가 가능한 배열과 달리 연결 리스트는 조회를 위해서는 처음 또는 끝 데이터에서 포인터를 따라 순차적으로 이동하는 수밖에 없다. 연결 리스트의 종류 연결 리스트: 데이터가 (데이터 + 다음 데이터를 가리키는 포인터)로 구성 - 단방향 탐색 가능 더블 연결 리스트: 데이터가 (이전 데이터를 가리키는 포인터 + 데이터 + 다음 데이터를 가리키는 포인터)로 구성 - 양방향 탐색 가능 환형 연결 리스트: 더블 연결 리스트에서 양끝 데이터 .. Data Structure 2023. 2. 15.

• 배열(array) 배열(array): 특정 크기만큼의 연속된 메모리 공간을 할당받는 자료형 배열의 특성 c언어 기준 자료형을 지정하고 선언 한 번 공간 크기가 정해지면 변경 불가 정수형 int로 배열을 선언할 때, 데이터의 사이즈는 컴파일러와 프로세서의 구조에 따라 다름 int형은 과거에는 2바이트였다가 현재 32비트 이상의 시스템에서는 4바이트로 변경됨 배열의 각 엘리먼트의 주소는 사용된 자료형의 크기만큼 증가 배열은 특정 엘리먼트의 위치를 O(1)에 조회 가능 배열의 크기가 얼마나 늘어나든 조회 속도에는 변함 X 배열의 시작 주소에 (인덱스 x 자료형 크기)를 더해주면 해당하는 배열의 주소를 쉽게 계산할 수 있기 때문 현실적으로 데이터의 크기를 정확히 예상하기 어렵다. 미리 할당해놓은 공간이 너무 작거나 클 수 있다... Data Structure 2023. 2. 15.

• 

  자료구조 자료구조는 자료에 효율적으로 접근하고, 수정할 수 있도록 자료를 조직하는 것을 의미한다. 자료구조는 데이터 값, 데이터 간 관계, 함수를 정의한다. 이를 통해 효율적인 알고리즘을 구성할 수 있다. 자료구조의 종류는 다양하지만 대부분의 자료구조는 결국 내부적으로 리스트와 연결리스트, 두 가지의 물리적인 자료구조로 구현되었다. 단순구조(Simple Structure) 컴퓨터가 기본적으로 제공하는 자료형으로 구성된 자료구조를 의미한다. 수, 문자/문자열, True/False와 같이 컴퓨터가 0과 1로 직접적으로 대응하여 해석할 수 있다. 이렇게 기본 자료형만으로 구성한 사용자 정의 자료형도 단순구조에 속한다. 배열, 구조체, 클래스가 이에 해당한다. 배열: 동일한 자료형을 연속적으로 나열한 자료형 구조체: 동.. Data Structure 2023. 2. 15.