IT

    [자료구조] 우선순위 큐와 힙 (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 호출을 하게 되므로 반복에 비해 수행 속도가 떨어진다. 하지만, 필요한 경우 순환을 사용하면 반..

    [자료구조] 리스트 (ArrayList vs LinkedList)
    IT/Data Structure

    [자료구조] 리스트 (ArrayList vs LinkedList)

    1. 리스트 1.1 리스트란? 리스트(List)란 앞에서 공부한 배열, 스택, 큐 등과 같은 선형 자료구조이다. 그렇다면 이들과 리스트의 차이점은 무엇일까? 스택과 큐의 경우 자료의 접근이 전단(front) 혹은 후단(rear)에 제한되어 있다. 하지만 리스트는 이러한 제한이 없다. 즉, 임의의 위치에 있는 항목에 접근이나 연산이 가능하다는 것이다. 1.2 배열 vs 리스트 배열(array) 또한 임의의 위치에 접근이 가능하다. 그렇다면 배열과 리스트의 차이는 무엇일까? 배열은 각각의 원소에 순서대로 index가 할당되어 있다. 위 배열에서 c 원소를 삭제하는 경우 아래와 같은 형태가 된다. 삭제한 c의 메모리 공간은 빈 공간으로 남아있으며, d와 e의 index는 변함이 없다. 만약 위의 행위가 리스트..

티스토리툴바