#INFO 난이도 : SILVER2 문제유형 : 백트래킹 출처 : 15663번: N과 M (9) (acmicpc.net) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #SOLVE 백트래킹 방식으로 문제를 풀이했다. 수열을 입력받은 후 sort 함수를 이용해 오름차순으로 정렬한 뒤, 중복이 발생하지 않도록 출력을 해야한다. 2번째 케이스 n = 4 , m = 2 , [9, 7, 9, 1] 를 예로 들어보면 중복 처리를 하지 않는다면 [7, 9]가 2번 출력되고 만다. 따라서 소스 코드에 "이전 수열의 마지막..
#INFO 난이도 : GOLD4 문제유형 : 재귀 출처 : 2448번: 별 찍기 - 11 (acmicpc.net) 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net #SOLVE 같은 패턴이 반복되는 재귀 유형 알고리즘 문제이다. 가장 기본이 되는 삼각형의 규칙을 찾아 base condition으로 설정한 뒤, 삼각형 각각의 좌표를 fill_star(배열에 알맞은 *을 채워 주는 함수)의 파라미터로 보낸 뒤 재귀로 호출하여 풀이하였다. void fill_star(int x, int y){ board[x][y] = '*'; board[x+1][y-1] = '*'; b..
#INFO 난이도 : SILVER2 문제유형 : 백트래킹 출처 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net #SOLVE i번째 수를 더할지 말지 정한 뒤 i+1번째 수를 정하러 들어가는 방식으로 풀이했다. {-3, -2, 5} 수열을 예시로 들어보도록 하자. 왼쪽은 현재 수를 더하지 않는 케이스 오른쪽은 현재 수를 더하는 케이스이다. 아래 그림과 같이 백트래킹 방식을 이용해 모든 경우를 탐색한 뒤 합이..
#INFO 난이도 : SILVER3 문제 유형 : 백트래킹 출처 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #SOLVE 백트래킹 N과 M시리즈 4번째 문제이다. 문제의 조건은 수열을 사전 순으로 증가하는 순서로 출력해야 한다. st(시작)변수를 이용해 조건문을 작성하여 가지치기를 수행하면 풀리는 간단한 문제이다. int st = 1; if(k != 0) st = arr[k-1]; for(int i = st; i
#INFO 난이도 : SILVER1 알고리즘 : 재귀/분할정복 문제 출처 : 2447번: 별 찍기 - 10 (acmicpc.net) 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net #SOLVE 큰 문제를 작은 문제로 나누어 풀이하는 분할정복 문제이다. 우선 배열의 원소를 모두 빈 칸으로 채워준다. int n; cin >> n; for (int i = 0; i < n; i++) fill(board[i], board[i]+n, ' '); 다음으로 재귀 함수를 정의한다. solve 함수는..