이분 그래프 이분 그래프 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테...

halting problem 우리 교수님이 항상 이 halting problem에 대한 이야기를 첫 수업마다 한다. 재밌는 이야기라 정리해보자. 이발사 문제 우선 이발사 문제에 대해 알아보자. 어떤 마을에는 이발사가 한 명 있는데 이 이발사는 스스로 이발하지 않는 사람 모두 이발을 해준다. 그러면 이발사의 머리는 누가 이발을 하는가? 만약 스스...

트리의 지름 트리의 지름 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000) 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정...

최대공약수와 최소공배수 수학 관련 문제에서 가장 많이 사용하는 것은 이전 글인 소수와 최대공약수인 것 같다. 보통 최대 공약수를 구하는 문제에서는 유클리드 호제법을 이용한 알고리즘을 사용한다. 시간 복잡도는 O(lonN)이고, 이 글에서는 간단하게 증명을 해보려고 한다. 증명 A와 B라는 두 숫자의 최대 공약수 G를 구해보자. 증명할 내용은 a...

소수 판별 수학 관련된 문제를 풀다보면 어떤 숫자가 소수인지 아닌지를 판별해야 할 때가 많다. 어떻게 어떤 수가 소수인지 아닌지 알 수 있을까? 소수 우선 소수란 자기 자신과 1로만 나누어 떨어지는 수이다. 이 때 1은 제외한다. 2, 3, 5, 7... 숫자 1개가 주어졌을 때 소수인지 판별하는 방법부터 보자. 시간 복잡도 O(N) 가장 간...

특정한 최단 경로 특정한 최단 경로 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했...

거짓말 거짓말 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말...

백준 마라톤 (코스40) (8/8) 39주차는 일본어 문제 + 위상 정렬 4문제라는 문제 셋을 받아서 풀 수 없었다.. 그래도 이번 주차는 수학 + 애드 훅 구성으로 나와서 쉽게 풀만했다. A번 노트북 세 대를 가지고 왔다 (33515, B5) A번 문제 풀이 숫자 2개를 입력 받고 더 작은 것을 출력하면 되는 간단한 문제이다. int ...

Alkon 1주차 챌린지 (6/6) 이번에 학교 알고리즘 동아리 들어갔는데 매주 챌린지가 있다길래 다 풀어보려고 한다. 문제 난이도는 각각 B4, B2, S4, G5, G3, P4였는데 나름 풀만한 난이도였던 것 같다. A번 심부름 가는 길 (5554, B4) A번 문제 풀이 이동하는 시간이 초 단위로 4개가 주어지고, 그걸 다 더한 다음...

GCD(n, k) = 1 GCD(n, k) = 1 문제 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ 10^12)이 주어진다. 출력 GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다. 풀이...