![]()
백트래킹현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 - 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘 - 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제 - 모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것 - 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음 - 만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감 ‼️ 주의재귀로 푸니까 스택 메모리 제한을 확인해야된다.N이 클 경우 백트래킹을 적용하면 시간초과 난다. 백트래킹 알고리즘의 시간 복잡도는 주로 문제의 조건에 따라 달라진다. 선택할 수 있는 숫자가 N개이고, 수열의 길이가 M이므로 총 경우의 수는 O(N^M)다. 따라서 최악의 경우에는 지수 시간이 소요..
![]()
https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 풀이과정 처음으로 set을 사용해봤다. map을 사용하지 않고, set을 사용한 이유는 중복되는 값을 삭제해야 되기 때문이다. 이것이 set의 가장 큰 메리트라고 생각한다. 좋은 문제인 것 같다! next_permutation - 현재 나와있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구한다. - 사전식으로 정렬한다. - 사용 전에 꼭 sort하고 시작해야 한다. #include #include #include #include #include using namespace std; ..
