재귀
-
SWEA 1244 : [S/W 문제해결 응용] 2일차 - 최대 상금백준 문제풀이/BRUTE FORCE 2020. 5. 20. 15:29
문제 문제 풀어보기 풀이 재귀를 돌면서 모든 경우를 탐색하는 것은 굉장히 기본적인 완전 탐색 방법입니다. 하지만 이상하게 교환횟수가 7개 정도만 넘어가면 계속해서 시간초과가 뜨더군요. 생각해봅시다. 주어지는 수는 최대 6자리의 숫자입니다. 여기서 두개의 인수를 교환해서 원하는 숫자를 얻기 위해서는 최대 몇번의 교환이 필요할까요? 카드게임을 예를 들어 봅시다. 도둑잡기, 원카드, 훌라 어떤 게임이든 상관없이 손에 6장의 카드가 있습니다. 우리는 이 카드를 정리하기 위해 한 카드 씩 원하는 위치에 가져다 놓습니다. 이 과정은 두 개의 위치를 교한 하는 것과 크게 다르지 않습니다. 그리고 우리는 정확히 카드의 개수만큼 교환할 수 있다면 어떤 순서의 배열이든 만들 수 있습니다. 그렇기 때문에 이 문제에서도 재귀..
-
SWEA 4168 : 삼성이의 쇼핑 ( 비트마스크 + 조합 연습 )백준 문제풀이/Dynamic Programming 2020. 5. 20. 14:00
문제 문제 풀어보기 (로그인 후 접속 가능) 풀이 냅색 문제에서 비트 마스크를 사용하여 선택한 물건들을 출력할 수 있도록 하였습니다. 냅색 알고리즘은 배낭문제에서 나온 기법인데 생각보다 자주 나오는 유형입니다. 최대의 만족도를 구하는 방법은 냅색을 이용해서 구하게 됩니다. 그리고 만족도를 인덱스로 하는 배열에 비트 마스크를 저장합니다. 출력 과정에서 정답이 되는 만족도에 있는 비트 마스크를 통해 어떤 옷을 선택했는지 출력합니다. 코드 #include #include #include #include using namespace std; int max(int a, int b) { if (a > b) return a; else return b; } int T; int ans; int n, m; int v[26..
-
BOJ 1182 : 부분집합의 합백준 문제풀이/BRUTE FORCE 2020. 1. 29. 16:42
문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 풀이 아래의 코드에서 틀린점을 찾아보세요. void go(int index, long long sum) { if (sum == s) { ans++; return ; } if (index >= n) { return; } go(index + 1, sum + a..
-
[재귀] BOJ 9095 : 1, 2, 3 더하기백준 문제풀이/etc 2019. 10. 14. 00:50
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 풀이 요즘 재귀 함수를 구현하는 법을 많이 연습 중입니다. 브루트 포스 문제들을 해결할 때 재귀 함수가 많은 도움이 되기 때문입니다. 이 문제는 재귀를 처음 접할 때 좋을 것..