본문 바로가기

Algorithm109

이분 그래프 (Bipartite Graph) 이분 그래프 (Bipartite Graph) 이분그래프는 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 뜻한다. 다시 말해, 그래프의 모든 정점이 두그룹으로 나뉘어져있고 같은 그룹끼리는 인접하지 않은 그래프이다. 이분그래프를 확인하는 방법은 BFS 나 DFS를 이용한다. 1. BFS , DFS 를 수행하며 각 정점을 방문할때 마다 인접한 그룹과 다른 색을 칠한다. 2. 각 정점을 방문 중, 자신과 인접한 정점의 색이 자신과 같다면 그 그래프는 이분 그래프가 아니다. (발견과 동시에 BFS 종료) 3. 모든 정점을 방문하고 인접한 정점끼리 같은색이 없다면 이분그래프이다. 특징) 모든 정점을 방문하기 때문에 시간 복잡도는 O (V+E) 이다. 아래의 코드는 백준사이트의 이분그래프를 풀면서 BFS.. 2021. 3. 6.
51. SW_Test 연습 백준 스타트링크 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄.. 2021. 3. 2.
50. SW_Test 연습 백준 보물섬 www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최.. 2021. 3. 2.
49. SW_Test 연습 백준 어른상어 www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 청소년상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다. N×N 크기의 격자 중 M.. 2021. 2. 28.
위상정렬 위상정렬은 정렬 알고리즘의 종류이다. 위상정렬이란 '방향그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열' 하는 것이다. 쉽게 비유를 하자면 '대학교 커리큘럼'을 예로들수있다. 예를들어 모 대학교의 컴공과는 인공지능과목을 자료구조를 선수강한 뒤에 신청할수있도록 하였다. 이처럼 그래프상에서 선후관계가있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 순서를 계산할수있다. 위상정렬의 알고리즘 순서는 다음과 같다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌때 까지 다음의 과정을 반복한다. 1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 여기서 진입 차수란, 특정노드로 들어오는 간선의 개수와 같다. #.. 2021. 2. 26.
신장트리, 크루스칼 알고리즘 신장트리는 그래프에서 자주보이는 유형이다. 신장트리란, 하나의 그래프가있을때 모든 노드를 포함하면서 사이클을 발생 시키지 않는 부분그래프를 뜻한다. 이처럼 신장트리에서 최소 비용으로 만들어진 신장트리를 '최소비용 신장트리' 리고하는데 이 신장트리를 구하는 대표적인 방법은 크루스칼 알고리즘이 있다. 크루스칼 알고리즘의 동작순서는 다음과 같다. 1. 간선데이터의 비용을 크기에 따라 오름 차순 정렬한다. 2. 간선을 하나씩확인하며 사이클을 발생 시키는지 확인한다. 1. 사이클이 발생하지 않는다면 최소비용 신장트리에 포함시킨다. 2. 사이클이 발생하는 경우 포함하지 않는다. 3. 모든 간선에 대하여 2 번의 과정을 반복한다. 다음은 크루스칼 알고리즘의 코드이다. #include #include #include .. 2021. 2. 26.

티스토리툴바