대표적인 탐색 알고리즘깊이 우선 탐색그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘모든 노드를 방문하고자 하는 경우에 사용미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른
Key-value쌍으로 데이터를 저장하는 자료구조
일반적인 큐는 선입선출. 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 우선순위 큐는 힙 이라는 자료구조를 이용하여 구현할 수 있다.우선순위가 중간인 것이 삽입 되려고 할 때 삽입 과정에서는 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산처음 최단 거리 테이블은 무한으로 설정출발 노드 설정최단거리 테이블 초기화방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신3,
탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 것결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는것크루스칼 알고리즘은 최적의 해답을 준다.그래프의 간선들을 가중치의 오름차순으로
합치기 찾기 자료구조서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조합집합(union), 찾기(find) 연산을 지원합집합 : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산찾기 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법.가능한 모든 경로를 탐색지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아감DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상
1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는다.시작과 끝을 나타내는 포인터 2개를 준비. => start, end맨 처음에는 start=end=0. 항상 start <= end 만족이 두개의 포인터는
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법.➡ 정점 선택 기반최소 비용의 한붓 그리기시작점을 정하고 시작점에서 가까운 정점을 선택하면서 트리를 구성. 따라서 그 과정에서 사이클을 이루지 않는다.시간복잡도가 O(N^2)이므로 간선의 경우가 많