IT/Data Structure

    [자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree
    IT/Data Structure

    [자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree

    1. 그래프 1.1 그래프란? 그래프(Graph)란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다. G = (V, E) 수학적으로 그래프를 표시하는 방법이다. V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 그래프는 수학자 오일러(Euler)에 의해 창안되어 수학의 한 분야로서 수백 년 간 연구되어 왔지만, 컴퓨터 과학 분야에서 그래프 알고리즘을 다루기 시작한 것은 오래되지 않았다. 지하철 노선도, 도심의 도로 등 실생활의 다양한 예를 그래프로 표현하고 활용할 수 있으며, 특히 알고리즘에서 굉장히 많이 사용되므로 그래프에 대해 반드시 공부해야 한다. ※ 오일러 경로 (Eul..

    [자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)
    IT/Data Structure

    [자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)

    1. 우선순위 큐 1.1 우선순위 큐란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다. 1.2 힙이란? 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다. 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태) 이진탐색트리(BST)와 달리 중복된 값이 허용된다. 힙의 종류 최대 힙 (Max Heap) ..

    [자료구조] 이진탐색트리 (Binary Search Tree)
    IT/Data Structure

    [자료구조] 이진탐색트리 (Binary Search Tree)

    1. 이진탐색트리 1.1 이진탐색트리란? 이진탐색트리(BST: Binary Search Tree)는 이진트리 기반의 탐색을 위한 자료구조이다. 이진탐색의 효율적인 탐색 능력을 가지며, 삽입과 삭제가 가능한 것이 특징이다. 1.2 이진탐색트리의 4가지 조건 모든 노드는 유일한 키를 갖는다. 왼쪽 서브트리의 키들은 루트의 키보다 작다. 오른쪽 서브트리의 키들은 루트의 키보다 작다. 왼쪽과 오른쪽 서브트리도 이진탐색트리이다. 1.3 이진탐색트리 특징 이진탐색트리를 순회할 때는 중위순회(In-order Traversal) 방법을 사용한다. (왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서) 이진탐색트리를 중위 순회한 결과는 트리 내의 모든 값들을 오름차순으로 정렬한 결과를 나타낸다. 예를 들어 위 그림의 트리를..

    [자료구조] 트리? + 이진 트리 (Binary Tree)
    IT/Data Structure

    [자료구조] 트리? + 이진 트리 (Binary Tree)

    1. 트리 1.1 트리란? 트리(Tree)란 계층적인 구조를 나타내는 자료구조이다. 이전에 다룬 스택(Stack)과 큐(Queue)와 같은 선형 구조와 달리 트리는 비선형 구조이며, 나무를 거꾸로 그린 형태이다. 1.2 트리 용어 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드 간선(edge): 노드간의 연결 레벨..

    [자료구조] 순환 (Recursion) - 팩토리얼, 거듭제곱 계산, 피보나치 수열, 하노이의 탑, 영역 채색
    IT/Data Structure

    [자료구조] 순환 (Recursion) - 팩토리얼, 거듭제곱 계산, 피보나치 수열, 하노이의 탑, 영역 채색

    1. 순환 1.1 순환이란? 순환(Recursion)은 컴퓨터 과학에서 재귀라고도 하며 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 순환은 알고리즘을 해결하는데 사용되는 일종의 프로그래밍 기법이며, 트리 자료구조를 공부하기에 앞서 간단하게 알아보자. 1.2 반복 vs 순환 프로그래밍 언어에서 같은 일을 반복하기 위한 방법에는 반복(iteration)과 순환(recursion)이 있다. 반복이란 for나 while 등의 반복문을 사용하여 조건이 만족할 때까지 계속하여 반복시키는 방식이다. 순환은 위에서 말한대로 method가 자기 자신을 다시 호출하는 방식을 의미한다. 일반적으로 순환은 method 호출을 하게 되므로 반복에 비해 수행 속도가 떨어진다. 하지만, 필요한 경우 순환을 사용하면 반..

티스토리툴바