차근차근

0. 제목 백준 1182 부분수열의 합 BOJ 1182 부분수열의 합 C++ 1182 부분수열의 합 1. 문제 https://www.acmicpc.net/problem/1182 2. 풀이 브루트포스 방식으로 해결하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; int arr[20]; int N, S; int cnt; void dfs(int i, int sum){ if(i == N) return; if(sum + arr[i] == S) cnt++; dfs(i + 1, sum); dfs(i + 1, sum + arr[i]); } int mai..

0. 제목 백준 1987 알파벳 BOJ 1987 알파벳 C++ 1987 알파벳 1. 문제 https://www.acmicpc.net/problem/1987 2. 풀이 DFS와 백트래킹을 사용하는 문제이다. 방문 여부를 체크할 때 A~Z, 총 26개의 인덱스를 가진다. 상하좌우 이동하며, 방문하지 않았다면 true로 체크한다. 방문한적이 있다면 무시하고 넘어간다. 가장 깊게 들어간 최댓값이 정답이다. 3. 코드 #include #include #include #include using namespace std; char arr[21][21]; bool visitedAlpha[26];//A~Z int R, C; int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; int df..

0. 제목 백준 1759 암호 만들기 BOJ 1759 암호 만들기 C++ 1759 암호 만들기 1. 문제 https://www.acmicpc.net/problem/1759 2. 풀이 브루트포스를 이용하여 푸는 문제이다. 모음과 자음을 따로 입력받고 벡터에 각각 저장한다. visited는 map으로 설정하였고 해당 string에 방문한적이 있으면 true, 없으면 false를 저장한다. 최소 한개의 모음과 최소 두개의 자음이 포함되어야 하므로 그 조건에 맞고 길이가 길이조건인 L과 같다면 해당 문자열을 사전순으로 정렬하고 visited.count(s)가 false이면 즉, 방문한적이 없으면 result에 push 해주고 return 한다. 만약, 요구하는 길이인 L과 길이가 같지만 자음, 모음 조건을 만족..

0. 제목 백준 1525 퍼즐 BOJ 1525 퍼즐 C++ 1525 퍼즐 1. 문제 https://www.acmicpc.net/problem/1525 2. 풀이 이 문제는 브루트포스와 BFS를 사용하는 문제였다. 아홉개의 칸 순서대로 이어지는 숫자로 표현할 것이기 때문에 0을 9로 바꿔주고 시작한다. 정수를 입력받으면서 start라는 변수에 9자리 수를 저장한다. key, value쌍을 가지고 있는 map을 사용하여 dist를 선언한다. dist[x]는 x까지 움직인 횟수를 뜻한다. BFS를 사용하기 위해 큐를 선언하고 큐가 빌때까지 반복한다. 큐의 맨 앞에 있는 정수를 문자열로 만들어준다. 그 후 pop을 하고 9가 저장되어 있는 인덱스를 찾는다. 찾은 인덱스를 이용하여 x좌표와 y좌표를 찾는다. 미로..

0. 제목 백준 1697 숨바꼭질 BOJ 1697 숨바꼭질 C++ 1697 숨바꼭질 1. 문제 https://www.acmicpc.net/problem/1697 2. 풀이 완전탐색을 푸는데에 5가지 방법이 있다. brute force(N중 for문) 순열 BFS(최소를 구하는 문제) 비트마스크 백트래킹 이 문제는 BFS를 사용하여 푼다. 현재위치와 현재까지 걸린 시간을 큐에 넣고 조건을 확인해가며 push, pop을 반복한다. 그렇게 반복문을 돌다가 현재위치가 동생이 있는 위치와 같아지게 되면 bfs함수는 현재까지 걸린시간을 반환한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33..

0. 제목 백준 10819 차이를 최대로 BOJ 10819 차이를 최대로 C++ 10819 차이를 최대로 1. 문제 https://www.acmicpc.net/problem/10819 2. 풀이 next_permutation 이라는 STL 함수를 사용하면 된다. next_permutation은 순열의 순서를 바꿔주고 순열이 최종적으로 끝나면(완전하게 역순이 되면) 다시 원래 순서대로 바꾼 뒤 false를 반환해준다. 예를 들어, 1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> 1 3 4 2 -> ... -> 4 3 2 1 -> (false반환)1 2 3 4 그리고 처음에 무조건 실행을 하는 do~while문을 사용하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

0. 제목 백준 2309 일곱 난쟁이 BOJ 2309 일곱 난쟁이 C++ 2309 일곱 난쟁이 1. 문제 https://www.acmicpc.net/problem/2309 2. 풀이 9명의 난쟁이중 2명을 제외한 나머지의 합을 모두 구한 후 100과 비교해본다. 2명을 제외한 나머지를 vector에 넣고 오름차순 정렬 후 출력한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include using namespace std; int main(int argc, const char * argv[]) { int A[10]; in..

0. 제목 백준 1065 한수 BOJ 1065 한수 C++ 1065 한수 1. 문제 https://www.acmicpc.net/problem/1065 2. 풀이 어떤 양의 정수 X의 자리수가 등차수열을 이루면 그 수를 한수라고 한다. 1부터 99까지는 모두 한수이다. 문제에서 1000이하의 수를 입력 받는다고 하였으니 100이상, 1000이하 인 수들을 처리해주면 된다. 1의 자리, 10의 자리, 100의 자리를 각각 구해서 각 자리수 사이의 공차가 같으면 한수여부를 판단하는 배열 arr의 해당 index 값을 true로 설정해준다. 마지막에 총 한수의 개수를 구할 때 1부터 입력받은 N까지 루프를 실행하여 배열 arr의 해당 index값이 true이면 개수를 센다. 그 개수가 한수의 개수이다. 3. 코..

0. 제목 백준 1476 날짜 계산 BOJ 1476 날짜 계산 C++ 1476 날짜 계산 1. 문제 https://www.acmicpc.net/problem/1476 2. 풀이 모든 경우의 수를 탐색한다. 완전 탐색(Brute-force)이라고도 한다. 각각 년도가 15, 28, 19를 초과 할 수 없다. 초과하면 다시 1로 갱신이 된다. 나눗셈의 나머지를 이용해서 문제를 풀 수 있다. 현재 년도에서 각각의 수를 뺀 후 나머지가 모두 0일때 반복문을 탈출한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int E, S, M, year; int main(int argc, const char * argv[]) {..