서로소 집합 먼저 중학생 때 배웠던 서로소를 떠올려보자. 어떤 두 수 A와 B가 있을 때, 두 수의 공약수가 1을 제외하고는 존재하지 않는 수를 서로소라고 부른다. 이를 고등학생 때 배운 집합의 개념을 빌려 그림으로 표현해 보자. 위의 그림은 24와 49의 약수를 벤다이어그램으로 표현한 것이다. 그림을 보면 둘의 공약수가 오직 1만 존재하는 것을 볼 수 있으며, 이런 형태의 수를 서로소라고 부른다. 이제 집합에서의 서로소가 무엇을 의미하는지 알아보자. 정수에서 서로소는 서로의 약수가 1을 제외하고 겹치지 않는 것을 의미했다. 이와 유사하게 서로소 집합은 두 집합의 원소가 겹치지 않는 것을 의미한다. 예를 들면 아래의 그림과 같은 집합을 서로소 집합이라 부를 수 있다. 위의 두 집합 A와 B를 보면, 두 ..
https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 이번에 풀 문제는 아침 산책이라는 문제다. 이전 문제들과는 달리 서브태스크가 있고 각 태스크마다 배점이 부여되어 있는데, 이를 통해 내 풀이가 어떤 조건을 만족하지 못하는지 알 수 있다. 일단 본격적으로 풀이를 하기에 앞서 문제 요구사항을 짚고 넘어가자! 문제에서 장소를 노드로 표현하였으며, 실내인 노드는 1, 실외인 노드는 0으로 표현하였다. 문제에서 구하고자 하는 것은 실내..
그래프 탐색 알고리즘 그래프 탐색 문제는 시작 정점이 주어졌을 때, 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 구하는 문제이다. 그래프 탐색 알고리즘에는 대표적으로 너비 우선 탐색(breadth-first-search;BFS)과 깊이 우선 탐색(depth-first-search;DFS) 방식이 있다. 깊이 우선 탐색(DFS) DFS의 경우 이름부터가 깊이 우선 탐색이기 때문에 노드의 깊이가 직접적으로 나타나지 않는 그래프보다는 트리에서 이해하기가 좋다. 만약 다음과 같은 트리의 1번 정점에서 DFS를 진행한다고 하자. 진행 과정은 아래의 그림과 같다. 먼저 현재 노드인 1번 노드를 방문 처리 한다. 이후 1번과 연결되어 있는 간선을 하나씩 조사하는데, 먼저 4번 노드와 연결된 간선을 조사한다..
