Algorithms/study log

[java] 트리와 DFS

백준 11725: 트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제를 해결하기 위해서 사용할 것 ✅트리 데이터를 저장할 인접 리스트 visited ✅ 방문 기록 저장 배열 tree ✅ 부모 노드 저장 정답 배열 parent import java.io.*; import java.util.*; //무엇이 필요한가 //트리 데이터를 저장할 인접 리스트 //방문 기록 저장 배열 //부모 노드 저장 정답 배열 public class tmp { static int n; static boolean[] visited; static ArrayList tree[]; st..

[java] 큐 / 우선순위 큐 / 힙

1. 백준 1655: 가운데를 말해요 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net Queue를 사용하여 중앙값을 찾는 방법 중앙값 기점으로 maxPq(Heap) / minPq(Heap) 이용하기 maxPq: 중앙값보다 작은 값 저장 / minPq: 중앙값보다 큰 값 저장 import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException { Buffere..

[java] 플로이드-워셜 알고리즘

플로이드-워셜 알고리즘 ✏️dp(동적계획법)의 개념을 활용한 최단경로 탐색 알고리즘 ✏️ 벨만포드 알고리즘과 마찬가지로 음수 가중치 에지가 있어도 수행이 가능하다. ✏️ 시간복잡도는 O(V^3)으로 느린편이다. 반복문을 노드 개수 V만큼 총 3번 반복하기 때문. 우선 동적계획법의 원리부터 간단히 적어본다. 노드가 1~4까지 4개 있다고 가정했을 때, 1부터 4까지 가는 최단경로가 1→2→4 라고 하자. 이는 1부터 2까지 가는 최단경로와 2부터 4까지 더하는 최단경로의 조합이 된다. Min(1→2) + Min( 2→4) 플로이드 워셜 알고리즘은 이와 유사하게 최단거리를 저장하는 배열을 만들고 dp 원리를 이용하여 값을 업데이트 해준다. 이 배열을 D라고 했을 때 D[Start][End]는 Start에서 ..

[java] 벨만포드 알고리즘

벨만포드 알고리즘 🔑그래프에서 최단거리를 구하는 알고리즘 ✏️음수 가중치 에지가 있어도 수행이 가능하며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 시간 복잡도: O(VE) 1. 에지 리스트로 그래프 구현> 최단 경로 배열 초기화 tip) 자바의 경우, Arrays.fill을 사용하면 빠르다. static final int INF = Integer.MAX_VALUE; Arrays.fill(arr, INF); 2. 모든 에지를 확인하면서 정답 배열을 업데이트 해준다. 노드 개수가 N이라고 가정할 때, 최단거리 배열에서 업데이트 반복 횟수는 N-1번이다. N개의 노드가 있고 음수 사이클이 없을 때 최단 경로를 구성하는 엣지의 개수는 최대 N-1개가 된다. (N개가 될 수가 없다) ✏️업데이트..

[java] 다익스트라 알고리즘

다익스트라 ✨start 노드와 모든 노드간 거리 탐색, 최단거리를 저장하는 배열 dist[] ✨edge는 모두 양수 ✨시간복잡도 O(ElogV) 🪄시간초과를 대비하여 되도록이면 buffer를 사용하도록 하자 1. 인접리스트로 그래프 구현 2. 최단거리 배열 초기화 3. 값이 가장 작은 노드 고르기 4. 최단거리 배열 업데이트 Min(현재 선택한 노드의 최단거리 배열 값+가중치, 연결 노드의 최단거리 배열 값) 한번 선택된(방문한) 노드는 다시 선택되지 않도록 체크하는 배열이 필요: check[] 백준 1753 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고..

[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 😓Arrays.sort 사용하는 방법 - 지양하기 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea..