개인공부1221 [알고리즘] 백트래킹 2 (Backtracking) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 해당 필기는 2024.02.15 - [Develop/algorithm] - [알고리즘] 백트래킹 (Backtracking) 에서 이어집니다. 목차 1. 기존 백트래킹 변형 2. 2차원 백트래킹 1. 기존 백트래킹 변형 앞선 포스팅에서 우리는 3가지 형태의 템플릿을 보았다. 이번엔 이를 다른 형태로 변환해 사용해보도록 하자. 이전의 백트래킹(1, 2, 3 템플릿)은 cur가 채운 개수 기준이었다. 새로운 백트래킹 형식은 다음과 같다. 여기서의 cur는 여태까지 본 원소의 개수, cnt는 고른 원소의 개수가 된다. 이를 실제 문제풀이 형식에 맞추어 변형해보면 다음과 같이 바뀐다. 만약 위 코드를 응용해, 3개 이하의.. 2024. 2. 23. [백준] 25602번 : 캔 주기 (C++) 25602번 : 캔 주기 문제) 랑이 집사는 자신의 고양이 랑이와 메리 둘에게 매일 아침 캔을 정확히 하나씩 준다. 랑이 집사가 가진 캔의 종류는 N가지로, 집사는 i번째 캔을 A[i]개 갖고 있다. 랑이와 메리는 입맛이 까다롭고 변덕이 심해서 매일 각 캔에 대한 만족도가 다르다. i번째 날 랑이가 j번째 캔을 먹었을 때 만족도는 R[i][j], i번째 날 메리가 j번째 캔을 먹었을 때 만족도는 M[i][j]로 나타난다. 자연수 N과 A, R, M 배열이 주어질 때, 랑이 집사가 현재 가진 캔으로 K일동안 랑이와 메리에게 하루에 하나의 캔을 줘서 얻을 수 있는 만족도의 합의 최댓값을 구하는 프로그램을 작성하시오. 입력 : 출력 : 랑이와 메리의 만족도의 합의 최댓값을 출력한다. 풀이) 1 2 3 4 5 .. 2024. 2. 20. [백준] 9663번 : N-Queen (C++) 9663번 : N-Queen 문제) N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 : 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 풀이) 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 // 9663. N-Queen #include #include using namespace .. 2024. 2. 19. [백준] 2661번 : 좋은 수열 (C++) 2661번 : 좋은 수열 문제) 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다. 다음은 나쁜 수열의 예이다. 33 32121323 123123213 다음은 좋은 수열의 예이다. 2 32 32123 1232123 길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다. 입력 : 입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다. 출력 : 첫 번째 줄에 1, 2, 3으로만 이루어져 .. 2024. 2. 19. 이전 1 ··· 4 5 6 7 8 9 10 ··· 306 다음
