트리에서 두 노드 사이 유일한 경로를 찾는 방법

1. 문제 30893번: 트리 게임 (acmicpc.net) 30893번: 트리 게임 첫째 줄에 정점의 개수 $N (2≤N≤100,000)$과 말의 시작 정점 $S$, 목표 정점 $E (1≤S, E≤N, S≠E)$가 주어집니다. 다음 $N-1$개의 줄에 걸쳐서 트리의 각 간선이 잇는 두 정점의 번호 $u, v (1≤u, v≤N, u≠v www.acmicpc.net 2. 풀이 트리니까, 출발 정점 S에서 도착 정점 E로 이동하는 경로는 유일하면서 반드시 존재한다. 이때, 선공은 어떻게든 S에서 E로 이동시킬려하고 후공은 E로 어떻게든 못가게 하는게 목적 여기서 한번 방문한 노드는 다시는 방문하지 못하니까, 이동 못하게 방해하는게 가능하다. 핵심은 S에서 E로 가는 경로를 찾아야하는데 DFS를 하면서 이동한..

• format_list_bulleted 알고리즘/DFS BFS 정복기
• · 2023. 12. 5.
• textsms

트리 자료구조에 대한 개념과 트리에서의 다이나믹 프로그래밍 기본기(+트리를 만들지 않고 트리를 탐색하는 방법)

1. 그래프와 트리 그래프(graph)란 정점들과 정점 둘을 잇는 간선들로 이루어진 집합 위는 9개의 정점(원)과 10개의 간선(실선)들로 이루어진 그래프이다. 각 원의 내부에 쓰여 있는 숫자는 편의상 정점에 매긴 번호를 의미한다. 간선(edge)은 항상 두 정점을 잇게 된다. 그래프의 간선에는 가중치가 있을 수 있다. 특별한 언급이 없다면 간선의 가중치는 1로 간주할 수 있다. 가중치가 존재한다면, 예를 들어 1-3 간선의 가중치가 3이라면 1번 정점에서 3번 정점으로 가기 위해선 길이 3인 간선을 지나야한다고 표현한다. 그래프의 간선에는 방향성이 있을 수 있다. 예를 들어 1번 정점과 3번 정점사이 놓인 1-3 간선의 경우 1 > 3 또는 3 > 1 방향성을 가지는 것이 가능하다. 방향성 간선을 갖고..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2023. 11. 29.
• textsms

DFS 2번으로 트리의 지름을 구하는 방법

1. 문제 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 2. 풀이1 트리는 사이클이 없는 무방향 그래프이며, 두 노드 사이 모든 경로가 유일하다. 가장 길이가 긴 경로를 트리의 지름이라고 정의했는데.. 어쨌든 가장 길이가 긴 경로라면 결국 리프 노드와 리프 노드 사이 거리가 가장 길이가 긴 경로이다. 루트 노드가 1번 노드이고 (부모, 자식)으로 입력이 주어지니까 부모 노드 모두 표시해두면 표시가 안된 노드는 어떤 노드의 부모가 아니니까..

• format_list_bulleted 알고리즘/그래프 이론 정복기
• · 2023. 11. 28.
• textsms

최대 유량을 찾는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm) 배우기

1. 유량 네트워크(flow network) A에서 B까지 8명이 지나갈 수 있고, B에서 C까지 3명이 지나갈 수 있다고 해보자. A에서 C까지 1초가 걸린다고 한다면, A에서 B로 8명을 보낼때, 1초 후에 상황은 어떻게 될까 그러면 B에 5명이 대기하고 있고, C에는 3명이 도착해있다. 즉, A에서 B로 8명씩 보내는건 손해라는 의미 A에서 B로 8명씩 보낼 수 있지만, A에서 C까지 막힘없이 데이터를 전송할려면 1초에 3명씩 보내야한다는 소리이다. 위의 그림은 A에서 B로 최대 8명이 갈 수 있는데, 실제로는 3명이 흐르고 있다는 뜻 때때로 네트워크상 특정 지점에서 다른 지점으로 실제로 데이터가 얼마나 흐르고 있는가를 측정하는 것에 관심이 있다. 송유관에서 두 도시 사이 보낼 수 있는 석유의 양,..

• format_list_bulleted 알고리즘/유량 알고리즘
• · 2023. 10. 6.
• textsms

강한 연결 요소(Strongly connected component)를 구하는 코사라주 알고리즘(kosaraju's algorithm) 배우기

1. 강한 연결 요소(strongly connected component) 방향그래프에서 임의의 정점 v1,v2를 골랐을때, 항상 v1과 v2를 서로 오갈 수 있는 경로가 존재한다면, 그러한 방향 그래프를 강한 연결 요소(SCC)라고 부른다. 이 정의에 의하면 무방향 그래프에서는 전체 그래프가 반드시 강한 연결 요소가 되므로 의미가 없다. 즉, 방향 그래프에서만 의미있는 정의가 된다. 아무튼 예를 들어 다음 그래프는 모든 정점 쌍 (v1,v2)에 대하여 서로 오가는 경로가 존재하는 강한 연결 요소이다. 하지만 다음 그래프는.. 2번에서 5번으로는 갈 수 있어도 5번에서 2번으로 올 수는 없다. 그러므로 강한 연결 요소가 아니다. 하지만 그래프를 다음과 같이 적당히 분할하면, 분할된 그룹들 [1,2,3,4..

• format_list_bulleted 알고리즘/그래프 이론 정복기
• · 2023. 9. 2.
• textsms

이분 매칭(Bipartite matching) 알고리즘 배우기

https://justicehui.github.io/hard-algorithm/2018/12/21/BipartiteMatch/ [그래프] Bipartite Matching 이분 매칭이란? 이전 글에서 Max-Flow를 구하는 방법에 대해 알아보았고, 마지막 부분에서는 문제 하나를 풀어보았습니다. icpc.me/11375 문제를 풀어보았고, 문제를 그래프로 모델링하면 아래 사진처 justicehui.github.io 29. 이분 매칭(Bipartite Match.. : 네이버블로그 (naver.com) 29. 이분 매칭(Bipartite Matching) 지난 번에 네트워크 플로우(Network Flow) 알고리즘에 대해 공부하는 시간을 가졌습니다. 이... blog.naver.com Kuhn's Algo..

• format_list_bulleted 알고리즘/이분 매칭
• · 2023. 8. 23.
• textsms