Do you believe in you?

백트래킹(Back Tracking) - 완전 탐색에서 불필요한 분기(Branch)를 가지치기(Pruning) - 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 즉, Backtracking이란, 간단하게 말해 brute-force(전부 일일히 다 해보는 것)방법을 수행하지만 한정 함수(bounding function)을 이용해 경우의 수를 줄여나가는 방법을 말한다. [관련문제] 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 1차원 행열 int queen_col[15] 을 이용해서 퀸의 위..

[문제 설명] 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. (), [], {} 는 모두 올바른 괄호 문자열입니다. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다. 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다. 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 retur..

▷ 문제설명 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 0과 1로 이루어진 지도(1은 땅, 0은 바다)에서 섬의 개수를 탐색하는 문제 상, 하, 좌, 우, 대각선 방향에 땅이 있다면 섬으로 판단. 지도의 가로, 세로로 0 0이 입력될 때까지 지도 입력과 정답 출력을 반복한다. ▷ 문제풀이 지도좌표 (0, 0)에서 부터 현재 위치가 땅인지 판단하고 땅이면 탐색을 시작한다. 탐색은 상, 하, 좌, 우, 대각선을 체크하여 지도 범위내이고 1로 연결되어 있는 곳만 탐색한다. 좌표만 옮겨서 탐색을 반복하므로..

▷ 문제설명 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 주어진 암호를 만들 수 있는 문자열 L 개에서 C개를 골라서(순열) 오름차순으로 출력하는 문제. 단, 암호는 모음의 개수는 1개 이상이고 자음의 개수는 2개 이상인 문자로 이루어져 있다. ▷ 문제풀이 순열문제 이므로 재귀함수를 이용한 DFS 방법으로 풀이할 수 있습니다. [ 변수 설명 ] vector alpha; 알파벳의 개수만큼 쉽게 입력받기 위해 vector 자료구조 사용(동적할당) string answer_arr = ""; 정답 출력을 쉽게 하기 위..

▷ 문제설명 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 집이 있는 곳은 1, 집이 없는 곳은 0으로 표현된 지도정보(정사각형)를 주고, 단지의 수와 각 단지 내 집의 수를 오름차순으로 출력하는 문제 조건) 연결된 집들은 상하좌우에 있는 집이다. 대각선 X. 지도의 크기 N은 5 map_size; for (int i = 0; i < map_size; i++) { for (int j = 0; j < map_size; j++) { scanf_s("%1d", &map[i][j]); // 공백없는 숫자를 한줄씩 입..

▷ 문제설명 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 문제 이 때, n의 범위는 1 T; for (int t = 0; t > num; cout

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ▷ 문제설명 NxM 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제 N, M의 범위는 4 > N >> M; for (int i = 0; i > arr[i][j]; } } StartCalculation(arr, N, M); } void StartCalculation(int arr[SIZE][SIZE], int N, int M) { int ..

1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net ▷ 문제설명 준규가 사는 나라는 연도를 표현할 때 E, S, M 세 문자로 표현한다. 각각의 문자가 가지는 범위는 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19 이다. E, S, M이 주어질 때, E S M으로 표시되는 가장 빠른 연도를 출력하자. ▷ 문제풀이 이 문제의 경우 표현할 수 있는 년도는 15 * 28 * 19 = 7980년까지 이므로 브루트포스 방법으로 1년 부터 7980년까지 구하다가 정답과 같아지는 순간을 찾으면 된다. 이 때, 문제에..

2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net ▷ 문제설명 찐 일곱난쟁이를 찾는 문제! 즉, 가짜 난쟁이 2명이 포함된 9명의 난쟁이 중에서 찐 일곱난쟁이를 찾아야 한다. 그리고 일곱난쟁이의 키를 오름차순으로 출력해야 한다. ▷ 문제풀이 1) 일곱 난쟁이의 키의 합이 100인 것과 순열의 성질을 이용한다. 2) 9명 중, 7명을 선택하는 방법이 아닌 2명의 난쟁이를 선택하는 경우를 구한다.(9C7 = 9C2) 3) 전체 키의 합에서 2명 키를 빼본다. 4) 그 값이 100이 된다면 그 둘이 가짜 난쟁이들이다. ▷ 시..