분류 전체보기

https://www.acmicpc.net/problem/2568전깃줄이 교차? 전깃줄이 교차한다는 것은 무엇일까?두 개의 전깃줄이 교차하려면 A의 위치와 B의 위치가 꼬여있어야한다. 예를 들어 임의의 두 전깃줄 a, b가 있다고 할때, a의 전봇대 A에서의 위치를 a1, B에서의 위치를 a2 라고 하고,마찬가지로 b1, b2 라고 했을 때, a1 > b1 이면 a2 a1 b2 일때,전깃줄이 꼬인다고 할 수 있다. 그렇다면 한 전봇대에 대해 오름차순으로 정렬한 다음,반대편 전봇대에 연결되어있는 위치가 "꼬여있는"지를 확인하면 된다. 예를 들어,주어진 예제 입력의 경우에서,전봇대 B의 위치에 대해서 오름차순으로 정렬을 한 후 전봇대 A의 위치를 살펴보자. index01234567B124678910A426..

https://www.acmicpc.net/problem/28872024.06.09 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application1. an Application Union-Find 를 알아보기 전에 이것을 언제 사용하는지를 먼저 파악하는 것이 좋아보입니다. MST(* Minimum Spanning Tree), 최소신장트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최hw-hk.tistory.com문제를 처음 보자마자 최소 신장 트리 문제임을 알았다.하지만 기존의 최소 신장 트리..

https://www.acmicpc.net/problem/16566문제는 단순해 보였다.처음 문제를 읽자 마자 생각한 것은 다음과 같다.리스트에 민수가 뽑은 숫자들을 담는다.리스트를 정렬하고 철수가 보여주는 카드보다 큰 수의 숫자를 뽑는다.뽑은 숫자는 삭제하고 2번으로 돌아간다. 왜 리스트를 정렬하는가? 리스트를 정렬하지 않으면 철수가 보여주는 카드보다 큰 수들 중 가장 작은 수를 찾기 위해서는 선형탐색밖에 답이 없기 때문이다. 선형탐색의 시간 복잡도는 O(N) 이므로, 최대 4,000,000 x 10,000 = 40,000,000,000 의 연산이 필요하다. 대충 100,000,000 에 1초 이므로, 이는 반드시 시간초과가 발생한다. 하지만 정렬을 한다면 다르다. 정렬이 되어있는 자료구조에 대해서는 ..

1. Path Path는 한 정점에서 다른 정점가지 연속되는 간선들을 통해서 도달할 수 있는 방법입니다. 예를 들어 아래와 같은 그래프가 있을 때:1번 정점에서 3번 정점까지 도달할 수 있는 Path 는 다음과 같이 나타낼 수 있습니다:1-e1 → 2-e1 →  1-e3 →  3-e4 →  2-e6 →  2-e5 →  2-e4 →  3 이때 간선의 이름과 같이 정점의 이름도 같이 적어주는데, 그냥 간선 이름들만 적어줘도 Path 를 설명할 수 있지 않을까?그렇지 않습니다. 만약 e1 → e1 → e3 → e4 → e6 → e5 → e4 라고만 적어놨다면,처음 시작하는 노드는 어디였고, 어느 정점에서 어느 정점으로 향하는 간선인지 명확하지 않습니다. 다시한번 Path 에 대해 정의하자면 다음과 같습니다: ..

3. Graph Patterns 3.1 Complete Graph - Kn 서로 다른 노드들의 모든 노드쌍에 대해서 간선을 공유하는 단순 그래프를 Complete Graph - Kn 이라고 합니다. 이때 n 은 정점의 개수입니다.(* A simple graph is complete if every pair of distinct vertices share an edge. The notation Kn denotes the complete graph on n vertices) 3.2 Cycles - Cn ... (* The cycle graph Cn is a circular graph with V = {0,1,2,...,n-1} where vertex i is connected to i+1 mod n and ..

0. 들어가기 전 해당 글은 Zeph Grunschlag 의 Graphs 에서 배운 내용을 정리하는 글 입니다. 1. Graphs - Intuitve Notion 그래프는 정점(혹은 노드)(* Vertices or Nodes)들의 집합입니다. 이를 간선(* Edges)들에 연결된 점들로 표현할 수 있습니다.수학적으로 (멀티그래프를 제외한) 그래프는 정점 집합(* Vertices)에 대한 이진 관계(* binary-relations) 입니다. 2. various types of Graphs  그래프를 사용하는 곳이 많기 때문에 서로 다른 종류의 그래프들이 필요합니다. 예를 들어, local computer network 에서는 bidirectional(* undirected) 하고 loop 가 없어야 하며..

1. an Application Union-Find 를 알아보기 전에 이것을 언제 사용하는지를 먼저 파악하는 것이 좋아보입니다. MST(* Minimum Spanning Tree), 최소신장트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리입니다. 그렇다면 Spanning Tree 는 무엇일까요? Spanning Tree 는 그래프 내의 모든 노드를 포함하는 부분 그래프입니다. 또한 Spanning Tree 는 그래프의 최소 연결 부분 그래프이기도 합니다. 최소 연결이란 간선의 수가 가장 적은 것을 의미합니다.즉, n 개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1) 개 이므로, Spanning Tree 의 간선의 개수는 (n-1) 개 입니다.다른 말로 하면 주어진 그..