알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2398 2398번: 3인통화첫 번째 줄에는 두 개의 정수가 있다. 첫 번째 정수 n(1 ≤ n ≤ 1000) 는 전화망에 있는 스위치의 개수를 나타내며, 두 번째 정수 m은 스위치와 스위치를 연결하는 링크의 개수를 나타낸다. 단, 같은www.acmicpc.net다익스트라와 백트래킹을 이용한 문제였습니다.3자 통화를 할 때 드는 최소 비용과 이때의 연결된 링크의 갯수, 어떤 링크인지를 출력하는 문제입니다. 먼저 3자 통화를 하는데 필요한 최소 비용을 구하는 것부터 해보겠습니다. N개의 정점에서 세명의 위치까지의 최소거리를 구한 후 값을 더해 각 정점에서 출발했을 때의 값을 각각 구한다면 N(

문제 링크입니다. https://www.acmicpc.net/problem/6603 6603번: 로또입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net백트래킹을 이용한 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int N; vector num; int Select[14]; int arr[14]; void solve..

문제 링크입니다. https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 백트래킹과 BFS를 이용한 문제였습니다. N개의 정점이 주어질 때, 이들을 적절하게 나눠 인구수 차이를 가장 적게 만드는 문제였습니다. 해당 문제를 풀려면 구햔해야 하는 것들이 있습니다. 1. 선거구를 나누는 방법 2. 나뉜 선거구가 연결되는 지 확인 3. 선거구의 인구차를 확인 이와 같이 3개를 구현하면 풀 수 있었습니다. 먼저 1번부터 확인해보겠습니다. 1. 선거구를 나누는 방법 인구수를 최소로 ..

문제 링크입니다. https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹을 이용한 문제였습니다. 주어진 알파벳을 통해 암호를 만드는 문제입니다. 암호가 되는 조건은 모음이 1개 이상, 자음이 2개 이상입니다. 나올 수 있는 모든 경우를 출력하는 것이기에 백트래킹을 사용하면 됩니다. 또한, 출력은 사전 순이기에 백트래킹을 시작하기 전에, 오름차순 정렬을 해주고 시작하면 편하게 코드를 짤 수 있습니다. 자세한 것은 코드를 참고해주세요 #define _..

문제 링크입니다. https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹을 이용해 푸는 문제입니다. 해당 문제와 완전히 같은 방식으로 푸는 문제였습니다. https://junseok.tistory.com/316 백준 2239 -스토쿠(C++) 문제 링크입니다. https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개..

문제 링크입니다. https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹을 이용하는 문제입니다. 기본 스도쿠가 주어졌을 때, 가능한 스도쿠 중 조건에 만족하는 것을 구하는 문제입니다. 스도쿠를 채울 수 있는 경우는 3가지입니다. 1. 자신이 속한 3*3 사각형 내에 겹치는 수가 없다. 2. 자신이 속한 행에 겹치는 수가 없다. 3. 자신이 속한 열에 겹치는 수가 없다. 이 3가지 조건을 만족해야 스도쿠를 채울 수 있습니다. 저는 각각 s..

문제 링크입니다. https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net BFS와 구현, 브루트포스가 합쳐진 문제였습니다. 문제 자체는 간단하지만 구현 능력이 있어야했던 문제입니다. 5개 층의 Map이 주어지고, 이를 통해 미로를 구성한 뒤 탈출할 수 있는지를 확인하는 문제입니다. 이 문제를 풀기 위해서 구현해야할 것이 있습니다. 1. 5개 층을 선택하기 2. 층을 반시계 혹은 시계 방향으로 돌리기 3. 구성된 미로를 탐색하기 먼..

문제 링크입니다. https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트리킹을 이용해 푸는 문제입니다. 백트래킹을 통해 모든 경우를 확인해보면 되는 문제입니다. N개의 정수 중, S값을 만들 수 있는 부분 수열을 구하는 문제입니다. 먼저 구할 수 있는 경우는 크게 N가지 입니다. 1. 1개만 사용해 S를 만들 경우 2. 2개만 사용해 S를 만들 경우 ..... N. N개만 사용해 S를 만들 경우 즉, 1 ~ N..

문제 링크입니다. https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net vector와 백트래킹을 이용한 문제입니다. M개가 선택된 수가 항상 오름차순이여야 되며, 같은 수가 여러번 선택되도 됩니다. N개가 입력될 때, 중복된 수가 입력될 수 있기에, 저는 중복된 수를 지우고 시작했습니다. 1. 중복된 수 지우기 sort(num.begin(), num.end()); num.erase(unique(num.begin(), num.end()), num...

문제 링크입니다. https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 이용한 문제입니다. N개의 수가 주어졌을 때 M개의 수를 선택하고 출력하는 문제입니다. N개의 수가 중복되어 주어질 수도 있으며, 선택된 수열이 항상 오름 or 내림차순이 아닐 수도 있는 것이 다른 점이였습니다. 저는 중복된 수가 들어왔을 때, 중복된 수를 모두 없애줬습니다. -> 백터를 사용하면 편합니다. 예를 들어 (9 7 9 1)이 입력되었을 때, (1 7 9)..

문제 링크입니다. https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹을 이용한 문제입니다. N개의 수가 주어진뒤, 주어진 수를 통해 M개만큼 출력하는 문제입니다. 중복된 수도 출력이 되야하기에, check 배열을 통해서 선택된 수를 확인하면 안되는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #..

문제 링크입니다. https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 이용한 문제였습니다. 1~N까지의 수에서 M개의 수를 선택하는 문제입니다. 중복 선택도 가능하기에, check 배열을 통해 X번째 수가 선택되었는지를 확인하지 않고 푸는 문제였습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include..