본문 바로가기

서로소알고리즘2

[이코테] 팀 결성 - 이해까지 도와주는 풀이 문제 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다. 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는 지 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력 조건 1. 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 2024. 1. 21.
다양한 그래프 알고리즘 - 서로소 집합 안녕하세요. 오늘은 코딩 테스트에서 사용할 수 있는 다양한 그래프 알고리즘에 대해서 소개드리려고합니다. 그래프 알고리즘에 들어가기 앞서, 먼저 기초 내용부터 다지고 들어가겠습니다. 그래프 노드와 노드 사이에 연결된 간선정보를 가지고 있는 자료구조를 의미합니다. 그래서 알고리즘 문제에서 '서로 다른 개체(혹은 객체)가 연결되어 있다'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 합니다. 트리 더불어 그래프 자료구조 중에서 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억하면 좋습니다. 다익스트라 최단 경로 알고리즘에서는 우선순위 큐가 사용되었는데, 우선순위 큐를 구현하기 위해 최소 힙이나 최대 힙을 이용할 수 있다고 했습니다. 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조.. 2024. 1. 19.