백준
[백준 13397] 구간 나누기 2 C++
www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net m개 이하의 구간을 나누어서 각 구간마다의 최댓값 최솟값을 뺀 값 중에서, 최댓값이 나올 수 있는 모든 경우의 수에서 최댓값 중에서 최솟값을 구하는 문제입니다. 구해야하는 값이 조금 복잡하다고 느낄 수 있습니다. 각 구간마다의 최댓값 최소값을 뺀 값 중에서 최댓값을 구하는건 알겠지만, 그러한 구간의 경우수가 정말 많기 때문에, 각 경우의 수마다의 최댓값 중에서 최솟값을 구하..
[백준 1756] 피자 굽기 C++
www.acmicpc.net/problem/1756 1756번: 피자 굽기 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 www.acmicpc.net 피자 굽기는 오븐에 들어갈 피자 크기를 판단하여 오븐 안에 차곡차곡 넣고, 오븐 크기에 따라, 들어갈 수 있는 피자 칸도 달라지게 됩니다. 예제 입력으로 5 6 4 3 6 2 3의 오븐 크기가 나오는데, 이부분을 좀 더 쉽게 생각하면, 5 5 4 3 3 2 2로 숫자를 바꿔서 생각할 수 있습니다. 피자 반죽 5가 5 6을 들어가던 5 5를 들어가던 들어갈 수 있는 크기는 정해져있습니다. 5 6 4에서 4부분을 통과하지 ..
[백준 17471] 게리맨더링 C++
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 이 문제는 브루트포스 문제로, 모든 경우의 수를 다 시뮬레이션 돌려보고, 문제의 조건에 맞다면 경우의 수를 +1 해줍니다. 브루트포스 문제라고 생각했던 이유는 바로, N의 제한이 10밖에 안됐기 때문입니다. 조합을 구하는데 시간복잡도는 약 O(2^N)으로, 2의 10승은 1024이고, 노드가 1개 이상일 때부터 조건이 가능하니까 때문에 2^10승 * 10정도로 생각했습니다. 원리는 두 개의 집단으로 나누면 되는데, DFS 조합을 구..
[백준 1707] 이분 그래프 C++
www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이 문제는 두 개의 정점이 주어졌을 때, 두개의 정점은 인접하지 못하도록 표시 후, 이분 그래프가 맞는지 판별하는 문제입니다. BFS, DFS 둘 중 아무거나 사용하면 됩니다. 이분 그래프 알고리즘의 핵심은, 두 개의 정점이 인접하지 못하도록, 2 가지 색깔로 칠해주는 것입니다. 처음 노드를 선택했을 때 1, 1로 칠해진 노드안에 있는 다음 노드를 선택 했을 때 2, 그리고 2노드안에 있는 다음..
[백준 2178] 미로 탐색 Swift
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 문제는 단순한 BFS, DFS탐색 문제입니다. 기본 문제이지만, Swift 언어 활용을 위해 풀어보려고 합니다. 최소 거리는 BFS탐색을 이용해서 자주 풀기 때문에 BFS코드로 풀었습니다. map함수는 갈 수 있는 곳 1과 갈 수 없는 곳 0으로 입력으로 받았고요. check함수는 방문했는지 여부, distance는 최소거리를 구하기 위해 사용했습니다. 주의 해야할 점은 입력값의 map이 숫자가 붙어서 나오는데, Swift는 readLi..
[백준 11724] 연결 요소의 개수 C++
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 이번 시간은 그래프의 기본인 연결 요소의 개수를 구하는 문제의 풀이법을 설명하겠습니다. 문제에서 조건은 방향이 없는 그래프라고 말하고 있습니다. 입력으로 정점의 개수 N과 간선의 개수 M을 입력받고요, 연결된 요소가 총 몇개 있는지 구하는 문제입니다. 이 문제는 DFS, BFS로 어느것으로 풀어도 되지만, 저는 DFS를 이용해서 깊..