[16일차]
[위상 정렬] Topology Sort
: 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘.
*위상 정렬에서는 항상 유일한 값으로 정렬되지 않음. 사이클이 존재하면 노드 간 순서를 명확히 정의하지 못하기 때문에 위상 정렬 적용 못 함.
→ 예를 들어 '수강신청 선수과목' 등 A를 해야 B를 할 수 있는 조건이 있을 때 그 순서를 찾아내기 위해 사용함.
- 어디에 적용?
- 백엔드에서 Spring 프레임워크의 의존성 주입(DI) 부분에 여러 객체 중 어떤 객체를 먼저 메모리에 올려야 에러가 나지 않는지 계산할 때 위상 정렬이 사용됨.
- 컴퓨터 비전에서 PyTorch나 TenserFlow 같은 딥러닝 프레임워크를 쓸 때,
입력 이미지 전처리 - 합성곱 레이어 - 활성화 함수 - 풀링 등의 연산 순서를 스케줄링하고 최적화하는 로직이 위상 정렬 기반!!
- 핵심 원리는?
진입 차수(indegree) : 나를 향해 들어오는 화살표의 개수. → 내가 실행되기 위해 먼저 끝나야 하는 선행 작업의 개수를 의미.
- 인접 리스트를 구현해서 각 노드 별 도착 노드를 지정해준다.
진입 차수 배열도 추가로 생성 해야하며 배열의 크기는 노드 갯수보다 +1 크게하여 각 인덱스에 차수를 저장할 수 있도록 함.
*포인트는 인접 리스트 생성과 함께 진입 차수도 모두 셋팅해둬야 함. - 진입 차수가 0이 된 노드. 즉, 현재 가장 우선이 되는 노드부터 큐에 offer한다. (큐는 위상 정렬을 위한 배열. 들어가는 순서)
큐에서 데이터를 poll하여 해당 노드를 탐색 결과에 추가한다.
그 후, 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. - 계속해서 다음 진입 차수가 0인 노드를 선택하여 큐에 offer 하고 다음 노드의 진입 차수를 1 뺀다. (반복)
*여기서 진입 차수가 0인 노드가 1개보다 많을 수가 있는데, 이 때는 어느 노드를 먼저 선택하는지에 따라 정렬 결과가 달라질 수 있다.
문제에서 결과가 여러가지일 경우 아무 답이나 출력한다. 라는 말이 있을 경우 이에 해당 !!!
- 예제 문제
- 백준 2252번 : 줄 세우기 (골드 3)
package study.week4.day16; import java.util.*; import java.io.*; public class P2252 { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); // N : 학생 수 int M = Integer.parseInt(st.nextToken()); // M : 키를 비교한 횟수 ArrayList<Integer>[] A = new ArrayList[N + 1]; // 인접 리스트 생성 int[] indegree = new int[N + 1]; // 진입 차수 배열 생성 for (int i = 1; i <= N; i++) { A[i] = new ArrayList<>(); // 리스트 초기화 : 객체 생성 } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); // 토크나이저 다시 생성해서 엣지 입력 받음 int S = Integer.parseInt(st.nextToken()); // S : Start 시작 노드 의미 int E = Integer.parseInt(st.nextToken()); // E : End 도착 노드 의미 A[S].add(E); // S 시작노드에 E 도착노드 추가 → 인접 리스트 구현 indegree[E]++; // 도착 노드의 진입 차수 1 증가. } Queue<Integer> queue = new LinkedList<>(); // 위상 정렬 큐 대기열 생성하기 for (int i = 1; i <= N; i++) { // 1번 노드부터 순회 N번 노드까지. if (indegree[i] == 0){ // 순회 중, 해당 노드의 진입 차수가 0일 때 queue.offer(i); // 위상 정렬 큐에 추가하기! } } StringBuilder sb = new StringBuilder(); // 최종 출력할 결과 쌓을 빌더 생성 while (!queue.isEmpty()) { // 큐가 빌 때까지 반복 int cur_node = queue.poll(); // cur_node는 대기열 큐에서 꺼낸 노드 : 출력할 결과 sb.append(cur_node).append(" "); // 빌더에 방금 꺼낸 노드 저장 후 띄어쓰기 추가 for (int next : A[cur_node]) { // 현재 노드의 다음 노드들을 순회 indegree[next]--; // 다음 노드들의 진입 차수 1씩 감소 if (indegree[next] == 0) // 다음 노드의 진입 차수가 0이라면, queue.offer(next); // 대기열 큐에 다음 노드 추가 (offer) } } System.out.println(sb.toString()); // 최종 위상 정렬된 결과 출력 } } - 백준 1516번 : 게임 개발하기 (골드 3)
- 백준 1948번 : 임계 경로 구하기 (플래티넘)
*지금 파이썬으로 코테 풀다가 자바로 넘어오니까 큐 offer, poll이 헷갈린다.. push/pop ↔ offer/poll 익숙해지기!!!
[17일차]
[다익스트라] Dijkstra
: 그래프에서 최단 거리를 구하는 알고리즘
출발 노드와 모든 노드 간의 최단 거리를 탐색하여 최종 목적지까지의 최단 경로를 찾는다. 이때 엣지의 가중치(비용)은 모두 양수.
실제 배열에서는 모든 노드 간의 최단 거리를 표현함. 이렇게 되면 원하는 목적지를 선택했을 때 항상 최단 거리를 구할 수 있게 됨.
- 시간 복잡도 : O(ElogV)
*다익스트라는 일반 큐가 아닌 우선순위 큐(Priority Queue)를 사용한다.
→ 힙 자료구조 사용해서 최솟값을 우선적으로 뽑음 O(logN) 소요.
우리가 우선순위 큐에 넣을 건 Node 클래스이기 때문에 (도착 노드, 가중치) 이 두 개중에 어떤 걸 기준으로 정렬할 지 정해줘야 함.
*여기서 우리가 앞에서 배운 정렬 사용! Comparable의 compareTo 메서드
(도착 노드, 가중치) 중에서 우리는 최단 거리(최소 비용)을 찾는 거니까 가중치(weight)를 기준으로 정렬해주면 됨.
Ex)
public int compareTo(Node o) {
return this.weight - o.weight;
}
- 핵심 원리는?
- 마찬가지로 그래프를 인접 리스트로 구현한다. 이 때는 가중치가 존재하기 때문에 (도착, 가중치) 형태로 저장
- 최단 거리를 저장하는 배열을 하나 생성한다. 출발 노드는 0으로, 이외 노드는 모두 무한(큰 값)으로 초기화한다.
*큰 값 : 사용되는 가중치보다는 충분히 클 정도의 적당한 수. 예로 99,999,999 정도? - 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 값이 0인 출발 노드부터 시작.
우선 순위 큐에 출발 노드를 넣고, 경로 탐색을 시작. - 큐에서 노드 하나 뽑고 방문 유효성 검사 수행 (방문했던 노드 다시 방문하는 것 방지. 방문했다면 다음 노드 탐색)
현재 노드를 방문 노드로 업데이트하고, 현재 선택된 노드부터 다음 노드들까지 비용을 비교하며 최단 거리 갱신
*다음 노드가 방문하기 전 노드이면서, (현재 노드까지의 최단 거리 + 다음 노드까지 비용)이 최단 거리 배열의 다음 노드 값보다 작다면 비용 갱신! 갱신 후엔 다음 노드를 우선순위 큐에 삽입. - 큐가 빌 때까지 위 동작 반복하여 모든 노드 방문할 때까지 수행.
#이러한 다익스트라 알고리즘의 장점은 모든 노드를 순회하되, 그 노드로 가는 모든 경로들을 순회하지 않고 효율적인 경로만 탐색.
- 예제 문제
- 백준 1753번 : 최단 경로 구하기 (골드 5)
package study.week4.day17; import java.io.*; import java.util.*; class Node implements Comparable<Node> { int end_node; // 도착 노드 int weight; // 가중치(비용) public Node(int end_node, int weight) { this.end_node = end_node; this.weight = weight; } @Override public int compareTo(Node o) { // 가중치 기준으로 오름차순 정렬하도록 return this.weight - o.weight; // 내 가중치(거리)에서 남의 거리 뺐을 때 음수면 내가 더 작다는 뜻 } } public class P1753 { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int V = Integer.parseInt(st.nextToken()); // V : 노드 갯수 int E = Integer.parseInt(st.nextToken()); // E : 엣지 갯수 int K = Integer.parseInt(br.readLine()); // K : 출발 노드 ArrayList<Node>[] A = new ArrayList[V + 1]; // 인접 리스트 생성 및 초기화 for (int i = 1; i <= V; i++) { A[i] = new ArrayList<>(); } for (int i = 0; i < E; i++) { // 엣지 갯수만큼 그래프 정보 저장 st = new StringTokenizer(br.readLine()); int start_node = Integer.parseInt(st.nextToken()); // 시작 노드 int end_node = Integer.parseInt(st.nextToken()); // 도착 노드 int weight = Integer.parseInt(st.nextToken()); // 시작 → 도착 까지의 가중치(비용) A[start_node].add(new Node(end_node, weight)); // 인접 리스트에 노드 정보 추가 } int[] distance = new int[V + 1]; // 최단 거리 배열 생성 boolean[] visited = new boolean[V + 1]; // 방문한 노드인지 체크할 목록 for (int i = 0; i <= V; i++) { distance[i] = Integer.MAX_VALUE; // 초기 값은 모두 무한대로 설정! } PriorityQueue<Node> Q = new PriorityQueue<>(); // 우선순위 큐 생성 distance[K] = 0; // 최단 거리 배열의 시작 노드인 K는 0으로 설정. Q.offer(new Node(K, 0)); // 큐에 (출발 노드, 거리 0)을 삽입 while (!Q.isEmpty()) { Node current = Q.poll(); // 큐에서 거리가 가장 짧은 노드 꺼냄 int cur_node = current.end_node; // 현재 뽑은 노드 if (visited[cur_node]) continue; // 현재 노드가 방문했던 적이 있는 노드라면 건너뜀 visited[cur_node] = true; // 현재 노드를 방문했다고 도장 찍기! for (Node next : A[cur_node]) { // 현재 노드와 연결된 다음 노드들을 순회 int next_node = next.end_node; // 다음 노드를 선택 : next_node int weight = next.weight; // 다음 노드까지의 가중치 : weight // 현재 노드까지의 비용과 다음 노드까지의 가중치의 합이, 최단 거리 배열의 다음 노드 값보다 작다면 if (distance[cur_node] + weight < distance[next_node]) { distance[next_node] = distance[cur_node] + weight; // 최단 거리를 새로 갱신 Q.offer(new Node(next_node, distance[next_node])); // 큐에 다음 노드와 그 노드까지의 최단거리 저장하여 추가 } } } for (int i = 1; i <= V; i++) { // 시작점부터 모든 노드 순회 if (visited[i]) { // 방문했던 적이 있는 노드라면? System.out.println(distance[i]); // 해당 노드까지의 최단 거리 출력 } else { // 방문한 적 없다면? System.out.println("INF"); // 무한대 값(INF) 출력 : 갱신을 안 했으니까. } } } } - 백준 1916번 : 최소 비용 구하기 (골드 5)
package study.week4.day17.P1916; import java.io.*; import java.util.*; class Node implements Comparable<Node> { int end_node; int weight; public Node(int end_node, int weight) { this.end_node = end_node; this.weight = weight; } @Override public int compareTo(Node o) { return this.weight - o.weight; } } public class P1916 { // P1916 클래스에서 사용 가능하도록 static으로 선언. static int N, M; static ArrayList<Node>[] list; static int[] dist; static boolean[] visited; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; N = Integer.parseInt(br.readLine()); // N : 도시의 개수 (노드) M = Integer.parseInt(br.readLine()); // M : 버스의 개수 (엣지) // N개의 노드가 있고 M개의 엣지가 있다는 뜻 list = new ArrayList[N + 1]; dist = new int[N + 1]; visited = new boolean[N + 1]; Arrays.fill(dist, Integer.MAX_VALUE); // 아래와 동일한 작업으로 dist 함수로 축약 가능 !!! 미세하게 성능상 유리하다 하네 // for (int i = 0; i <= N; i++) { // dist[i] = Integer.MAX_VALUE; // } for (int i = 0; i <= N; i++) { list[i] = new ArrayList<Node>(); } for (int i = 0; i < M; i++) { // 노드 정보 인접 리스트에 추가 st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); // 시작 노드 int end = Integer.parseInt(st.nextToken()); // 도착 노드 int weight = Integer.parseInt(st.nextToken()); // 가중치(비용) list[start].add(new Node(end, weight)); // 인접 리스트에 추가 } st = new StringTokenizer(br.readLine()); int start_city = Integer.parseInt(st.nextToken()); // 출발 도시 int end_city = Integer.parseInt(st.nextToken()); // 도착 도시 bw.write(dijkstra(start_city, end_city) + "\n");// 출발 - 도착 도시까지 최소 비용 버퍼에 입력 bw.flush(); // bw 버퍼의 내용 모두 출력 bw.close(); // bw 버퍼 닫기 br.close(); // br 버퍼 닫기 } public static int dijkstra(int start_city, int end_city) { PriorityQueue<Node> Q = new PriorityQueue<>(); // 우선순위 큐 생성 Q.offer(new Node(start_city, 0)); // 시작 노드 큐에 삽입 dist[start_city] = 0; // 최단 거리 배열의 시작 노드 값은 0으로 while (!Q.isEmpty()) { Node current = Q.poll(); // 큐에서 최단 거리인 노드 뽑기 int cur_node = current.end_node; // 해당 노드를 현재 노드로 지정 if (cur_node == end_city) { // 현재 노드가 도착 도시 노드라면? return dist[end_city]; // 바로 도착 도시까지 최단 거리 반환해서 조기 종료하기! } if (visited[cur_node]) continue; // 현재 노드가 방문했던 노드면 건너뜀 visited[cur_node] = true; // 아니라면 방문 도장 찍기 for (Node end : list[cur_node]) { // 현재 노드와 연결된 다음 노드들 순회 // ※ 여기서 헷갈렸던 부분 : list[cur_node]는 인접 리스트에서 [cur_node]와 연결된 노드들 정보 가져옴 // 즉, 1이면 (2번 노드, 3), (3번 노드, 8) 이런 식으로 노드 클래스를 가져옴 // 여기서 기존에 Node next로 변수명을 지었는데 이게 약간 헷갈릴 수 있음! next - end로 변경 int end_node = end.end_node; // 이건 현재 노드의 다음 도착 노드 번호를 의미 int weight = end.weight; // 이건 도착 노드까지 걸리는 비용(가중치) 의미 // 즉 현재 출발 노드까지의 비용과 도착 노드까지의 가중치를 더한 값이, 최단 거리 배열에 저장된 도착 노드 값보다 작으면 if (dist[cur_node] + weight < dist[end_node]) { dist[end_node] = dist[cur_node] + weight; // 최단 거리 갱신 Q.add(new Node(end_node, dist[end_node])); // 방금 그 도착 노드와 가중치를 큐에 삽입 } } } return dist[end_city]; } }
[18일차]
[벨만-포드]
: 그래프에서 최단 거리를 구하는 알고리즘
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색.
*다익스트라와의 차이점은 음수 가중치 엣지가 있어도 수행 가능하다. 전체 그래프에서 음수 사이클의 존재 여부를 판단 가능하다.
- 시간 복잡도 : O(VE) V는 노드 수, E는 엣지 수
#사이클은 존재해도 됨! 양수 사이클까지는 괜찮은데, 음수 사이클이 존재하면 안됨.
- 핵심 원리는?
: 엣지를 중심으로 동작한다. (다익스트라는 노드 중심)
- 입력된 엣지들로 엣지 리스트를 만든다. (입력 순서는 노드 순서대로가 아닐 수 있음)
- 엣지 리스트가 정렬되지 않았을 수 있기 때문에, 노드 갯수 - 1번 만큼 (V - 1) 엣지 리스트를 돌면서 최단 거리 맵을 갱신한다.
- V - 1번 만큼 반복한 뒤 음수 사이클 확인을 위해 검증용으로 1번 더 리스트를 돈다.
- 여기서 최단 거리 맵에서 거리 비용이 감소하는 부분이 있다면 음수 사이클이 존재한다는 뜻.
- 어디에 적용?
- 금융권에서 차익 거래에 사용 (Arbitrage)
: 예로, 100달러 → 엔화 → 원화 → 다시 달러로 환전했을 때, 105달러가 돼서 돌아오는 순간이 존재한다.
알고리즘 관점에서 이건 한 바퀴 돌았을 때 비용이 깎이는 음수 사이클이다. (방금 우리가 얘기했던!)
이제 전 세계 환율 데이터를 그래프로 만들어서 벨만-포드 돌린 다음 음수 사이클 발생 순간에 자동 매매 돌린대.# 이건 좀 대박인 듯. 나중에 이거 관련 자동 매매 앱 만들어봐도 좋을듯 ㅎㅎ불가능입니다. - 네트워크 인터넷 공유기 (거리 벡터 라우팅, RIP/BGP)
: 이거는 뭐 컴퓨터공학 전공자였다면 한번쯤은 들어봤을 거리 벡터 라우팅이다.
전국의 여러 수많은 공유기들이 서로 라우팅 테이블을 교환하면서 어느 쪽으로 데이터를 전송해서 전달할 지를 교환하며 트래픽을 관리한다.
근데 이 부분은 약간 다른 게, 공유기가 다른 전국의 공유기들까지의 세부 경를 저장하고 있는 게 아니라, 인접한 공유기들과 라우팅 테이블을(엣지 리스트) 전달함으로써 내가 원하는 목적지까지의 최단 거리를 갱신한다고 보면 됨.
즉, 인접한 애들이 주는 정보만을 통해 갱신하고, 인접한 애들은 또 걔네의 인접한 애들 ... 뭐 이렇게 타고타고 전국/전 세계까지 퍼져나가서 먼 거리의 공유기까지의 거리도 구할 수 있다는 것.
- 예제 문제
- 백준 11657번 : 타임머신으로 빨리 가기 (골드 4)
package study.week4.day18.P11657; import java.util.*; import java.io.*; public class P11657 { private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int N, M; static long distance[]; static Edge edges[]; public static void main(String args[]) throws IOException { StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); edges = new Edge[M + 1]; distance = new long[M + 1]; Arrays.fill(distance, Integer.MAX_VALUE); for (int i = 0; i<M; i++) { st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); // 시작 도시 int end = Integer.parseInt(st.nextToken()); // 도착 도시 int time = Integer.parseInt(st.nextToken()); // 이동 시간 edges[i] = new Edge(start, end, time); // 엣지 리스트에 저장 } distance[1] = 0; for (int i = 1; i<N; i++) { // 노드 수 - 1번 만큼 루프 for (int j = 0; j<M; j++) { // 엣지 리스트의 엣지들을 순회 Edge edge = edges[j]; if (distance[edge.start] != Integer.MAX_VALUE && // 시작 노드의 거리가 무한이 아니면서, distance[edge.end] > distance[edge.start] + edge.time) { // 거리 배열[도착노드] 거리 > 거리 배열[시작 노드] + 시작 노드 → 도착 노드에 소요되는 시간 이라면? distance[edge.end] = distance[edge.start] + edge.time; // 거리 배열 갱신 } } } boolean minusCycle = false; for (int i = 0; i<M; i++) { // 음수 사이클 찾기 위해 마지막으로 한 번 더 루프 돌기 Edge edge = edges[i]; if (distance[edge.start] != Integer.MAX_VALUE && distance[edge.end] > distance[edge.start] + edge.time) { minusCycle = true; } } if (!minusCycle) { // 음수 사이클이 없다면? for (int i = 2; i<=N; i++) { // 2번 노드부터 끝까지 if (distance[i] == Integer.MAX_VALUE) // 해당 거리 배열이 무한 값이면 System.out.println("-1"); // -1 출력 else System.out.println(distance[i]); // 아니면 해당 거리 배열 값 출력 (최단 시간) } } else { // 음수 사이클이면 System.out.println("-1"); // -1 출력 } } } class Edge { int start, end, time; Edge(int start, int end, int time) { this.start = start; this.end = end; this.time = time; } } - 백준 1219번 : 세일즈맨의 고민 (골드 2)
[플로이드-워셜]
: 그래프에서 최단 거리 구하는 알고리즘
모든 노드 간 최단 경로 탐색
음수 가중치 엣지가 있어도 수행 가능. *동적 계획법 원리를 이용해 알고리즘 접근
시간 복잡도 : O(V^3). V는 노드 수
- 핵심 이론?
플로이드-워셜 점화식 : D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
- 배열 선언 후 초기화하기
D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열이라 정의.
S와 E의 값이 같은 칸은 0, 다른 칸은 무한값으로 초기화. - 최단 거리 배열에 그래프 데이터 저장하기
출발 노드는 S, 도착 노드는 E, 에지의 가중치는 W라고 했을 때, D[S][E] = W로 엣지 정보를 배열에 입력.
→ 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현함! - 점화식으로 배열 업데이트하기
구했던 점화식을 3중 for문 형태로 반복하며 배열 값 업데이트.
그냥 싸그리 모든 경우 다 돌아서 시간 복잡도 최악.
* 플로이드-워셜 알고리즘 사용하는 문제는 일반적으로 노드 개수의 범위가 다른 그래프에 비해 적게 나타나는 걸 알 수 있음.!!!
- 예제 문제
1. 백준 11404번 : 가장 빠른 버스 노선 구하기 (골드 4)
2. 백준 11403번 : 경로 찾기 (실버 1)
3. 백준 1389번 : 케빈 베이컨의 6단계 법칙 (실버 1)
[19일차]
[최소 신장 트리]
: 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치 합을 최소로 하는 트리.
- 사이클이 포함되면 가중치 합이 최소가 될 수 없으므로 사이클을 포함하지 않음.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 갯수는 항상 N - 1개.
- 핵심 이론?
- 엣지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기
데이터를 노드가 아닌 엣지 중심으로 저장(엣지 리스트). 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화. - 그래프 데이터를 가중치 기준으로 정렬하기 (오름차순)
- 가중치가 낮은 엣지부터 연결 시도하기
가중치 낮은 엣지부터 순서대로 선택해 연결 시도하는데, 이때 바로 연결하지 않고 엣지를 연결했을 때 그래프에 사이클 형성되는지 여부를 find 연산을 이용해 확인한 후에 생성되지 않을 때만 union 연산 이용해 두 노드를 연결. - 3번 과정 반곡. 엣지 갯수 N-1이 될 때까지.
- 총 엣지 비용 출력하기
엣지 개수 N - 1이 되면 알고리즘 종료. 최소 신장 트리의 총 엣지 비용 출력.
- 예제 문제
- 백준 1197번 : 최소 신장 트리 구하기 (골드 4)
- 백준 17472번 : 다리 만들기 (골드 1)
- 백준 1414번 : 불우이웃돕기 (골드 1)
[20일차]
[트리]
: 노드와 엣지로 연결된 그래프의 특수한 형태.
- 순환 구조를 지니고 있지 않고(사이클 x), 1개의 루트 노드가 존재.
- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐.
- 트리의 부분 트리 역시 트리의 모든 특징을 따름.
- 핵심 이론?
| 구성 요소 | 설명 |
| 노드 | 데이터의 index와 value를 표현하는 요소 |
| 엣지 | 노드와 노드의 연결 관계를 나타내는 선 |
| 루트 노드 | 트리에서 가장 상위에 존재하는 노드 |
| 부모 노드 | 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 |
| 자식 노드 | 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 |
| 리프 노드 | 트리에서 가장 하위에 존재하는 노드(자식 노드 없는 노드) |
| 서브 트리 | 전체 트리에 속한 작은 트리 |
- 예제 문제
- 백준 11725번 : 트리의 부모 찾기 (실버 2)
- 백준 1068번 리프 노드의 개수 구하기 (실버 1)
[트라이]
: 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조.
- N진 트리 : 문자 종류의 개수에 따라 N이 결정. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성.
- 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지.
* 기본적으로 트라이의 모든 노드는 N개의 공백 노드를 자식 노드로 가짐. (알파벳의 경우 26개)
- 예제 문제
- 백준 14425번 : 문자열 찾기 (실버 3)
4주차 내용 요약
- 위상 정렬 : 사이클이 없는 방향에서 노드의 순서를 찾는 알고리즘. 약간 노드 간 계층적인 관계라고 보면 이해 쉬울 듯?
- 다익스트라 : 최단 경로 알고리즘으로서. 가중치가 음수가 없는 양수로만 된 그래프에서 가장 빠르게 최단 경로를 찾을 수 있음
- 벨만-포드 : 마찬가지로 최단 경로 알고리즘. 이건 가중치가 음수인 그래프에서도 가능.
- 플로이드-워셜 : 이것도 최단 경로인데, 음수 가중치 있어도 가능하고, 동적 계획법 원리 기반 구현됨. 속도는 아주 늦음 O(N^3)
- 최소 신장 트리 : 한 마디로 그래프의 모든 노드를 사이클 없이 싹 다 연결 한 것. 그러고 이 중에 최소 비용 드는 루트.
주간 회고록
- 트리 부분에 좀 약한 것 같아 트리 부분 중점적으로 이해해야할 듯.
- 최단 경로 중에 다익스트라가 좀 중요하니, 이건 완벽하게 외운단 생각으로 ㄱㄱㄱ
- 문제를 많이 못 풀고 있음. 문제 풀이 시간 비중 높여
'Etc > 알코테 스터디' 카테고리의 다른 글
| [Do it! 알고리즘 코딩 테스트 자바] 6주차 기록. 동적 계획법(DP) (1) | 2026.04.05 |
|---|---|
| [Do it! 알고리즘 코딩 테스트 자바] 5주차 기록 (0) | 2026.03.30 |
| [Do it! 알고리즘 코딩 테스트 자바] 3주차 기록 (1) | 2026.03.15 |
| [Do it! 알고리즘 코딩 테스트 자바] 2주차. 정렬과 탐색 (0) | 2026.03.07 |
| [Do it! 알고리즘 코딩 테스트 자바] 1주차. 시간복잡도와 기초 자료구조 및 알고리즘 (1) | 2026.03.01 |