어흥

문제 링크: www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 주의할 점 - 모든 TC가 진행되기 전, 변수를 초기화한다 - 트리가 이뤄지지 않은 Node는 무시한다 → 무조건 Tree가 없다고 하면 WA 2. 구현 - 트리의 특징인 노드 N개 → 간선 N-1개를 통해 MST를 떠올린다(MST도 똑같이 노드 N개, 간선 N-1개) - 트리가 많을 수 있기 때문에 MST의 방법중 하나인 유니온 파인드를 사용한다 - Par[] 함수를 통해 ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 1. 주의할 점 - 범위가 1~10^12를 어떻게 처리할 것인가 → 배열 시도시 컴파일 에러 - Room_Number 벡터로 1이 20만개 들어온다고 할때, 하나하나 다음칸을 확인한다 → O(N^2): TLE 2. 구현 - 해당 방이 배정되었다면, 다음 방을 가리키도록 한다 → '유니온 파인드' 처럼 생각한다 → O(NlgN) Ex. 순서대로 2,2,3이 들어오고 추가로 2가 들어온다면, 2,2,3은 모두 다음으로 비어있는 칸인 5를 가리키도록 하여 2가 5에 할당되도록 한다 - Map을 이용하여 10^12도 처리할 수 있도록 한다. Map..

문제 링크: www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었�� www.acmicpc.net 1. 주의할 점 - 유니온 파인드를 사용할 경우, 부모를 저장하는 Par[] 배열이 항상 갱신되도록 해야한다 - 사용하는 메모리들에 대한 초기화를 잘 한다 2. 구현 - 입력받음과 동시에 Par[] 배열을 초기화하며 입력받은 데이터들을 V벡터에 넣는다 - 각 통신탑과의 거리를 구하여 반지름의 합보다 작거나 같다면 같은 진영으로 판단 -> Make_union() 함수를 수행한다..

문제 링크: https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 1. 주의할 점 - Node를 Cluster로 묶을 수 있어야 한다 - 중복 방문하는 Node에 대한 처리를 해야 한다 2..

문제 링크: https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계 www.acmicpc.net 1. 주의할 점 - Union-find와 함께 친구의 수를 저장하는 배열이 필요하다 - 이미 같은 집합에 속해 있는 경..