리스트

Java DFS를 이용한 미로 탐색 Java로 DFS(Depth First Search)를 이용하여 간단한 미로 탐색을 구현하는 방법에 대해 알아보겠습니다. 1. 미로의 탐색 위와 같은 미로가 있다고 했을 때 탐색을 위해서는 출발 정점과 도착 정점의 설정이 필요합니다. S를 출발 정점, F를 도착 정점이라고 했을 때 S부터 F까지 도달 가능한 모든 경로를 구하고 이 중에서 최단 경로의 값을 구하는 방법에 대해 알아보겠습니다. 2. DFS를 이용한 미로 탐색 구현 이전에 깊이 우선 탐색(DFS)에 대해서 정리한 내용을 간단히 설명하면, DFS는 출발 정점부터 시작하여 최대한 깊숙히 탐색 후 원점으로 돌아가서 다른 정점을 탐색하는 방식입니다. 미로 탐색에 사용하는 DFS의 조건은 다음과 같습니다. 미로 탐색..

Java DFS(Depth First Search) 구현하기 Java로 DFS(Depth First Search)를 구현하는 방법에 대해 알아보겠습니다. 1. 그래프의 탐색 그래프의 탐색은 하나의 정점으로부터 시작하여 모든 정점을 차례대로 한 번씩 방문하는 것을 의미합니다. 예를 들어 특정 도시에서 다른 도시로의 이동 여부 판별이나 회로에서 단자와 단자의 연결 여부 확인 등에 사용됩니다. 그래프 탐색에서 대중적으로 많이 알려진 알고리즘은 DFS와 BFS가 있는데 이번 포스팅에서는 DFS에 대해서 알아보도록 하겠습니다. 2. 깊이 우선 탐색(DFS, Depth First Search) 깊이 우선 탐색(DFS)는 루트 노드나 임의의 노드에서 시작하여 최대한 깊숙히 들어가서 탐색한 후 다시 원점으로 돌아가 다..

Java로 연결 리스트(Linked List) 구현하기 Java로 연결 리스트(Linked List)를 구현하는 방법에 대해 알아보겠습니다. 1. 연결 리스트(Linked List) 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당합니다. 배열에 비해서 데이터의 추가/삭제가 용이하나, 인덱스가 없는 리스트의 특징으로 인하여 특정 요소에 접근하기 위해서는 순차 탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어집니다. 즉, 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것을 권장합니다. (자바 LinkedList..