안녕하세요, 이번 글에서는 백준 1389번 문제인 “케빈 베이컨의 6단계 법칙” 문제를 함께 해결해 보겠습니다. 이 문제는 각 사람 사이의 거리를 계산하여 케빈 베이컨 수가 가장 작은 사람을 찾는 문제입니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 문제 URL: https://www.acmicpc.net/problem/13891. 문제 설명1) 문제 개요여러 사람들 사이의 친구 관계가 주어질 때, 각 사람의 케빈 베이컨 수를 계산하여 가장 작은 사람을 찾는 문제입니다. 여기서 케빈 베이컨 수란, 한 사람이 다른 모든 사람들과 연결되는 최소 단계를 의미합니다. 2) 입력 • 첫 번째 줄: 사람의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ..
Python
안녕하세요, 이번 글에서는 백준 1417번 문제인 “국회의원 선거” 문제를 함께 해결해 보겠습니다. 이 문제는 다솜이가 국회의원이 되기 위해 필요한 최소 득표수를 계산하는 문제입니다. 함께 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 문제 URL: https://www.acmicpc.net/problem/1417 1. 문제 설명 1) 문제 개요• 다솜이는 국회의원 선거에 출마했습니다.• 다솜이 이외의 다른 후보들이 존재하며, 다솜이가 가장 많은 득표수를 가져야만 당선될 수 있습니다.• 다른 후보의 득표수 중 다솜이보다 많은 득표수를 가진 후보들의 표를 빼앗는 방식으로 다솜이의 득표수를 늘려야 합니다.• 이때, 다솜이가 최소 몇 표를 더 받아야 하는지 계산하는 문제..
이번 글에서는 백준 14889번 문제 “스타트와 링크”를 함께 해결해 보겠습니다. 이 문제는 N명의 사람들이 두 팀으로 나누어질 때, 두 팀의 능력치 차이를 최소화하는 문제입니다. 1. 문제 설명1) 문제 개요 • N명의 사람들이 두 팀으로 나뉘어 게임을 합니다. • 각 사람마다 다른 사람과 팀을 이루었을 때의 능력치가 주어집니다. • 두 팀의 능력치 차이를 최소화하는 것이 목표입니다. 2) 입력 • 첫 번째 줄에 사람의 수 N이 주어집니다. (4 ≤ N ≤ 20, N은 짝수) • 두 번째 줄부터 N개의 줄에 걸쳐 각 사람의 능력치가 주어집니다. 3) 출력 • 두 팀의 능력치 차이의 최솟값을 출력합니다. 2. 접근법1) 입력받기 • sys.stdin.readline을 사용하여 입력 속도를 높입니다. • ..
이번 글에서는 백준 2606번 문제 "바이러스"를 함께 해결해 보겠습니다. 이 문제는 네트워크 상에서 컴퓨터 바이러스가 퍼지는 것을 시뮬레이션하여 감염된 컴퓨터의 수를 계산하는 문제입니다.1. 문제 설명1) 문제 개요• 한 컴퓨터가 바이러스에 감염되면 네트워크를 통해 연결된 모든 컴퓨터로 바이러스가 퍼집니다.• 1번 컴퓨터가 바이러스에 감염되었을 때, 네트워크를 통해 바이러스에 감염되는 컴퓨터의 수를 계산하는 문제입니다.2) 입력• 첫 줄에 컴퓨터의 수 N (1 ≤ N ≤ 100)과 연결된 쌍의 수 T가 주어집니다.• 다음 줄부터 T개의 줄에 걸쳐 각 줄에 두 정수 a와 b가 주어집니다. 이는 a번 컴퓨터와 b번 컴퓨터가 연결되어 있다는 의미입니다.3) 출력• 1번 컴퓨터를 통해 바이러스에 감염..
이번 글에서는 백준 14267번 문제 “회사 문화 1”을 함께 해결해 보겠습니다. 이 문제는 직원 간의 칭찬이 어떻게 전달되는지를 시뮬레이션하여 각 직원이 받은 최종 칭찬 수를 계산하는 문제입니다. 1. 문제 설명1) 문제 개요 • 회사의 직원들에게 칭찬이 주어졌을 때, 그 칭찬이 상사로부터 전달되어 각 직원이 최종적으로 받은 칭찬의 수를 계산하는 문제입니다. • 회사는 트리 구조로 구성되어 있으며, 각 직원은 하나의 상사를 가지고 있습니다. 2) 입력 • 첫 줄에 직원의 수 n과 칭찬 횟수 m이 주어집니다. • 두 번째 줄에 각 직원의 상사 번호가 주어집니다. 루트 직원의 상사 번호는 -1입니다. • 다음 m개의 줄에 걸쳐 칭찬 정보가 주어집니다. 각 줄은 두 정수 i와 w로 구성되며, i번 직원에게 ..
