개발 무지렁이

트리의 부모 찾기 🪅 에지리스트를 인접리스트로 구현할 수 있는가 🪅 인접리스트를 루트부터 탐색해가며 parent배열을 완성할 수 있는가 🪅 DFS를 구현할 수 있는가 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class Main { static List[] tree; static boolean[] isVisited; static int[] parent; public static..

트리 🪅 parent배열을 보고 인접리스트를 구현할 수 있는가 (루트노드 지정) 🪅 트리를 인접리스트로 구현할 수 있는가 🪅 트리의 일부분을 잘라낼 수 있는가 => remove(int index)와 remove(Object obj)의 차이를 알고 있는가 🪅 Leaf Node의 특징을 알고 있는가 => tree[node].size() == 0 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; /** * 백준 1068번 트리 * 입력: * 첫째..

ABCDE 🪅 에지리스트를 인접리스트로 구현할 수 있는가 🪅 반복동작을 수행할때마다 전의 동작이 다음 동작에 영향을 미치지 않도록 초기화해 주었는가 🪅 flag 변수를 용도에 맞게 사용할 수 있는가 🪅 모든 경로 탐색에 필요한 백트래킹을 할 줄 아는가 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; /** * 백준 13023번 ABCDE * * 입력: * 첫째 줄에 사람의 수 N (5 ≤ N ≤..

최단거리를 구하는 다익스트라(Dijkstra) 알고리즘 시작노드와 나머지 노드 간의 최단거리를 탐색하는 알고리즘을 다익스트라 알고리즘이라고 한다. (단, 이때 엣지가 모두 양수여야한다.) 🕑 시간복잡도: O(V^2) (V:노드수, E:간선수) [ O(ElogV): 우선순위 큐 이용시 ] 다익스트라(Dijkstra)와 우선순위 큐(Priority Queue) 다익스트라 알고리즘은 '우선순위 큐(Priority Queue)'로 구현하며, '우선순위 큐(Priority Queue)'란 데이터가 새롭게 들어올 때마다 '자동으로 정렬'하는 큐를 말한다. 정렬 기준은 Node클래스의 'compareTo() 함수'를 통해 설정할 수 있다.다익스트라(Dijkst..

그래프의 모든 노드를 탐색하는 BFS(Breadth First Search) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 시작노드에서 출발하여 레벨 기준으로 자기 레벨을 다 탐색하고 내려가는 과정을 반복하는 것을 ' 넓이우선탐색(BFS) '라고 한다. ** (시작노드 기준으로 가까운 노드를 먼저, 최단경로를 보장) ** 🕑 시간복잡도: O(V+E) (V:정점수, E:간선수) [모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니] BFS와 큐 BFS는 큐(Queue)로 구현하며, 큐(Queue)란 먼저 들어온게 먼저 빠지는 형태의 자료구조(FIFO)를 말한다 Queue queue = new ArrayDeque(); BFS 코드 구현 ⚠️ 한번 방문한 노드..

그래프의 모든 노드를 탐색하는 DFS(Depth First Search) 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 시작노드에서 출발하여 리프노드까지 내려가고 부모에게 올라가, 다시 리프노드까지 내려가는 것을 반복하는 과정을 ' 깊이우선탐색(DFS) '라고 한다. 🕑 시간복잡도: O(V + E) (V: 노드 수, E: 간선 수) [모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니] DFS와 재귀함수 DFS는 재귀함수로 구현하며, 재귀함수란 '자기 자신'을 Function call(함수 호출)하여 동작하는 방식을 말한다. (종료조건과 재귀적확장이 있어야 한다.)DFS 코드 구현, 백준 1260 DFS 🪅 에지리스트를 인접리스트로 구현할 수 있는가 🪅 ..