브루트포스 알고리즘

문제https://www.acmicpc.net/problem/1065풀이수학, 브루트포스 알고리즘 입력되는 수는 1000 이하의 수이다. 100 미만의 수는 모두 한수를 이루기 때문에, 100 미만의 수가 들어온다면 N을 출력한다.0 ~ 9까지의 수는 그 자체로 등차수열이다.10 ~ 99까지의 수는 수열을 이루는 수가 2개이기 때문에 등차수열이다.100 이상의 수가 들어온다면 100부터 N까지 아래의 검사를 실시하여, 통과된 개수를 출력한다.현재 수의 각 자리수를 구한다. 연속된 자리수 사이의 차이가 일치한다면 한수이다. 코드#include using namespace std;int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.t..

문제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 백트래킹, 브루트포스 알고리즘 연산자의 수는 N - 1로 어떤 연산에서 사용되지 않는 연산자를 생각할 필요가 없고, 전체 연산자를 어떤 순서로 사용할지 정하면 된다. 재귀 함수에서 현재까지 연산한 값(current)과 사용할 피연산자(operands[depth + 1]와 각 연산자의 남아 있는 수를 인자로 받는다. current와 피연산자를 남아 있는 연산으로 계산하고, 사용한 연산자를 1 줄여..

문제 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 풀이 구현, 브루트포스 알고리즘 1부터 10000까지의 수, n이 셀프 넘버인지 검사한다. 1부터 n 사이의 수 i에 대해서 (n - i)가 n의 생성자인지 검사한다. (n - i)의 각 자리수의 합을 구한다. (n - i) + ((n - i)의 각 자기수의 합) == n 이라면 (n - i)는 n의 생성자이므로 셀프 넘버가 아니다. 위의 방법으로 셀프 넘버를 찾는다. 코드 #include using nam..

문제 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 구현, 브루트포스 알고리즘, 백트래킹 문제를 잘 읽어야 한다. 회전의 순서가 고정적인 것이 아니라, 배열의 최솟값을 구할 수 있도록 회전의 순서를 바꿀 수 있다. 회전의 순서를 정할 수 있도록, dfs를 이용하여 순열 알고리즘을 구현한다. // dfs를 이용한 순열 void dfs(bool select[], int map[], int cnt, int n, int k, vector v) { if (cnt == k) { sol..

문제 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 브루트포스 알고리즘, 너비 우선 탐색, 조합론, 백트래킹 학생은 전체 25명이다. 여기서 자리를 7개 선택하여 문제의 조건이 맞는지 확인하는 방식으로 답을 구한다. 학생의 수가 많지 않기 때문에 브루트포스로 구현해도 시간 초과는 발생하지 않는다. 자리를 선택하는 방법은 백트래킹을 사용한다. 자리 선택과 해제를 반복하며 자리를 7개 선택했다면 현재 상태가 문제의 조건을 만족하는지 확인한다. 문제의 조건은 다음과 같다. 선택한 자리 모두 상하좌우로 연결되어 ..

문제 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개로 나뉘어져야 하므로, 선택한 선거구가 ..

문제 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 브루트포스 알고리즘, 두 포인터, 슬라이딩 윈도우 문제이다. 두 포인터는 구간의 넓이가 유동적으로 변하고, 슬라이딩 윈도우는 구간의 넓이가 고정적이다. 현재 문제에서 회전 초밥은 연속으로 k개 집어야 하므로 구간이 고정적이기 때문에 슬라이딩 윈도우로 풀어야 한다. 슬라이딩 윈도우 방식에서 구간을 한칸 옮겼을 때, 모든 구간을 다시 검사하는 것 보다 변한 구간. 즉, 맨 왼쪽과 맨 오른쪽만 계산하는게 더 빠르다. ..