본문 바로가기

학습노트/자료구조

 (10)
[JavaScript] Quick Sort(퀵 정렬) Quick Sort(퀵 정렬)의 개념 Quick Sort(퀵 정렬) 구현 소스 코드 function quickSort(arr) { // arr의 요소가 하나이면 arr 자체를 그대로 반환 if(arr.length ..
[JavaScript] Tree(트리) - Depth-first Search(깊이 우선 탐색), Breadth-first Search(너비 우선 탐색) 이진 트리의 탐색에는 크게 2가지 방법이 있다. 이번 포스팅에서는 깊이 우선 탐색(Depth-first Search)과 너비 우선 탐색(Breadth-first Search) 이 두 가지에 대하여 알아보고 각 순회들을 코드로 구현해 보려고 한다. Depth-first Search(깊이 우선 탐색) 1. Pre-Order Traversal(전위 순회) root -> left -> right 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 A, B, D, H, I, E, J, K, C, F, L, M, G, N, O 순으로 탐색 2. In-Order Traversal(중위 순회) left -> root -> right 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 H, D, I, B, J, ..
[JavaScript] Tree(트리) - Binary Search Tree(이진 탐색 트리) 지난 포스팅에서 트리 구조의 이론적인 부분을 학습하였다. 이제 그 이론을 바탕으로 이진 트리를 Javacript언어로 구현하려고 한다. 이진 트리를 구현하는 방법론 이진 트리를 구현하는 방법은 두 가지가 있다. 1. Array(배열)를 이용하는 방법 노드에 번호를 부여하고 그 번호에 해당하는 값을 인덱스 번호로 활용한다. 따라서 배열을 첫 번째 요소인 인덱스 0 직관화를 위해 비워둔다. 2. Linked List(연결 리스트)를 이용하는 방법 Linked List(연결 리스트)기반으로 왼쪽 링크와 오른쪽 링크에 자식 노드를 연결하는 방법이다. 연결 리스트 구조 자체가 트리 구조와 일치 하기 때문에 굉장히 직관적인 이해가 가능하다. 이 방법으로 트리 구조를 구현하는 것은 굉장히 좋은 구현이라고 할 수 있다..
[JavaScript] Tree(트리) - 이론학습 트리의 정의 계층적 관계를 표현하는 자료구조를 트리라고 한다. 회사내의 조직도, 의사결정을 하는데 필요한 알고리즘 등을 트리 형태로 나타내고 있다. 트리의 용어 정리 - 노드(node) : 트리를 구성하는 각 요소 A, B, C, D, E, F - 간선(edge) : 노드와 노드를 연결하는 선 - 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드 A - 단말 노드(terminal node) or leaf : 트리 구조에서 아래로 또 다른 노드(자식 노드)가 존재하지 않는 노드 C, D, E, F - 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 A, B - A는 B, C, D의 부모 노드(parent node)이다. - B, C, D는 A의 자식 노드(chi..
[JavaScript] Queue - Linear Queue(선형 큐) Queue의 개념 큐는 FIFO(Frist In First Out)의 특징을 가지고 있다. 우리나라 말로 선입선출이라고 한다. 예를 들어 마트, 편의점 또는 가게 등에서 처음 들어온 물건을 가장 먼저 파는 것 같은 형태이다. 먼저 진열된 유통기한이 가까운 제품을 먼저 팔거나 가게, 콘서트 등에서 줄을 서고 있는 고객들을 연상시키면 될 것 같다. Linear Queue(선형 큐) 구현 선형 큐란 것은 배열의 공간에 들어간 데이터가 고정되어 데이터를 빼내더라도 초기화하지 않으면 원래 데이터가 있던 배열자리에 더이상 다른 것이 들어갈 수 없는 형태의 Queue이다. 1. class 생성자로 뼈대 만들기 class queueType { constructor(size) { this.maxSize = size; t..
[JavaScript] Stack(스택) 자바스크립트에서는 배열 메서드가 정의가 되어 있어 딱히 구현한 필요는 없지만 c언어 같은 로우레벨의 언어에서는 함수들을 정의해줘야 스택의 개념을 쓸 수 있다. 비록 자바스크립트이지만 자료구조의 이해를 위해 해당 개념을 직접 구현해 보려고한다. Stack의 개념 스택은 LIFO(Last In First Out)의 특징을 가지고 있다. 즉, 아래 그림과 같이 맨 마지막으로 들어갈 f가 제일 처음 꺼내어 진다는 이야기이다. 스택의 최대 단점으로는 제일 먼저 들어간 데이터를 꺼낼 때 모든 데이터를 연산해야한다는 것이다. 데이터 a를 빼내고 싶다면 f, e, d, c, b를 차례대로 꺼낸 후 a를 꺼내고 다시 b, c, d, e, f 순으로 집어 넣어야 한다. Stack 구현 1. stack이라는 class만들어..
[JavaScript] List - Double Linked List(이중 연결 리스트) Double Linked List(이중 연결 리스트)의 개념 이중 연결 리스트는 Link가 앞 뒤 node와 서로 연결되어 있는 리스트를 말한다. Front Link와 Back Link로 전, 후 노드에 접근이 가능하다는 특징이 있다. 맨 앞에 있는 노드와 맨 뒤에 있는 노드가 서로 연결되어 있어 첫 노드에서 마지막 노드를 검색할 때 시간복잡도가 O(1)로 찾을수 있다는 장점이 있다. Javascript를 이용한 Double Linked List(이중 연결 리스트) 구현 1. 클래스 생성자를 통하여 Data와 Link의 뼈대를 잡아준다. class nodeType{ constructor(item) { this.data = item; this.forwardLink = null; this.backLink =..
[JavaScript] List - Circular Linked List(원형 연결 리스트) Circular Linked List(원형 연결 리스트)의 개념 원형 연결 리스트는 연결 리스트와 다르게 마지막 node의 link가 null 값을 향하는 것이 아니고 처음 Head 부분을 향하고 있다. 따라서 node의 링크가 끊임 없이 연결되어 있다. JavaScript를 이용한 Circular Linked List(원형 연결 리스트) 구현 원형 연결 리스트가 연결 리스트와 크게 다른 점은 위에 설명한 것 처럼 마지막 Link가 Head로 들어가게 만들어 주면 된다. 1. 클래스 생성자를 통하여 Data와 Link의 뼈대를 잡아준다. class nodeType { constructor(item) { this.data = item; this.link = null; } } 2. 클래스 안에 원형 연결 리..
[JavaScript] List - Linked List(연결 리스트) 리스트 자료구조는 데이터를 나란히 저장하며 중복된 데이터 또한 저장이 가능하다. 리스트 자료구조는 구현방법에 따라 Array List(배열 리스트)와 Linked List(연결 리스트)로 나눌 수 있다. 자바스크립트의 배열은 배열의 크기를 데이터 추가/제거와 동시에 자동적으로 정의가 된다. 하지만 c언어, java 등과 같은 언어들은 배열의 크기가 자동적으로 늘어나거나 줄어들게 하는 기능이 없기 때문에 배열을 사용하는 범위가 한정되어 있다. 따라서 노드라는 개념으로 구조체들을 서로 연결하는 리스트 개념을 만들어 활용하는 것이 효율적이다. Array List(배열 리스트)의 개념 배열 리스트는 어떤 언어에서도 기본적으로 내장된 데이터 타입이다. 따라서 가장 사용하기 쉽다. 물리적으로 고정되어 있다고 볼수있..
[JavaScript] Array(배열) 자료구조를 이해하기 위해 처음으로 알아야 하는 것은 배열(Array)이라고 생각합니다. 배열의 자세한 내용과 정의는 MDN web docs에서 더욱 자세히 볼 수 있지만 제가 공부한 배열에 대해서 간단히 정리해보려고 합니다. 배열의 구성 배열은 인덱스 번호가 0번 부터 시작한다. 길이는 0이 아닌 1부터 시작한다. 인덱스 번호와 길이는 다르다는 것을 주의해야 한다. javascript 배열 선언 방법 javascript는 배열을 선언할 수 있는 두 가지 방법을 가지고 있다. ////////////// 1. 생성자 함수로 배열 선언 ///////////////// // 빈 배열 생성 let arr = new Array(); // 빈 배열에 값 넣기(문자열) arr[0] = 'one'; arr[1] = 't..

티스토리툴바