트리 위의 모든 입자 이동시켜서 소멸시키기(트리에서의 다이나믹 프로그래밍)

https://atcoder.jp/contests/abc409/tasks/abc409_e E - Pair AnnihilationAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 트리 위에 정점 i에서 xi개의 양전자가 놓여있고, 혹은 -xi개의 전자가 놓여있다. 이때 모든 입자의 합은 0임이 보장된다. 따라서 입자들을 적절히 이동시키면 모든 입자를 소멸시킬 수 있다. 한 입자를 간선 j를 따라 이동시키면 에너지 wj가 소모된다. 양전자와 전자가 같은 정점에 속하면 입자가 소멸된다. 모든 입자를 완전히 소멸하는데 필요한 최소 ..

  • format_list_bulleted 알고리즘/다이나믹 프로그래밍
  • · 2025. 6. 14.
  • textsms

모든 양의 유리수는 단위분수의 합으로 나타낼 수 있다

1. 단위분수 분자가 1이고 분모가 양의 정수인 분수 1/1, 1/2, 1/3,...이 단위분수이다. 1/(1.5)라든지 1/(3.4)같이 분모가 실수이면 단위분수가 아니다. 흥미로운 점은 모든 유리수는 어떤 단위분수들의 합으로, 여러가지 방법으로 나타낼 수 있다는 점이다. $$\frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20} = \frac{1}{3} + \frac{1}{5} + \frac{1}{6} + \frac{1}{10}$$ 단위분수들의 합을 이집트 분수(Egyptian fraction)라고 부른다 이렇게 나타내는 방법에 대해 여러가지 연구들이 있다.. https://en.wikipedia.org/wiki/Egyptian_fraction Egyptia..

  • format_list_bulleted 정수론
  • · 2025. 4. 28.
  • textsms

그래프에서 역방향 간선을 놓아 노드들의 크기 순서를 찾는 테크닉(도달 가능성)

1. 문제 2458번: 키 순서  1번부터 n번까지 번호가 붙여진 학생들의 키 순서가 주어진다. 예를 들어 1번  이 결과로 모든 학생중 키가 가장 작은 학생부터 자신이 몇번째 학생인지 알 수 있는 학생도 있고,  그렇지 못한 학생들도 있다. 이러한 결과가 주어질때 자신의 키가 몇번째 학생인지 정확히 알 수 있는 학생 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------------ 상식적으로? 먼저 생각해보면 i번이 몇번째 순서인지 알고 싶다면 i번보다 키가 큰 학생의 수, 키가 작은 학생의 수를 찾..

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2025. 3. 29.
  • textsms
트리에서 임의의 노드에서 모든 노드를 적어도 1번 이상 방문하는데 걸리는 최소 거리

트리에서 임의의 노드에서 모든 노드를 적어도 1번 이상 방문하는데 걸리는 최소 거리

E - Tree and Hamilton Path 2 (atcoder.jp) E - Tree and Hamilton Path 2AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  트리의 어떤 정점 A에서 출발하여 모든 정점을 1번 이상 방문하고, 다시 정점 A로 돌아온다고 생각해보면, 만약 트리의 어떤 변을 제거하면 다음과 같이 2개의 연결성분이 생기고 출발점에서 다시 출발점으로 돌아올려면 두 연결성분을 서로 왔다갔다 해야하므로, 정확히 각 변을 2번 지나면 출발점에서 모든 노드를 1번 이상 방문하여 출발점으로 돌아올 수 있다..

  • format_list_bulleted 알고리즘/DFS BFS 정복기
  • · 2024. 7. 11.
  • textsms
DFS로 사이클 탐지하는 알고리즘 탐구하기2 -사이클의 길이-

DFS로 사이클 탐지하는 알고리즘 탐구하기2 -사이클의 길이-

1. 연습문제1 9466번: 텀 프로젝트 (acmicpc.net) 문제를 보면 u가 A[u]를 향하는 그래프이고 이 그래프에서 사이클을 모두 찾아 각 사이클에 속하는 노드의 개수를 구하고 전체 노드 수에서 사이클에 속하는 노드의 개수를 빼면 된다 dfs로 사이클을 탐지할 수는 있는데... 사이클에 속하는 노드의 개수는 어떻게 알 수 있을까? 노드 u1부터 u2,u3,...,un을 차례대로 방문한다고 생각해보자 u1 > u2 > u3 > .... > un 그러다가 다시 un에서 u1으로 온다면? u1 > u2 > u3 > ... > un > u1으로 오면 (u1,u2,.u3,...,un)이 하나의 사이클이 된다. 따라서 dfs로 노드를 방문할때마다, 방문한 노드의 번호를 1,2,3,.. 순서대로 매겨준다...

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2024. 6. 15.
  • textsms
DFS로 사이클 탐지하는 알고리즘 탐구하기1 -기본 이론-

DFS로 사이클 탐지하는 알고리즘 탐구하기1 -기본 이론-

1. 무향 그래프에서 사이클 union find 알고리즘을 이용해서 쉽게 판단할 수 있다 https://deepdata.tistory.com/432 union find 알고리즘 활용 - 사이클을 판별하는 방법 -1. 사이클 판별 서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다. 방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다 핵심 원리는 union 연산이 그래프에deepdata.tistory.com  간선을 확인하면서, 간선을 연결하는 두 노드의 대표자가 서로 같다면 사이클이 발생하는것이고, 서로 다르다면 union을 수행하면 된다  2. 유향 그래프에서 사이클 한 노드에서 출발했다가, 다른 노드들을 거쳐 이동하다보니 출발 노드로 돌아오면 사이클이 존재한다고 한..

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2024. 6. 14.
  • textsms