개발에 도움이 되는 (78) 썸네일형 리스트형 이진 탐색 트리(Binary Search Tree, BST) - 이진 탐색 트리 (Binary Search Tree) 정렬된 이진 트리로 다음과 같은 규칙을 갖는다. 1. 이진 탐색 트리의 노드에 저장된 값은 유일하다. 2. 부모의 값은 왼쪽 하위 트리 노드들의 값보다 항상 크다. 3. 부모의 값은 오른쪽 하위 트리 노드들의 값보다 항상 작다. 4. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다. BST의 검색에 대한 시간 복잡도는 균형 상태면 O(log n)의 시간이 걸리고 불균형 상태(편향 트리 Skewed Tree)라면 최대 O(n)의 시간이 걸린다. 이러한 문제를 막기 위해 Rebalancing 기법이 등장하였다. (ex. Red-Black Tree 등) - 이진 탐색 트리의 연산 1. 검색 : 이진 탐색 트리에서 특정 요소의 위치를 찾는다. .. 이진 트리(Binary Tree) - 이진 트리 (Binary Tree) 모든 노드들이 둘 이하(공집합 포함)의 자식을 가진 트리 - 이진 트리 유형 1. 전 이진트리 (Full Binary Tree or Strict Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리 2. 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리, 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함 3. 포화 이진 트리 (Perfect Binary Tree) : 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖음 4. 균형 이진 트리 (Balanced Binary Tree) : 왼쪽과 오른쪽.. 트리(Tree) - 트리 (Tree) 계층적 관계를 표현하는 비선형 자료 구조, 연결된 비순환 무방향성 그래프 트리 내에 다른 하위 트리가 있고 그 하위 트리안에는 또 다른 하위 트리가 있는 재귀적 자료 구조 - 기본 용어 1. 노드 (Node) : 트리를 구성하고 있는 기본 요소, 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음 2. 간선 (Edge) : 노드와 노드 간의 연결선 3. 루트 노드 (Root Node) : 트리 구조에서 부모가 없는 최상위 노드 4. 부모 노드 (Parent Node) : 자식 노드를 가진 노드 5. 자식 노드 (Child Node) : 부모 노드의 하위 노드 6. 형제 노드 (Sibling Node) : 같은 부모를 가지는 노드 7. 외부 노드 (External Node, Oute.. 그래프(Graph) - 그래프 (Graph) 정점의 집합과 간선의 집합으로 구성된 비선형 데이터 구조 - 정점 : 자료를 저장하려는 자료의 단위 (= 노드) - 간선 : 정점 사이를 연결하는 선으로 두 정점 쌍(n1, n2)으로 표현 - 방향성(유향) 간선 (Directed edge) : 뱡향을 가진 정점의 쌍(u, v)으로 화살표로 표현하고 단방향을 가리킴 u는 출발점 v는 도착점을 의미. 방향성 간선을 가진 그래프를 방향성 그래프(Directed Graph)라고 함. - 무방향성(무향) 간선 (Undirected edge) : 방향이 없는 정점의 (u, v)으로 직선을 표현하며 양방향을 가리킴 간선 (u, v)와 (v, u)는 같다. 무방향성 간선을 가진 그래프를 무방향성 그래프(Undirected Graph)라고 함... 해시 테이블(Hash Table) - 해시 테이블 (Hash Table) Key 값을 해시 함수를 통해 변환한 값(해시 값)을 index로 삼아 Value 데이터를 저장하는 자료 구조이다. 내부적으로 배열을 사용하여 데이터를 저장하고, 고유의 index로 접근하기 때문에 빠른 검색 속도(충돌이 일어나지 않는 경우에 O(1))를 갖는다. 대표적인 해시 함수로는 Key 값을 테이블 크기로 나누어 계산(ex. 해시 값 = Key % 테이블 크기)하는 Division Method과 문자열을 키로 사용하는 해시 테이블에 잘 어울리는 알고리즘으로 Key 값을 ASCII 코드로 바꾸고 값을 합한 데이터를 이용하는 Digit Folding 등이 있다. 하지만 문제는 아무리 좋은 해시 함수를 이용한다해도 비둘기집의 원리에 의해 충돌이 발생할 확률이 있다.. 스택(Stack), 큐(Queue) 스택(Stack)과 큐(Queue) 모두 선형 자료 구조이며, 추상 데이터 타입(ADT)이다. - ADT : 자료 구조의 방법이 코드로 정의 된 것이 아닌 그 구조의 행동 양식만 정의된 것 (일종의 규칙) - 스택 (Stack) LIFO (Last In First Out) 즉, 나중에 들어간 원소가 먼저 나온다. - 사용 사례 재귀 알고리즘, DFS, 실행 취소, 웹 브라우저 뒤로가기 등 - 큐 (Queue) FIFO (First In First Out) 즉, 먼저 들어간 원소가 먼저 나온다. - 사용 사례 어떠한 작업 및 데이터를 순서대로 실행 및 대시킬 때 사용 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 많이 사용함. 배열(Array), 연결 리스트(Linked List) - 배열 (Array) 물리적 순서와 논리적 순서가 같은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음 따라서 Index로 해당 원소에 접근할 수 있다. 그렇기 때문에 원소의 Index를 알고 있으면 시간복잡도 O(1)에 해당 원소로 접근할 수 있다. 하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤, Shift를 해줘야 하는 상황이 발생할 수 있기 때문에 Shift하는 비용이 발생하고 이 경우의 시간 복잡도는 O(n)이 된다. 배열의 크기가 대부분 정적으로 결정된다. 배열은 순차적인 데이터를 저장하며 값보다는 순서가 중요하거나 다차원 데이터를 다룰 때, 어떤 특정 요소를 빠르게 읽어야할 때, 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때 사용.. JavaScript - 정의 : 웹페이지에 생동감을 불어 넣기 위해 만들어진 프로그래밍 언어. 객체 기반의 스크립트 언어. - 특징 1. 인터프리터 언어지만, 실행하는 플랫폼에 따라 인터프리팅과 컴파일이 혼합되어 사용하여 성능을 크게 향상 시킴 자바스크립트 엔진 내부에서 실행 중 컴파일이 필요한 경우 내부에서 컴파일을 한다. 2. 동적 타입 언어 : 변수 타입이 없으며, 프로그램 실행 도중에도 변수 타입이 변경될 수 있음 3. 프로토타입 기반의 객체 지향 언어 : 클래스 기반(상속, 캡슐화 등)의 언어가 아닌 프로토타입 기반의 객체지향 언어 - 프로토타입 : 어떤 객체의 원본 / 원형이 되는 객체 4. 일급 객체 함수 : 고차 함수를 구현할 수 있어 함수형 프로그래밍이 가능 - 일급 객체 조건 1. 무명의 리터럴로 생성할 .. 이전 1 ··· 5 6 7 8 9 10 다음
