직대딩 블로그

오늘은 알고리즘 문제를 풀 때 정말 흔히 보이는 에 대하여 알아보겠습니다. DFS, BFS, 다익스트라, 스패닝 트리 등 정말 다양한 문제에서 등장하는 것이 그래프죠. ​ 1. 그래프란 ? 가장 기본적인 정의는 정점(Vertex)와 간선(Edge)의 집합입니다. 여기서 간선은, 두 정점을 이어주는 역할을 합니다. 자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주 다양한 형태의 그래프가 있습니다. 위의 그래프는 1,2,3,4,5,6의 총 6개의 정점으로 이루어져 있고, {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)} 의 총 7개의 간선으로 이루어져 있다고 불 수 있겠습니다. V(정점의 집합)..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong." 을 출력하라고 문제에 나와있는데 그럴 필요없다. 왜냐면 문제에서 주어진 n의 범위는 6 ≤ n ≤ 1000000 이고, 골드바흐의 추측은 이미 10의 18제곱 까지 증명되었기 때문이다. ​ 그러므로 그냥 에라토네스의 체를 이용하여 ~n 까지의 소수의 개수를 미리..