컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해결 알고리즘 백트래킹으로 네 개의 칸까지 가는 경우의 합들의 최댓값을 구한다. 이 부분은 백트래킹으로는 탐색이 불가능하므로 따로 완전탐색을 실행해주어야한다. 소스 코드 #include using namespace std; int N, M, result = 0; int arr[501][501]; bool visited[501][501]; int dir[4][2] = {{0, 1}, {0, -..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 알고리즘 전형적인 dfs를 활용한 백트래킹 문제. 비내림차순일 때 출력해주는 것만 유의하면 된다. 소스 코드 #include using namespace std; int N, M; int arr[9]; vector v; map numberCnt; bool flag(){ for(int i=0;i arr[i+1]) return false; } return true; } void dfs(..

www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 알고리즘 해쉬맵과 dfs를 이용해서 푸는 백 트래킹 문제였다. 약간 스킬이 조금 필요한 문제였던 것 같다. 소스 코드 #include using namespace std; int N, M; vector v; map numberCnt; int visited[9]; void dfs(int cnt, int idx){ if(M == cnt){ for(int i=0;i M; for(int i=0;i> num..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 해결 알고리즘 1. num(숫자들의 개수), v(숫자들을 입력받는 배열), c(연산자들을 입력받는 배열)에 입력을 받는다. 2. dfs함수를 실행한다. 이때, n과 num이 같으면 최대값과 최소값을 갱신해준다. 같지 않다면, 연산자들을 순서대로 계산한 값과 v에서의 인덱스를 dfs함수에 다시 넣어 실행해준다. 그 전에 c배열에서의 해당 연산자를 하나 ..

www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 해결 알고리즘 1. 처음에 a, b를 입력 받고, 배열(v)에 모든 알파벳들을 다 넣고 정렬을 해준다. 2. dfs(n, x, y, pos)함수를 실행한다. int n : 글자 수 int x : 모음 수 int y : 자음 수 int pos : 마지막 글자의 배열(v)에서의 위치 3. dfs 함수에서 n이 a와 같아지고 x가 1 이상 y가 2 이상일 때, 암호를 출력해준다. 만약 n이 a와 다르다면, pos부터..

www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해결 알고리즘 1. N과 M 값을 입력을 받고 주어진 수들을 벡터(v)에 저장한 다음 정렬해주고 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같으면 배열(arr)에 있는 값들을 출력해준다. 같지 않다면 배열에 벡터(v)에 저장되어 있는 수들을 배열에 각각 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다. 소스 코드 #include using namespace std; int..

www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해결 알고리즘 1. N과 M 값을 입력을 받고 주어진 수들을 벡터(v)에 저장한 다음 정렬해주고 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같으면서, func 함수의 반환 값이 true라면, 배열(arr)에 있는 값들을 출력해준다. 같지 않다면 배열에 벡터(v)에 저장되어 있는 수들을 배열에 각각 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다. (func함수는 이 배열에..

www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해결 알고리즘 1. N과 M 값을 입력을 받고 주어진 수들을 벡터(v)에 저장한 다음 정렬해주고 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같으면서, func 함수의 반환 값이 true라면, 배열(arr)에 있는 값들을 출력해준다. 같지 않다면 배열에 벡터(v)에 저장되어 있는 수들을 배열에 각각 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다. (func함수는 이 배열에..

www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 알고리즘 1. N과 M 값을 입력을 받은 다음 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같으면서, func 함수의 반환 값이 true라면, 배열(arr)에 있는 값들을 출력해준다. 같지 않다면 배열에 숫자들을 1에서 N까지 순서대로 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다. (func함수는 이 배열에 있는 원소들이 비내림차순으로 정렬되어 있는지 확인해주는 함수이다...

www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 알고리즘 이 문제는 N과 M (1), (2)과 달리 next_permutation으로 구현하기 어렵다. 그러므로 이제부터 제대로된 백 트래킹 알고리즘으로 구현을 해야한다. 1. N과 M 값을 입력을 받은 다음 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같다면 배열(arr)에 있는 수들을 모두 출력해주고, 같지 않다면 배열에 숫자들을 1에서 N까지 순서대로 넣고 dfs함수에 n..