백준

[백준 - 14502] 연구소 [C++]

1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이과정 1. 연구소의 빈 칸 3곳에 벽을 세운다. 2. 바이러스를 퍼뜨린다. 3. 안전영역의 크기를 구하고 최댓값을 갱신한다. 이때 벽을 세울 수 있는 모든 경우의 수에 대해 1~3을 반복한다. [코드설명] main함수의 3중 for문으로 벽을 세울 3곳을 선정하고, 3곳이 모두 빈 칸이면 벽을 세우고 바이러스를 퍼뜨린 후, 안전영역의 크기 계산 및 최댓값 갱신을 수행한다. 이때, 3곳의 좌..

[백준 - 14889] 스타트와 링크 [C++]

1. 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 풀이과정 1. n명의 사람을 두 팀으로 나눈다 2. 각 팀의 능력치의 합을 계산한 후 차이를 구한다. 3. 차이의 최솟값을 갱신한다. 1~3을 반복하며 스타트와 링크 팀의 능력치의 차이의 최솟값을 구할 수 있다. [코드설명] stats[i][j]는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. dfs함수는 0번~n-1번 사람들 중 n/2명의 가능한 조합을 구해준다. 예를 들..

[백준 - 14888] 연산자 끼워넣기 [C++]

1. 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 풀이과정 문제 제목처럼 수들 사이에 연산자를 끼워넣어서 계산해보며 최댓값, 최솟값을 갱신해주면 된다. 주어진 연산자들을 나열할 수 있는 모든 경우의 수에 대해 식의 값을 계산해보면 된다. [코드설명] opers 는 연산자들을 저장하는 벡터이다. 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수가 2..

[백준 - 10819] 차이를 최대로 [c++]

1. 문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 2. 풀이과정 입력받은 n개의 수를 나열할 수 있는 모든 경우의 수에 대해 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 위 식을 계산하며 최댓값을 갱신해주면 됩니다. [코드 설명] dfs함수는 n개의 수의 순서를 적절히 바꿔줍니다. ex) n = 3, A = {1, 2, 3} 1 2 3 1 3 2 2 1 3 . . calculate함수는 나열된 ..

[백준 - 11724] 연결 요소의 개수 [C++]

1. 문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net 2. 설명 : 무방향 그래프가 주어졌을 때, 방문하지 않은 정점에 대해 dfs로 그 정점과 연결된 모든 정점들을 방문하며 visited배열에 체크해줍니다. 그렇게 한다면 아래 코드에서 cnt++가 실행되는 횟수가 결국 연결 요소(Connected Component)의 개수가 됩니다. 3. 코드 #include #inc..

[백준 - 11403] 경로찾기 [C++]

1. 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 설명 : 주어진 방향 그래프에서 각 정점을 기준으로 dfs로 연결된 정점들을 방문하면서 visited배열에 체크해 나갑니다. 모두 완료한 이후 visited배열을 출력해줍니다. 3. 코드 #include using namespace std; int arr[110][110], n; bool visited[110][110]; void dfs(int first, int x, int y) { visited[first][y] = t..