[Java 자료구조] DFS, BFS 1. DFS(Depth-First Search) 깊이 우선 탐색 스택을 사용 1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 모든 노드가 한번씩 방문되었으면 종료한다. 그래프의 노드 1을 시작 노드로 설정하여 DFS를 이용해 탐색 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다. 방문 처리된 노드는 회색으로, 현재 처리중인 스택의 최상단 노드는 하늘색으로 표현한다. step1. 시작 노드 '1'을 스택에 삽입하고 방문 처리 step2. 스택의 최상단 ..
우선순위 큐 Java에서 우선순위 대기열을 구현하려면 우선순위 대기열 데이터 구조의 내장 구현인 java.util.PriorityQueue 클래스를 사용할 수 있습니다. PriorityQueue 클래스는 Java Collections Framework의 일부이며 우선순위 큐의 힙 기반 구현을 제공합니다. import java.util.PriorityQueue; import java.util.Comparator; 우선 순위 대기열은 자연 순서(Comparable 인터페이스를 구현하는 경우) 또는 사용자 정의 비교기를 사용하여 요소를 정렬합니다. 사용자 지정 주문을 정의하려면 Comparator 구현을 만들어야 합니다. 우선 순위 대기열에 저장하려는 요소가 사용자 정의 클래스인 경우 해당 클래스에서 Comp..
04: 큐, 덱 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는..
01: 연결리스트 1. 연결리스트란? 연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다. Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다. 그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이..
01: 배열과 문자열 1. 해시테이블 연결리스트와 해시 코드 함수를 활용한다. 1. 키의 해시코드를 계산한다. 배열의 인덱스 구하기 -> hash(key) % array_length 키의 개수는 무한하지만 자료형의 개수는 유한하므로 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다. 2. 인덱스마다 키와 값으로 이루어진 연결리스트가 저장된다. 위와 같은 충돌 사항에 대해 방지하기 위함이다. 3. 키에 상응하는 값 찾는 과정 해시코드로 인덱스를 계산 -> 키에 상응하는 값을 연결리스트에서 탐색 2. ArrayList와 가변 크기 배열 자바의 경우 Array배열은 길이가 고정되어 있으므로 선언시에 크기를 함께 지정해야 한다. String[] arr1 = new String[5]; int[] arr2..
