그래프에서 각 노드의 사이클까지 거리를 빠르게 구하는 놀라운 방법

1. 문제 정확히 하나의 사이클을 포함하는 무방향 연결 그래프(connected undirected graph)가 주어진다. 각 노드 번호가 0부터 n-1까지 n개의 노드를 가진다. 노드 a와 b 사이 거리가 a에서 b로 가기 위해 필요한 최소 간선의 수 노드 i = 0,1,2,..,n-1에서 이 그래프에 존재하는 사이클에 있는 임의의 노드까지의 최소 거리를 구한다면? 당연히 사이클에 포함된 노드는 사이클 까지의 거리가 0이다.   위 그래프는 1,2,3,4가 사이클을 이룬다. 1,2,3,4는 각각 사이클까지 거리가 0이고, 0번 노드는 사이클 까지 거리가 1 5번 노드는 사이클 까지 거리가 1, 6번 노드는 사이클 까지 거리가 2이다.  2. 풀이 사이클에 포함된 노드는  위상정렬에 포함되지 않는다는 ..

• format_list_bulleted 위상정렬
• · 2024. 11. 13.
• textsms

그래프에서 서로 연결된 세 정점의 차수 합의 최솟값 찾기

17089번: 세 친구 (acmicpc.net) 서로 친구인 a,b,c에 대하여 a의 친구 수 + b의 친구 수 + c의 친구 수가 최소가 되도록 만들고 싶다. a의 친구 수에는 b,c는 제외해야한다. 마찬가지로 b,c의 친구 수에는 a,c, a,b는 제외해야한다. a의 친구 수 + b의 친구 수 + c의 친구 수 - 6의 최솟값을 찾아야한다는 소리 친구 관계를 그래프로 만드는데 각 정점에 연결된 정점을 set()으로 만들어서 O(1)로 서로 친구인 정점을 찾도록 만들자 from sys import stdinn,m = map(int,stdin.readline().split())graph = [set() for _ in range(n+1)]for _ in range(m): a,b = map(int,s..

• format_list_bulleted 브루트포스
• · 2024. 9. 10.
• textsms

특정한 정점들을 반드시 포함하는 최소 정점 트리 만들기 - list말고 반드시 set을 사용해야하는 경우

https://atcoder.jp/contests/abc368/tasks/abc368_d D - Minimum Steiner TreeAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  1부터 n까지 번호를 가진 정점을 가진 트리에서 어떤 정점들을 제거할때, 특정한 정점 v1,v2,...,vk를 반드시 포함하게 하는 트리를 만들고 싶다면, 그러한 트리의 최소 정점 수는? 예를 들어 왼쪽 트리에서 1,3,5를 반드시 포함하는 트리를 만들고 싶을때, 4번, 6번, 7번을 제거하면 된다     사실 테크닉에 감탄해서 복기하는거긴 한..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 8. 31.
• textsms

알고리즘 테크닉 - 좌표압축(grid compression)

1. 좌표압축이란 정점 번호가 1에서 $10^{9}$사이의 값으로 이루어져 있는 그래프가 하나 주어질때, 1번 정점에서 시작하여, 방문 가능한 서로 다른 노드의 수를 구하는 프로그램을 작성하세요. 일반적인 DFS 탐색으로는 1번 정점에서 N번 정점까지 번호가 매겨져 있어서, 큰 문제 없이 크기가 N인 visited 배열과 간선 정보를 나타내는 인접 리스트를 만들어 해결할 수 있습니다. 하지만 위와 같이 정점 번호가 1번에서 $10^{9}$사이로 주어진다면, visited 배열을 만드는 순간 메모리 초과로 일반적인 방법으로는 해결하기 어렵다. 그런데 조금만 생각해보면... 주어진 정점 번호를 오름차순으로 나열할때, 1,4,6,7,30,2000,$10^{9}$밖에 없으며.. 이 정점들의 번호를 1번부터 순서..

• format_list_bulleted 압축 알고리즘
• · 2023. 4. 14.
• textsms

자바 자료구조4 -HashMap과 HashSet-

1. HashMap 해싱을 기반으로 데이터들을 관리해주는 자료구조 파이썬에서 dict와 대응된다 HashMap은 (key,value) 쌍 형태로 들어가 있어서, key와 그 key에 따른 value값을 동시에 저장하는 형태 따라서 HashMap의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도는 O(1)이다. HashMap은 TreeMap보다 속도가 빠르며, 값 자체에만 관심이 있지, 그 순서에는 관심이 없는 자료구조 HashMap 사용을 위해서 import java.util.HashMap; HashMap (name) = new HashMap(); 형태의 선언이 필요하다. K,V는 key와 value에 해당하는 타입이다. import java.util.HashMap; public class Main { p..

• format_list_bulleted Java 기초
• · 2023. 3. 4.
• textsms

집합 set의 메소드

1. set 중복되는 요소가 없이, 순서에 상관없는 데이터들의 묶음 중복을 허용하지 않으므로 중복되는 원소가 있다면 하나만 저장함 순서가 없으므로 인덱스를 이용한 접근이 불가능하다 수학에서 집합을 표현한 자료형 >> 집합연산이 가능한데, 여집합을 나타내는 연산자는 별도로 존재하지 않아 >> 중복된 값이 존재하지 않아 담고 있는 요소를 삽입, 변경, 삭제가 가능함 >> 가변 자료형(mutable) 2. set의 메소드 리스트에서 append()를 쓰는것과는 다르게 set은 add로 추가한다는 점에서 add가 제일 중요하고.. 나머지도 알아보자고 set은 순서가 없는 자료형이기 때문에 s.pop()을 하면 랜덤하게 항목을 제거해서 반환한다고함 비슷하게 add()도 랜덤한 위치에 넣는다고 하는데 3. s.ad..

• format_list_bulleted Python
• · 2022. 8. 1.
• textsms