DFS(깊이우선탐색)이란? 그래프 탐색 알고리즘 중 하나로 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 현재 정점에서 아직 방문하지 않은 인접 정점들을 하나씩 탐색, 더 이상 탐색할 곳이 없다면 이전 상태로 되돌아가는 탐색방법 DFS의 구현은 스택 또는 재귀 호출을 이용한다. DFS는 그래프의 모든 정점을 확인하기 때문에 한정 조건이 있는 문제에서는 비효율적이다. 깊이 제한을 두어 조건이 만족하지 않는 경우를 무시하고 경우를 구하는 알고리즘인 백트래킹(backtracking) 사용 DFS 구현 방법 1. 그래프의 연결 상태를 나타내는 인접 행렬(adj)과 방문한 정점인지 확인하는(visited)배열이 필요하다. 2. 방문한 정점을 True로 체크, 현재 정점과 연결되어있고 방문한적 없는 정..

[ 도입 ] 우선순위 큐 가장 먼저 입력된 자료가 가장 먼저 꺼내지는 큐와 달리 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다. 우선순위 큐의 구현으로 가장 대표적인 것이 바로 힙(heap) 정렬되지 않은 배열or연결리스트에서 삽입 O(1) / 삭제 O(N) 힙에서 삽입 O(logN) / 삭제 O(logN) 힙(Heap)이란? 단순히 최대 원소 or 최소 원소를 찾는 데 최적화된 형태의 완전 이진 트리이다. 가장 큰(작은) 원소는 항상 트리의 루트에 들어가므로 힙은 느슨한 정렬 상태를 유지한다. 부모 노드의 원소는 항상 자식 노드의 원소보다 큰(작은) 값을 가져야 한다. 대소관계는 BST와 달리 부모 자식 관계에만 적용되며 형제 노드가 갖는 원소의 크기는 제한하지 않는다. 중복 값을 허용한다. 마지막 ..