옌의 로그

문제 [백준] 진우의 민트초코우유 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 사용 알고리즘 - 브루트포스 - 구현 해결방법 문제조건에서 우유의 총합이 10개를 넘지 않는 단 것이 포인트 가능한 우유 좌표의 순열을 모두 탐색해서, 민우가 집으로 돌아올 수 있다는 전제하에 마실 수 있는 최대 우유 개수를 구한다 (*순열 : 시퀀스에 담긴 원소를 중복없이 순서에 상관있게 나열하는 것) 예를 들면, 우유가 총 3개 있다고 했을 때, 각각의 우유 좌표를 벡터에 저장한다 {{1,1}, {3,4},..

문제 [백준] 감소하는 수 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 사용 알고리즘 - 백트래킹 (Backtracking) 해결방법 감소하는 수는 중복된 숫자를 허용하지 않는다. 이 의미는 nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 이렇게 10개의 숫자 수열이 있을 때, 해당 수열의 부분수열 찾아, 내림차순 정렬해주면 그게 감소하는 수가 된다. 예를 들면, 하나의 숫자만 뽑아서 부분수열을 만들면 다음과 같다 (10C1) {0}, {1}, {2}, , , {7}, {..

문제 [백준] N과 M (10) 사용 알고리즘 - 백트래킹 (BackTracking) 해결방법 주어진 수열을 백트래킹을 통해 탐색하면서, 부분 집합의 개수가 M이 된 경우만 집합에 담는다. 오름차순 정렬 소스코드 사용언어 : c++ #include #include #include #include using namespace std; int N, M; set unique_row; // 부분 수열을 저장할 집합 // 백트래킹을 이용하여 부분 수열 생성 void generateSubsequences(vector& sequence, vector& current, int index) { if (index == sequence.size()){ if (current.size() == M) { vector temp; ..

문제 [백준] 부분수열의 합 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 사용 알고리즘 - 백트래킹(Backtracking) 해결방법 문제 자체는, 주어진 수열에서 모든 부분 수열을 확인하면 되는 문제이다. 모든 부분 수열을 어떻게 확인할건데 ?? >> 백트래킹을 사용해보자 백트래킹 알고리즘의 핵심은 '해를 찾는 도중에 막히면 되돌아가서 다른 경로를 탐색한다' 이다. 문제 예제1을 살펴보면, 다음과 같다 더보기 -- 주어진 수열 [-7, -3, -2, 5, 8] -- 호..