알고리즘/백준

문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 수학, 브루트포스 알고리즘, 조합론, 백트래킹 사전순으로 출력되어야 하므로 미리 입력받은 문자를 정렬시킨 후에 시작한다. 문자열의 길이는 최대 15로 모든 경우의 수를 탐색해도 시간 초과가 발생하지 않는다. 정렬된 문자열의 앞의 문자부터 선택과 선택해제를 반복하며, 선택된 문자열의 길이가 L이라면 정답 조건을 만족하는지 확인한다. 백트래킹으로 문자를 선택한다. void dfs(int index) { // 선택한 문자의 수가 L에 충족한다면 조건에 맞는지 검..

문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 조합론, 너비 우선 탐색, 깊이 우선 탐색, 브루트포스 알고리즘 주어진 선거구에서 임의로 몇 개를 선택하여 A구역으로 설정하고, 선택하지 않은 구역은 B구역으로 설정한다. N이 최대 10이므로 모든 경우의 수를 비교해도 시간 초과는 발생하지 않는다. 선거구를 선택할 때는 깊이 우선 탐색의 방식으로 1번 선거구를 선택하고 계산한 다음, 다시 해제하는 방식으로 진행한다. 선택한 선거구가 문제의 조건을 만족하는지 확인해야 한다. 구역은 2개로 나뉘어져야 하므로, 선택한 선거구가 ..

문제 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 풀이 수학 N이 최대 10,000이므로 모든 순열을 구한다면 시간 초과에 메모리 초과이다. 주어진 순열의 바로 다음 순열을 구하는 방법은 다음과 같다. 순열의 가장 오른쪽부터 바로 왼쪽 원소가 자신보다 작은지 검사한다. 작다면 그 왼쪽 원소(기준)의 오른쪽 원소들 중 기준보다 큰 값 중 가장 작은 값을 가지는 인덱스를 찾는다. 인덱스와 기준의 원소를 맞바꾼다. 기준의 오른쪽 원소들을 오름차순으로 정렬한다. 만약 첫단계에서 알고리즘이 종료된 경우, 해당 순열은 사전순으로 마지막에 오는 순열인 경우로 -1을 출력한다. 코..

문제 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 수학, 조합론 집합 S에서 숫자 6개를 고르는 경우를 모두 출력하는 문제이다. 조합을 이용하면 간단히 해결할 수 있다. 코드 #include #include #include using namespace std; void Combination(vector arr, vector comb, int r, int index, int depth) { if (r == 0) { sort(comb.begin(), comb.end()); for (int i ..

문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 다리는 서로 겹쳐질 수 없으므로, 동쪽의 사이트 M개 중에서 N개의 사이트를 선택하는 경우의 수이다. int Combination(int n, int r) { if (n == r || r == 0) { return 1; } else { return Combination(n - 1, r - 1) + Combination(n - 1, r); } } 단순히 위의 함수로만 구하면 시간 초과가 발생한다. 다이나믹 프로그래밍을..

문제 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘, 너비 우선 탐색 다른 K칸에 최단 거리로 이동하려면, 최단 거리에 있는 S나 K칸에서 로봇을 복제해서 최단 거리로 이동해야 한다. 즉, S와 K칸을 하나의 노드로 취급하여 다른 S와 K칸 과의 간선을 설정하고, 해당 간선으로 최소 스패닝 트리를 이루면 로봇의 최소 이동 거리를 구할 수 있다. 여기서 각 노드의 거리를 구해야 한다. 현재 칸마다 가중치가 없고 각 칸사이의 거리는 1이므..

문제 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 노드에 물을 받을 수 있는 경우는 노드에 우물을 파거나, 물이 들어오는 노드와 연결시키는 것이다. 이 두가지를 하나의 그래프로 표현해야 한다. 우물을 파는 경우를 하나의 노드로 표현하여 한 노드에서 우물을 파는 비용을 해당 노드와 우물을 파는 노드와의 간선의 거리로 표현하여 연결할 수 있다. 기존에는 그래프가 위처럼 되어있다. 여기에 우물 노드를 추가하면 밑의 그래프처럼 표현할 수 있..

문제 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 최악의 경로에서는 내리막길보다 오르막길을 우선으로 선택하며, 최적의 경로는 내리막길을 우선으로 선택한다. 오르막길은 C가 0이므로, 간선을 내림차순으로 정렬하여 크루스칼 알고리즘을 실시하면 최악의 경로를 구할 수 있다. 최적의 경로는 반대로 간선을 오름차순으로 정렬하여 크루스칼 알고리즘을 실시하면 얻을 수 있다. 코드 #include #include #include using na..

문제 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘, 정렬 문제에서 행성 사이의 가중치 후보는 x좌표, y좌표, z좌표의 차의 절댓값이다. 행성의 수는 최대 100,000개 이므로 각 행성에서 다른 모든 행성에 대해 탐색한다면 시간초과와 메모리 초과가 발생한다. 그러므로, 행성 사이의 가중치 후보를 줄여서 계산해야 한다. 행성 사이의 거리는 x, y, z 좌표 차이 중 최솟값이므로, 각 좌표를 나눠서 처리한다. A, B, C 행성의 ..

문제 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 직접 작성한 코드는 모든 노드의 부모 노드가 발전소 노드일 때까지 크루스칼 알고리즘을 진행하며, 각 노드가 이미 발전소와 연결되어있는 간선은 선택하지 않는 방식으로 작성했다. 다른 코드를 보니, 발전소 노드를 미리 하나의 그룹으로 묶어서 크루스칼 알고리즘을 진행하는 방식으로 문제를 해결하였다. 이렇게 하면 모든 노드가 발전소와 연결되었는지 확인할 필요도 없고, 한..