PGDC_자료구조&알고리즘

큐 (Queue) First In First Out (먼저 삽입된 item이 먼저 삭제된다) 라는 개념을 가진 선형 구조이다.

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조정점 집합과 간선 집합으로 표현할 수 있다.

트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.

우선순위 큐는 일반적인 FIFO인 큐와 달리 우선순위가 높은 요소가 먼저 나가는 개념이다.힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다.우선순위 큐 !== 힙우선순위가 높은 요소가 먼저 나간다.루트가 가장 큰 값이 되는 최대 힙(Max Heap)와 루트가 가장

트리를 이용한 자료구조문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조ex) 검색에서 사용하는 자동완성 기능을 만들 때 사용하는 알고리즘검색어 자동완성, 사전 찾기 등에 사용한다.L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.각 정점이 자식에

정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘O(log N)만큼 시간복잡도가 걸린다.ex) Up & Down 게임반드시 정렬이 되어있어야 사용할 수 있다.배열 혹은 이진 트리를 이용하여 구현가능하다.시간복잡도가 O(log N)인 만큼 상당 빠르다.배열 중간 값을

BFS (너비 우선 탐색) 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 노드부터 탐색하는 알고리즘 BFS 특징 Queue를 이용하여 구현 루트 노드부터 가까운 노드부터 탐색 V가 정점의 수, E가 간선의 수 일때 BFS의 시간복잡도는 O(V+E) DFS (깊이 우

모든 경우의 수를 탐색하는 알고리즘DFS나 BFS이용효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기라고 한다.자바스크립트는 재귀 효율이 안좋다. 때문에 DFS일 경우 Stack을 이용하는 것이 좋다.순환(Cycle)이 발생할 수 있다면 BFS를 이용하는

해결한 작은 문제로 큰 문제를 해결하는 방식Dynamic Programming(DP)라고도 부른다.메모리를 사용하는 대신 빠른 성능을 자랑한다.두 가지 방법론메모이제이션타뷸레이션하향식 접근법동적 계획법에서 작은 문제들의 결과는 항상 같다.따라서 이 결과들을 메모리에 저