본문 바로가기

silver121

[C++] 백준 1325번: 효율적인 해킹 (DFS) https://www.acmicpc.net/problem/1325 문제 이해하기 문제의 요구사항은 다음과 같습니다.컴퓨터의 신뢰 관계가 주어질 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 구하여라.시간복잡도 어림하기 문제에서 A가 B를 신뢰하는 경우에, B를 해킹하면 A도 해킹할 수 있다는 조건이 있습니다. 이는 방향 그래프에서 B -> A의 관계를 가지고 있다고 해석할 수 있습니다. 따라서 연결 요소가 가장 큰 시작 위치를 구하는 문제입니다. 연결요소의 크기를 구하는 방법으로는 DFS와 BFS가 있습니다. DFS, BFS 알고리즘 이 문제에서는 그래프가 인접 리스트를 통해 구현되므로 시작복잡도는 O(노드 수 + 간선 수)입니다. 문제에서 노드 수의 최댓값은 10,000이고 간선의 .. 2024. 4. 29.
[C++] 백준 14940번: 쉬운 최단거리 (BFS) https://www.acmicpc.net/problem/14940문제 이해하기각 지점에서 목표지점까지의 최단거리를 구하여라.시간복잡도 어림하기BFS 알고리즘 가중치가 같은 최단거리 문제이므로 BFS를 사용하여 해결할 수 있습니다. 탐색 범위인 n x m은 최대 1,000,000 이므로 제한 시간내에 문제를 해결하기 충분한 수치입니다.알고리즘 설계하기 이번 문제는 특정 지점에서 목표 지점까지의 최단거리가 아닌, 모든 지점에서 목표 지점까지의 최단거리를 구하는 문제입니다. 이를 반대로 이야기하면 목표 지점에서 이동 가능한 모든 지점까지의 최단거리를 구하는 것과 같습니다. 따라서 BFS의 시작 위치를 목표지점으로 설정합니다.  BFS 알고리즘은 일반적으로 다음과 같이 구현합니다.1. queue에 시작 지점 .. 2024. 4. 28.
[C++] 백준 6588번: 골드바흐의 추측 (소수) https://www.acmicpc.net/problem/6588문제 이해하기 문제의 요구사항은 다음과 같습니다.자연수 n, 홀수 소수 a, b에 대해 n = a + b를 만족시키는 a, b를 구하여라. 답이 여러 개인 경우에는 b - a가 가장 큰 것을 출력한다.시간복잡도 어림하기소수 구하기  소수를 구하는 문제는 일반적으로 에라토스테네스의 채를 사용합니다. 에라토스테네스의 채를 사용해야하는 이유는 아래 문제 풀이에서 확인하실 수 있습니다. [C++] 백준 4948번: 베르트랑 공준 (소수)4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측quiver-.. 2024. 4. 27.
[C++] 백준 1926번: 그림 (DFS) 1926번: 그림어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로www.acmicpc.net문제 이해하기 문제의 요구사항은 다음과 같습니다.정해진 영역에 그림이 그려져 있을 때, 그림의 개수와 가장 넓은 그림의 크기를 구하여라.시간복잡도 어림하기DFS 알고리즘 연결요소(Connected Component)의 수와 크기를 구하는 문제이므로 dfs와 bfs를 사용할 수 있습니다. 두 알고리즘 모두 O(n^2)의 시간복잡도를 가지므로 최대 500 x 500 = 250,000 번의 탐색을 진행합니다. 이는 제한 시간 내에 문제를 해결하기 적절한 수치입니다. 이번 풀이에.. 2024. 4. 26.
[C++] 백준 5014번: 스타트링크 (BFS) 5014번: 스타트링크첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.www.acmicpc.net문제 이해하기 문제의 요구사항은 다음과 같습니다.위로 U층, 아래로 D층 이동가능 할 때, S층에서 G층으로 가기 위해 눌러야하는 버튼 횟수의 최솟값을 구하여라. 시간복잡도 어림하기BFS 알고리즘 가중치가 같은(이동할 때마다 1씩 추가) 최단거리 문제이므로 BFS로 접근할 수 있습니다. 탐색가능한 최대 노드의 수는 1,000,000이므로 제한 시간 내에 문제를 해결하기 충분한 수치입니다. 따라서 BFS를 통해 문제를 해결하겠습니다.알고리즘 설계하기 BFS 알고리즘은 일반적으로 다.. 2024. 4. 25.
[C++] 백준 1309번: 동물원 (DP) 1309번: 동물원첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.www.acmicpc.net문제 이해하기 문제의 요구사항은 다음과 같습니다.인접한 우리에는 사자를 배치하지 않을 때, 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘  각 우리는 사자를 배치하는지 배치하지 않는지의 두 가지 상태를 가질 수 있습니다. 인접한 우리에는 사자를 배치할 수 없다는 조건 때문에 전체 경우의 수는 더 작겠지만,  n의 최댓값은 100,000이고 우리는 2n개 있으므로 배치하지 못하는 경우를 고려 하더라도 아주 큰 경우의 수를 가질 것입니다. 따라서 브루트 포스 알고리즘은 적절하지 않습니다. DP 알고리즘  사자를 배치.. 2024. 4. 24.

티스토리툴바