본문 바로가기

전체 글68

[JS] 트리와 이진 탐색 트리 트리 Tree 트리는 항상 루트(root)에서부터 시작된다. 루트는 자식(child) 노드를 가지며, 간선(edge)으로 연결되어 있다. 자식 노드의 개수는 차수(degree)라고 하며, 크기(size)는 자신을 포함한 모든 자식 노드의 개수다. 높이(height)는 현재 위치에서부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리(subtree) 구성을 띤다. 레벨(level)은 0부터 시작한다. 논문에 따라 1부터 시작하는 경우도 있으나, 0부터 시작하는 것이 좀 더 일반적이다. 트리는 항상 단방향(uni-directional)이기 때문에 간선의 화살표는 생략 가능하다. 그림에서도 마찬가지로 생략해서 표현했고 일반적으로 방향은 위.. 2022. 12. 17.
[JS] 스택(stack)과 큐(Queue) 스택(stack) 스택(stack) 다음과 같은 성질을 갖는 자료형입니다. 데이터를 집어넣을 수 있는 선형(linear) 자료형입니다. 나중에 집어넣은 데이터가 먼저 나옵니다. 이 특징을 줄여서 LIFO(Last In First Out)라고 부릅니다. 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있습니다. 만약 스택이 비어있을 때 자료를 꺼내려고 시도하면 스택 언더플로우(Stack underflow)가 발생하고 반대로, 스택이 꽉 차있을때 자료를 넣으려고 하면 스택 오버플로우(Stack overflow)가 발생 예시 웹 브라우저 뒤로가기 : 가장 나중에 열린 페이지부터 뒤로 가기를 실행합니다. 문서작업에서 Ctrl+Z : 가장 .. 2022. 12. 17.
[프로그래머스] 피보나치 수 문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 제한 사항 n은 2 이상 100,000 이하인 자연수입니다. 입출력 예 N return 3 2 5 5 입출력 예 설명 피보나치수는 0번째부터 0, 1, 1, 2, 3, .. 2022. 12. 16.
[JS]이중연결리스트 Doubly Linked Lists 다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키게 하면 이중 연결 리스트가 된다. 뒤로 탐색하는 게 빠르다는 단순한 장점 이외에도 한 가지 장점이 더 있는데, 단순 연결 리스트는 현재 가리키고 있는 노드를 삭제하는 게 한 번에 안 되고 O(n)이 될 수밖에 없는데 비해 이중 연결 리스트에서 현재 노드를 삭제하는 것은 훨씬 간단하다. 대신 관리해야 할 참조가 두 개나 있기 때문에 삽입이나 정렬의 경우 작업량이 더 많고 자료구조의 크기가 약간 더 커진다. 단일 연결 리스트보다는 손상에 강한 편이다. Head와 Tail노드를 갖고 있다면 둘 중 하나를 가지고 전체 리스트를 순회할 수 있기 때문에 끊어진 체인을 복구하는 게 가능하다. 단일 연결 리스트는 Tail노드로는 리스트 순회가 불가능하고 He.. 2022. 12. 16.

티스토리툴바