Data Structure & Algorithm
-
트라이Data Structure & Algorithm 2022. 4. 4. 20:51
정의 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 특징 검색어 자동완성, 사천 찾기 등에 응용 가능 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 탐색 가능 L 이 문자열의 길이일 때 탐색, 삽입 시 O(L) 만큼 시간 소요 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용 규칙 루트는 비어 있음(공백) 각 간선(링크)은 추가될 문자를 키로 가짐 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐 해시 테이블과 연결 리스트를 이용하여 구현 가능
-
BFS, DFSData Structure & Algorithm 2022. 3. 29. 21:02
BFS 정의 Breadth-First Search 의 약자로 너비 우선 탐색 알고리즘을 뜻함 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 특징 Queue 를 이용하여 구현 가능 시작 지점에서 가까운 정점부터 탐색 V 가 정점의 수, E 가 간선의 수일 때 BFS 의 시간복잡도는 O(V + E) DFS 정의 Depth-First Search 의 약자로 깊이 우선 탐색 알고리즘을 뜻함 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘 특징 Stack 을 이용하여 구현 시작 정점에서 깊은 것부터 탐색 V 가 정점의 수, E 가 간선의 수일 때 DFS 의 시간복잡도는 O(V + E)
-
힙Data Structure & Algorithm 2022. 3. 27. 22:06
정의 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있음 특징 우선순위가 높은 요소가 먼저 나가는 특징을 가짐 => 우선순위가 높은 요소를 루트로 배치하고 루트가 가장 먼저 나감 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있음 => 오름차순/내림차순 차이 자바스크립트에선 직접 구현해서 사용해야 함 힙은 추가/삭제가 핵심 로 우선순위 큐와 비슷하지만 우선순위 큐는 큐를 활용한 개념이기 때문에 같은 것은 아니며 힙이 우선순위 큐보다 효율성이 높은 편 힙 요소 추가 알고리즘 요소가 추가될 때는 트리의 가장 마지막에 추가 추가된 요소가 부모 정점보다 우선순위가 높다면 부모 정점..
-
트리Data Structure & Algorithm 2022. 3. 27. 21:44
정의 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 자료 구조 용어 Root: 가장 상위의 정점 Node: 각 정점 Leaf Node: 자식이 없는 노드 Level: Root 부터 몇 번째 깊이(단계)에 위치해 있는 지 표시 Degree: 한 정점에서 뻗어 나가는 간선의 수 특징 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가짐 정점이 N 개인 트리는 반드시 N-1 개의 간선을 가짐 루트에서 특정 정점으로 가는 경로는 유일함 실생활 예: 조직도, 디렉토리 구조 이진 트리 각 정점이 최대 2개의 자식을 갖는 트리 완전 이진 트리: 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리 포화 이진 트리: 마지막 레벨까지 모두 채워져 있는 트리 편향 트리: 한 방향으로만 정점이 이어..
-
그래프Data Structure & Algorithm 2022. 3. 27. 21:31
정의 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 특징 정점 집합과 간선 집합으로 표현 가능 정점은 Node, 간선은 Edge 라고도 함 정점은 여러 개의 간선을 가질 수 있음 선형 구조는 앞 뒤로 하나의 요소만 가질 수 있음 방향 그래프와 무방향 그래프로 나눌 수 있음 간선은 가중치를 가질 수 있음 사이클이 발생할 수 있음 탐색 시 무한 루프에 빠지지 않도록 하는 것에 주의 인물 관계도로 비유 가능하며 지하철 노선도, 페이지랭크 등에 사용 간선 방향성에 따른 분류 무방향 그래프 간선으로 이어진 정점끼리 양방향으로 이동 가능 (A, B) 와 (B, A) 는 같은 간선으로 취급 ex) 양방향 통행 도로 방향 그래프 간선에 방향성이 존재하는 그래프 와 간선을 통해 양방향으로 갈 수 있더라도..
-
해시 테이블Data Structure & Algorithm 2022. 3. 27. 16:17
정의 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조 특징 요소의 추가는 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행 테이블의 인덱스는 Bucket 이라고 함 테이블의 각 요소는 키-값을 둘 다 저장 Hash: 해쉬 브라운의 해쉬와 같은 단어이며 고기와 감자를 잘게 다져 요리하듯, 입력받은 키를 잘게 잘라 숫자로 만든다는 점에서 유사 해시 함수 입력받은 값을 특정 범위 내 숫자로 변경하는 함수 해시 함수의 결과가 동일하다면 해시 충돌 발생 해시 충동 해결 방법 선형 탐사법: 충돌이 발생하면 인덱스를 옆으로 한 칸 이동 단순하지만 데이터가 몰릴 수 있다는 단점이 있으며 충돌이 연속해서 발생하면 계속해서 옆으로 이동하게 됨 최악의 경우에 탐색에 O..
-
큐Data Structure & Algorithm 2022. 3. 24. 21:11
정의 First In First Out 이라는 개념을 가진 선형 자료구조 Linear Queue와 Circular Queue가 존재 특징 Front: 큐의 맨 앞 요소 Rear: 큐의 맨 뒤 요소 EnQueue: 큐(의 가장 뒤)에 요소를 추가하는 것 DeQueue: 큐(의 가장 앞)에서 요소를 제거하는 것 현실에서 비유하면 대기열이라고 할 수 있음 Linear Queue 를 Array 로 구현하는 경우 Javascript Array 로 표현 가능하지만 배열의 길이가 고정되어 있지 않기 때문에 큐가 무한정으로 커질 수 있음 DeQueue 를 한 뒤에 요소를 앞으로 당기게 되면 O(n) 의 시간이 소요됨 Linear Queue 를 Linked List 로 구현하는 경우 Front 는 Head 가 되고 Re..
-
스택Data Structure & Algorithm 2022. 3. 23. 21:17
정의 Last In First Out 이라는 개념을 가진 선형 자료구조 특징 push: 스택에 요소를 추가하는 것 pop: 스택에서 요소를 제거하는 것 top: 스택의 가장 위(마지막)에 있는 요소 박스나 프링글스를 비유로 들 수 있음 Javascript 에서 스택 함수 호출이 스택 메모리로 관리됨 배열로 스택 구현 가능 => 배열 요소 사이에 새로운 요소를 추가하거나, 삭제하지 않으므로 효율이 높아짐 Array 클래스에 push, pop 메서드가 구현되어 있음