vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

https://atcoder.jp/contests/abc410/tasks/abc410_d D - XOR Shortest WalkAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 방향 그래프가 주어지는데, A에서 B로 가는 간선의 가중치가 W이다. 이때, 1번부터 N번 정점까지 경로의 가중치들의 bitwise xor이 최소가 되는 경로에 대해 그 최솟값을 구하면? 여기서 1번부터 N번 정점까지 경로는, 동일한 간선이나 동일한 정점을 여러번 방문하더라도, 처음 시작점이 1번이고 마지막 종점이 N번인 경로이다. ----------..

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

그래프에서 간선 가중치의 bitwise or이 최소가 되는 경로

E - Minimum OR Path E - Minimum OR PathAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 무방향 연결그래프에서 1번부터 N번까지 가는 단순 경로들의 모든 가중치들의 bitwise or의 최솟값을 구하는 문제 단순 경로는 어떤 정점을 두번이상 방문하지 않는 경로를 말한다. 1 > 2 > 3 > 4 > 5는 단순 경로 1 > 2 > 3 > 2 > 3 > 4 > 5는 2번 3번을 2번 방문했으므로 단순 경로가 아니다. ---------------------------------------------..

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

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

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

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2025. 3. 29.
  • 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
DFS 2번으로 트리의 지름을 구하는 방법

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