자료구조&알고리즘
1.[자료구조] 스택(Stack)
스택(Stack) 스택의 개념 데이터가 일렬로 나열되어 저장되는 선형(linear) 자료구조 한쪽 끝에서 삽입, 삭제가 이루어지는 후입선출(LIFO, Last in First Out) 구조를 가진다. 스택에 데이터가 삽입될 위치를 Top이라고 한다. 스택의 기본 연산 push(data): 스택의 top에 데이터를 삽입 pop: 스택의 top에 위치한...
2.[자료구조] 큐(Queue)
큐(Queue) 큐의 개념 스택과 마찬가지로 선형(linear) 자료구조 큐는 스택과 다르게 한쪽 방향에서 삽입이, 반대편에서 삭제가 이루어지는 선입선출(FIFO, First In First Out) 구조를 가진다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조이다. 데이터가 삭제될 위치를 Front/Head, 마지막 데이터가 삽입된 위치를 Rear/Tai...
3.[자료구조] 해시테이블(HashTable), 해시맵(HashMap) in Javascript
해시테이블(HashTable) 해시 테이블은 key-value pair로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시테이블(Hash Table)의 구조 해시테이블에 대해 이해하기 위해서는 먼저 해시테이블의 구성에 대해 이해할 필요가 있다. 해시테이블은 키(key), 해시 함수(Hash Function), ...
4.[자료구조] 힙(Heap)
힙(Heap) 힙은 완전 이진트리 기반의 자료구조로, 우선순위 큐를 구현하는데 사용된다. 트리 구조이기 때문에 삽입과 삭제에 O(logN)의 시간이 소요된다. 힙의 종류 힙의 종류에는 최대힙, 최소힙이 있다. 힙을 통해 최댓값이나 최솟값을 찾는 연산을 빠르게 수행할
5.[알고리즘] 완전탐색(Brute-Force Search / Exhaustive Search) 기법
완전 탐색이란? 컴퓨터의 계산 능력을 이용해 가능한 모든 경우의 수를 체크하여 답을 찾는 방법을 의미한다. 예를 들어, 4자리 암호로 구성된 자물쇠가 있다고 생각해보자. 자물쇠의 암호를 전혀 알지 못할때, 시도할 수 있는 가장 확실한 방법은 0000~9999까지 모든 조합을 시도해 보는 것이다. (최대 10000번의 시도로 해결 가능) 하지만 Compu...
6.[알고리즘] 이진 탐색 / 이분 탐색(Binary Search)
이진 탐색 / 이분 탐색(Binary Search) 이진 탐색 알고리즘은 데이터가 정렬된 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간 값을 선택해 찾고자 하는 값 X와 비교한다. 이때 X가 중간값보다 작으면 중간값을 기준으로 좌측의 데이터들을, X가 중간값보다 크면 중간값을 기준으로 우측의 데이터들을 대상으로 다시 탐색한다. 위의 과정을 ...
7.[자료구조] 그래프(Graph)
그래프 Graph 그래프는 정점(node)과 간선(edge)으로 이루어진 자료구조이다. 조금 더 구체적으로 말하면 각 정점(데이터)들의 관계(연결)를 나타낸 것으로 이해하면 된다. 비선형 자료구조로, 트리도 그래프 중 하나에 속한다. 그래프 용어 정점(node) : vertex 라고도 하며 정점에는 데이터가 저장된다.(0,1,2,3) 간선(edge) :...
8.[알고리즘] DFS & BFS
DFS(Depth-First-Search) 깊이 우선 탐색 가장 깊은 곳까지 탐색 모든 노드를 방문하고자 할때 사용되는 방법 ex) 미로 찾기, 그래프의 위상정렬, 전체 탐색, 연결 구성요소 찾기, 이분 그래프 등 BFS에 비해 검색 속도는 느림 스택, 재귀함수 사용해 구현 DFS 구현 1. 재귀로 구현 방문하지 않은 노드(v)일 경우 dfs 함수를...