나 JAVA 봐라

DFS / 백트래킹 이 두가지가 항상 함께 등장하는데, 어떤 차이가 있는지 몰라 정리해보았다. 쉽게 이야기 하자면 끝까지 가는지(DFS)/ 돌아오는지(백트래킹) 의 차이이다. 그래서, DFS 탐색하며 조건을 확인하며 해당 노드가 유망하지 않으면 탐색하지 않는 것 = 백트래킹 이다. 백트래킹도 일반적으로 재귀 형태로 작성되며 크게 3개의 내용을 작성한다. 재귀를 진행하는 동안 사용될 깊이(depth)를 매개변수로 넣기 재귀가 종료될 때 수행할 내용 재귀 종료조건 = 보통 정해진 depth에 도달했을 때 dfs 함수의 제일 앞에서 종료 조건에 포함되었는지 먼저 검사한다. 재귀가 진행 중이면 가지치기(백트래킹)할 내용 백트래킹으로 조합하는 함수를 구현하면 아래와 같다. public static void com..

BFS (Breadth Fisrt Search) 너비 우선 탐색 이라고 부른다. 가까운 노드부터 우선적으로 탐색하기 때문에 넓게 탐색해서 너비 우선 탐색이다. Queue 자료구조를 사용하여 구현할 수 있다. 탐색 방식 루트 노드 (혹은 다른 임의의 노드) 에서 시작하여 인접한 노드를 먼저 탐색한다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. ex) 미로 탐색 (최단 거리) 특징 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. (거리 1 탐색 후, 2,3,4 순서로 탐색) 그래프 탐색의 경우, 어떤 노드를 방문했었는지의 여부를 반드시 검사해야한다. 그래서 노드를 큐에 담을 때에는 꼭 방문처리를 한 후에 담는다. 방문 여부를 체크하지 않으면 무..

문득 JVM의 힙과 자료구조의 힙이 왜 이름이 똑같을까? 하는 궁금증이 생겼다가 자료구조 힙에 대한 개념을 다 잊어버려서 정리한다. 힙이란? 힙 : 데이터에서 최대값, 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙은 언제, 왜 사용해? 힙은 최대값, 최소값을 빠르게 찾기 위해 사용된다. 배열의 경우 최대값, 최소값을 찾는데 $O(n)$ 이 걸린다. 힙의 경우 최대값, 최소값을 찾는데 $O(logn$) 이 걸린다. => 따라서 최대값, 최소값을 찾기 위해 '힙' 을 사용한다. 우선순위 큐와 같이 최대값, 최소값을 빠르게 찾아야하는 자료구조, 알고리즘 구현에 활용된다. 즉, '힙' ..