Algorithm/Backtracking

백트래킹(Backtracking)이란?

백트래킹이란? 1. 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하다가, 가능성이 없다고 판단되면, 되돌아가서 다시 해를 찾아가는 기법 2. 조합, 순열, 부분집합도 가지치기가 없는 백트래킹이라고 할 수 있습니다. 3. 백트래킹을 이용하여, 완전탐색을 수행할 수 있고, 가지치기를 통해 최적화가 가능합니다. 백트래킹은 크게 두 부분으로 구분할 수 있습니다. void back(int depth, int m){ if(depth == m){ // 1. 선택한 원소로 기반으로 결과를 계산하는 부분 }else{ // 2. 원소를 선택하는 부분 } } 꿀팁 재귀 함수는 함수를 명확히 정의하는 것이 좋습니다. 함수를 명확하게 정의하면, 나를 이용하여 나를 정의하는 것이 명확해집니다. 예를 들어 아래와 같은 함..

[백준 16953번] A → B (C++)

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A → B 문제는 백트래킹으로 해결할 수 있습니다. 단, A와 B의 값이 최대 10억이고, 연산 적용시 21억을 초과할 수 있기 때문에 int형이 아닌 long long형을 사용해야합니다. 아래는 전체 코드입니다. #include using namespace std; long long a, b, ans = INT_MAX; void back(int th, long long n){ if(n == b){ ans = min(ans, (long long) th - 1); }else if(n < b){ back(th + 1, 2 *..

[백준 17626번] Four Squares (C++)

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net Four Squares는 백트래킹과 메모이제이션을 이용하여 해결할 수 있습니다. HTML 삽입 미리보기할 수 없는 소스 따라서 해당 범위에서 숫자를 선택하고, 재귀 함수의 파라미터로 선택한 숫자의 제곱을 뺀 값을 전달해주면 됩니다. 또한 이미 계산한 값을 배열에 저장함으로써 시간을 단축시킬 수 있습니다. 아래는 전체 코드입니다. #include using nam..

[백준 16986번] 인싸들의 가위바위보 (C/C++)

https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 인싸들의 가위바위보 문제는 백트래킹을 이용하여 해결할 수 있습니다. 백트래킹은 next_permutation 함수를 사용하여 수행할 수 있습니다. 손동작 수가 N개일 때, 1 ~ N으로 이루어진 순열의 각 경우의 수에 대해 게임을 진행하면 됩니다. 아래는 전체 코드입니다. #include using namespace std; int table[9][9]; int b[20], c[20]; ..