집주변이 최고야

문제 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1 개의 팀이 존재한다. 이때 선생님은 "팀 합치기" 연산과 "같은 팀 여부 확인" 연산을 사용할 수 있다. 1. "팀 합치기" 연산은 두 팀을 합치는 연산이다. 2. "같은 팀 여부 확인" 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, "같은 팀 여부 확인" 연산에 대한 연산 결과를 출력하는 프로그램을 작성 입력 조건 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다 다음 M개의 줄에는 각각의 연산이 주어진다. "팀 합치기" 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 ..

문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에..

문제 철수는 온라인으로 컴퓨터공학강의를 듣고 있다. 이때 각 온라인강의는 선수강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저. 들어야만 해당강의를 들을 수 있다. 예를들어 '알고리즘’ 강의의 선수 강의로 '자료구조'가 존재한다면, ‘자료구조를 들은 이후에 ‘알고리즘' 강의를 들을 수 있다. 철수는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N=3일 때, 3번강의의 선수 강의로 1번과 2번강의가 있고, 1번과 2번강의는 선수강의가 없다고 가정하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자. 1번 강의: 30시간 2번 강의: 20시간 3번 강의: 40시간 이 경우 ..

위상 정렬이란? 진입차수와 진출차수 위상정렬 알고리즘 동작 흐름 위상정렬 알고리즘 동작 과정 예시 위상정렬 특징 위상정렬 구현 관련 문제 위상 정렬이란? 위상 정렬은 정렬 알고리즘의 일정 사이클이 없는 방향 그래프의 모든 노드의 방향성에 거스르지 않도록 순서대로 나열하는 것 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (O) 자료구조 → 고급 알고리즘 → 알고리즘 (X) 진입차수와 진출차수 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 동작 흐름 과정 (queue를 사용) A. 진입차수가 0인 모든 노드를 큐에 넣는다. B. 큐가 빌 때까지 다음의 과정을 ..

서로소 집합 이란? 일반적인 서로소 집합 자료구조 경로 압축 사이클 판별 서로소 집합(Disjoint Sets) 이란? 공통 원소가 없는 두 집합 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리고 한다. 서로소 집합 자료구조는 두 종류의 연산으로 나누어짐 1. 합집합(Union): 두 개의 원소가 포함된 하나의 집합으로 합치는 연산 2. 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 흐름은 다음과 같음. 1. 합집합 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인 A와 B의 루트 노드 A..

신장트리 란? 크루스칼 알고리즘 이란? 크루스칼 알고리즘 구현 관련 백준 문제 신장 트리(Spanning Tree) 란? 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프 n 개의 정점이 있다면 신장 트리의 간선 수는 n-1 개 최소 신장 트리(Minimum Spanning Tree)는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리 가중치는 거리, 비용, 시간 등 여러가지로 응용 가능 최소 신장 트리의 대표적인 알고리즘은 프림(Prim), 솔린(Sollin), 크루스칼(Kruskal) 알고리즘이 존재 Prim 알고리즘 최초 선택된 정점에 연결된 간선들 중에서 작은 가중치를 가지는 간선을 선택하여 만드는 알고리즘 간선의 개수 N, 노드의 개수가 E 시간복잡도 O(N^2) 또는 힙을..