공부하자

4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 베르트랑 공준 문제를 풀기 위해서는 이 에라토스테네스의 체를 활용한 소수판별법을 먼저 알아야한다. 이 방법을 이용하지 않고 기존의 방법처럼 무식하게 풀다보면 시간 초과가 나오게 된다. 에라토스테네스의 체 (Sieve of Eratosthenes) 에라토스테네스의 체란 소수를 대량으로 빠르고 정확하게 구하는 방법이다. 시간 복잡도는 O(N^(1/2)). 이는 다음과 같은 절차로 진행된다. 원하는 숫자까지의..

7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS 알고리즘을 이용하여 구현하는 그래프 탐색 문제이다. 알고리즘을 구상하고 코드로 직접 옮기는 과정에서, 행렬로 되어있는 입력 예시들을 그래프로 바꾸어 이해하는 단계가 좀 껄끄러웠다. 게다가 문제에서 익은 토마토의 개수가 여러개인 경우도 고려하여 구현해야 되기 때문에 이것또한 생각을 많이 해야했다. C++ / vs code 환경에서 구현하였다. #include #include using namesp..

1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS의 구현을 묻는 아주 간단한 문제이다. 우선, DFS와 BFS의 의미는 다음과 같다. DFS : Depth-First Search (깊이 우선 탐색) / BFS : Breadth-First Search (너비 우선 탐색) DFS는 함수의 재귀 호출을 이용하여 소스코드로 구현하게 되지만, BFS의 경우엔 자료구조 Queue를 사용하여 소스코드로 구현하는것이 일..