프로그래밍/알고리즘

1보다 큰 자연수 N을 입력받았을 때, N 이하의 소수(Prime Number)를 모두 구하시오. 방법1: 하나씩 다 나눠보기 어떤 수가 소수인지 아닌지 판별하는 방법 소수(Prime Number)란 1과 자기 자신만 약수로 가지는 수로, 다시 말해 1과 자기 자신으로만 나누어 떨어지는 수이다. (단, 1은 소수가 아니다.) 그렇다면 특정 자연수 N이 소수인지 판별하려면 어떻게 해야 할까? 답은 어렵지 않다. 2부터 N-1까지의 숫자들로 나눠본 후, 나머지가 0인 경우가 하나라도 있으면 소수가 아닌 수이다. is_prime = True for i in range(2, N): if N % i == 0: is_prime = False break print("소수" if is_prime else "소수가 아님..

문제 1부터 N까지의 번호를 가진 N명의 사람이 있다. 각 사람들은 1부터 N 사이의 임의의 수 Ci가 쓰여있는 카드를 한 장씩 가지고 있다. 사람들 간에는 총 M쌍의 친구 관계가 있다. 모든 친구 관계는 양방향이라서, a번 사람과 b번 사람이 친구라면 b번 사람과 a번 사람도 친구이다. 서로 친구 관계에 있는 두 사람끼리는 서로 들고 있는 카드를 원하는 만큼 교환할 수 있다. 모든 사람들은 각자가 들고 있는 카드에 적힌 수가 자신의 번호와 최대한 비슷하기를 원한다. 어떤 한 사람의 불만족도를 그 사람이 들고 있는 카드에 적힌 수와 그 사람의 번호와의 차이로 정의하고, 전체 불만족도는 모든 사람의 불만족도의 합으로 정의한다. 카드 교환이 적절하게 이루어졌을 때, 가능한 전체 불만족도의 최솟값을 구하라. ..