Algorithm

1. Tree(트리) 트리는 노드(node)들과 이들을 연결하는 간선(edge)들로 구성된 계층적 자료구조이다. 각 노드는 부모-자식 관계를 가지며, 사이클이 없는 연결구조를 형성한다. 트리는 데이터를 계층적으로 표현하기에 적합하며, 검색과 정렬에 효율적인 구조를 제공한다. 우리가 사용하는 폴더 구조도 트리라고 할 수 있다.   2. 트리와 그래프의 차이점트리에 대해 이해하기 위해서는 그래프와 트리의 차이점을 알아보면서 이해하면 보다 쉽다. 트리는 사실 그래프의 한 종류이다. 특별한 제약조건들을 가진 그래프라고 생각하면 된다. 하지만 설명의 용이성을 생각하여 트리와 그래프는 따로 구분지어서 말하도록 하겠다. 그래프에 대한 설명은 아래 글을 참고하길 바란다. [알고리즘] Graph 자료구조 개념 (JS)1..

1. Graph(그래프)그래프는 노드(또는 정점)와 이들을 연결하는 간선으로 구성된 자료구조이다. 그래프는 네트워크 구조를 표현하는데 매우 유용하다. 또한 최소 신장 트리(MST), 깊이우선탐색(DFS), 너비 우선탐색(BFS)과 같은 알고리즘에서 기본적으로 사용하는 자료구조 중 하나이다. 그래프는 G = (V, E)는 노드(정점)과 간선으로 이루어져 있다.V: 정점(Vertex) 집합E: 간선(Edge) 집합그래프는 방향 그래프, 무방향 그래프, 가중치 그래프로 크게 3가지 유형이 존재한다. 간선(Edge)에 방향의 존재 유무를 통해 방향그래프와 무방향 그래프로 나눌 수 있으며, 간선에 가중치가 있으면 가중치 그래프로 분류한다.방향 그래프에 가중치가 있는 경우 방향 가중치 그래프이고, 무방향에도 마찬가..

1. Heap(힙)힙은 완전이진트리 구조를 기반으로 하는 자료구조로, 특정한 순서 속성을 만족한다. 주로 최댓값이나 최솟값을 빠르게 찾아야 하는 경우에 사용된다.힙에는 최대힙(MaxHeap)과 최소힙(MinHeap) 2가지 방식이 존재한다.최댓값 최솟값을 찾는 자료구조로써 우선순위가 높은 데이터를 빠르게 찾아야 하는 경우에 효율적인 자료구조이다.힙 자료구조는 우선순위 큐 구현, 다익스트라 알고리즘 등에 응용하여 사용되기도 한다.  2. Heap 작동 방식힙의 주요 연산은 push(삽입 연산), pop(최댓값/ 최솟값 추출), peek(최댓값/ 최솟값 확인), build Heap(힙 생성) 총 4개로 구분지을 수 있다.javascript로 기본적인 클래스를 생성하면 다음과 같다.class MinHeap {..

완전탐색 ( Complete Search) 이란? 완전탐색을 알기 전에 상위 개념인 탐색에 대해 알아야 하는 탐색(Search) 알고리즘은 많은 데이터 중 목적에 맞는 데이터를 찾기 위한 방법이다. 탐색 알고리즘에는 여러 가지 탐색 방법이 존재하는데 완전 탐색은 그중 대표적인 알고리즘 중 하나이다. 완전탐색(Complete Search) 은 말그대로 "모든 경우의 수를 검사" 하는 방식으로 브루트포스( Bruth-Force) 알고리즘으로 불리기도 한다. "brute"는 "무식한", "force"는 "힘"을 의미하는데 무식한 힘 즉 무식하게 전체 모든 경우의 수를 검사하는 알고리즘을 의미한다. 완전탐색(Complete Search)은 전체 모든 경우의 수를 검사하기 때문에 매우 큰 메모리를 사용하며, 시간..

알고리즘 공부를 시작하기 앞서 기본적으로 먼저 다뤄야 할 수학 부분에서는 대표유형으로 크게 나누면 약수, 소수, 최대공약수와 최소 공배수 유형으로 나누어 볼 수 있다. 각 유형별로 알아야 할 포인트를 다뤄보도록 하겠다. 약수 약수를 구하는 방법은 어떤 자연수N이 존재하는 경우 N이하의 자연수로 N을 나누었을 때 나머지가 0이면, 해당 N이하의 자연수는 자연수N의 약수이다. 어떤 자연수 N이 37일 때 코드로 작성하면 다음과 같다. n=36 for i in range(1,n+1): if n%i==0:print(i,end=" ") 결과: 1 2 3 4 6 9 12 18 36 하지만 이와 같이 작성하면 시간 복잡도는 O(n)으로 자연수 N이 10^8이 되는 경우 1초의 시간이 걸리게 된다. 더 적은 시간이 걸..

자료구조 개념 자료구조란? 데이터를 구조적으로 활용하기 위해 표현하는 것을 말한다. 자료구조는 알고리즘 공부 전 필수적으로 알고 넘어가야 하는 부분이며, 알고리즘 문제의 대부분은 자료구조를 사용하여 풀어나가는데 이 때 어떤 자료구조를 사용하냐에 따라 문제의 난이도가 바뀔 수 있다. 자료구조의 목차를 오른쪽에 간략하게 표현해보았다. 자료구조에서는 이번 글에서 다루는 스택, 큐, 덱, 힙과 같이 지식이 필요한 부분들 이외에도 평상시에 배우는 언어에 기본적으로 존재 하는 배열(리스트)와 같이 기본적인 자료의 표현도 자료구조라고 할 수 있다. 알고리즘을 공부하기 위해서는 선행적으로 자료구조의 이해는 필 수 이다. 한 알고리즘에 한 가지의 자료구조 또는 여러 가지의 자료구조가 조합되어 사용되기 때문이다. 왼쪽과 ..