컴퓨터 공학 기초/알고리즘 (브루트포스)
-
백준 13023(ABCDE)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 20. 21:48
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 해당 문제는 N명의 사람으로 구성 된 그룹이 있으며, 해당 그룹은 M개의 인원들이 친구 관계를 맺고 있다. 이때 아래와 같은 조건의 친구관계를 가지는 그룹일 경우 1 출력 아닐경우 0을 출력하는 문제이다. 주의 사항 : N명의 사람이 최대 2000 명이기 때문에 2000번을 탐색하기에는 시간초과가 발생한다. 따라서 Vector 에 n 번째 인원의 친구 정보만 push 하는 과정을 통해 오직 친구인 사람의 번호만 Vector 에 저장하도록 한다. #include #include using namespac..
-
백준 1182 (부분수열의 합)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 20. 03:58
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개의 정수가 주어질 때 N개의 숫자를 조합하여 더했을 때 주어진 S가 나올 수 있는 모든 경우를 구하는 문제이다. 따라서 DFS를 이용한 조합을 추출하고 해당 조합의 총합이 S인지만 비교해주면 되는 문제이다. 이때 주의해야 할 점은 따로 조합의 크기는 없으므로 재귀가 수행 할 때마다 현재 선택된 수의 총합을 갱신하며 S값과 ..
-
백준 1759 (암호 만들기)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 19:19
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해당 문제는 정수 L, C가 주어지며 C개의 문자들이 주어지면 해당 문자 중 L개의 문자를 가지고 조합을 만들어 해당 조합이 오름차순일때만 출력하는 문제이다. 추가적인 조건은 다음과 같다. 1. 출력 형태역시 문자조합의 오름차순으로 출력을 해야한다. 2. L개의 길이를 가지는 문자열은 항상 1개 이상의 모음, 2개 이상의 자음이 포함되어야 한다. #include #include #include #inc..
-
백준 6603 (로또)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 17:58
https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 양수 K와 K 개수의 수열이 주어질 때 해당 수열로 만들 수 있는 조합을 출력하는 문제이다. #include #include using namespace std; int n; vector nList; vector results; int used[50]; void dfs(int level, int idx){ if (level == 6){ for (int i = 0; i < 6; +..
-
백준 10971 (외판원 순회 2)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 17:38
https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 해당 문제는 N개의 도시가 주어질 때 N개의 도시를 빠짐없이 모두 순회하면서 드는 최소비용을 구하는 문제이다. 이때 도시를 순회하는 과정에 다음과 같은 규칙을 지켜야 한다. 1. 이미 방문한 도시는 재방문 하지 못 한다. 2. 단 마지막 도시에서 가장 처음 도시로 돌아가는 경우에는 재방문이 가능하다. 3. i 번째 도시에서 j 번째 도시로 이동 할 경우..
-
백준 10819 (차이를 최대로)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 16:40
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 해당 문제는 N개의 정수가 주어질 때 해당 정수를 아래에 식에 맞춰 계산 했을 때 나올 수 있는 최대한의 수를 구하는 문제이다. 이때 주어진 정수의 위치는 사용자가 바꿀 수 있으므로 순열을 이용하여 주어진 정수들의 숫자를 바꾸어 모든 탐색을 진행한다. 이렇게 탐색을 진행하면서 바꾼 수열에 식을 대입하여 결과 값만 비교하면 풀리는 문제이다. 풀이 : #include #include using namespace s..
-
백준 1476(날짜 계산)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 15:06
https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타�� www.acmicpc.net 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 위와 같은 조건..
-
백준 16197( 두 동전)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 18. 02:11
https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, �� www.acmicpc.net 해당 문제는 동전이 2개가 존재하며 아래와 같은 규칙을 이용하며 동전이 하나만 떨어지는 최소한의 경우를 구하는 문제이다. 따라서 BFS를 사용한 완전탐색을 이용하여 동전이 떨어질때의 Cnt 값을 반환하는 형식으로 풀이하면 된다. 요구사항 : 동전은 상하좌우로 이동가능하며 최대 10번 까지 이동할 수 있다 초과시 -1 반환 동전이 하나만 떨어질 경우가 없는 경우 -1 반환 동전의 이동방향이 ..