Computer Science/알고리즘, 자료구조10 자료구조 - Tree, Binary Tree Tree 트리는 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로, 부모 - 자식 관계로 표현된다. 스택, 큐와는 달리 2차원의 자료 구조로, 정점(node)와 간선(edge)를 이용해 데이터의 배치 형태를 추상화시킨다. 트리의 기본 특징 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다. 트리내에 또 다른 트리가 있는 재귀적 자료구조이다. 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조이다. 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다. 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다, 트리의 구성 요소 정점(node): 데이터를 직접적으로 담고 있는 요소 간선(edge): 노드를 잇는 연결선 뿌리.. 2023. 3. 31. 자료구조 - 선형 자료구조 자료구조(Data Structure)란 자료에 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법이다. 자료구조는 저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분되며, 선형 자료구조는 데이터가 일렬로 나열되어 있고 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다. 선형 자료구조의 종류에는 array, linked list, stack, queue 등이 있으며 비선형 자료구조로는 tree, graph 등이 있다. 이번 포스팅에서는 선형구조를 가지고 있는 자료구조를 개념 위주로 살펴보고, 비슷한 것들끼리 묶어 비교해보려고 한다. 배열 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다. 미리 크기를 정해놓고 생성하며, 해당 크기만큼의 연속된 메모.. 2023. 3. 31. Quick Sort vs Merge sort Quick sort, Merge sort는 이전 게시물인 https://nueahx7674.tistory.com/6 에서 확인 할 수 있다. 해당 게시글에서는 Quick Sort와 Merge sort의 차이를 중점적으로 다룬다. Quick Sort와 Merge Sort의 차이 퀵소트는 불안정 정렬, 병합 정렬은 안정 정렬이다. 퀵 정렬은 최악의 경우(오름차순 정렬이거나 내림차순 정렬일 경우) O(n^2)의 시간 복잡도를 가지지만 병합 정렬은 O(n log n)으로 동일하다. 병합 정렬은 추가 메모리 공간을 필요로 한다. 퀵 정렬이 평균 시간 복잡도에서는 Merge Sort보다 빠르다. 이는 아래에서 자세히 설명하겠다. Quick Sort가 Merge Sort보다 빠른 이유 이를 설명하기 위해서는 지역성의.. 2023. 1. 31. 정렬 알고리즘 정렬 알고리즘이란? 정렬 알고리즘은 원소들을 일정한 순서대로 열거하는 알고리즘을 말한다. 정렬 알고리즘의 대표적인 예시로는 삽입 정렬(Insertion sort), 선택 정렬(Selection Sort), 버블 정렬(Bubble sort), 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap sort)이 있다. Stable vs Unstable 정렬을 진행할 때, 같은 값의 원소더라도 상대적인 위치가 유지 되면 stable한 정렬 방식, 그렇지 않으면 unstable한 정렬 방식이다. 예를 들어, 아래의 숫자들을 오름차순으로 정렬해보자. 이때, 1’과 1은 같은 숫자이다. 5 3 1` 9 2 1 정렬 알고리즘이 수행 된 이후 1` 1 2 3 5 9 로 정렬 되었다면 상대적.. 2023. 1. 31. 이전 1 2 다음
