개요이전 게시글에서 백트래킹 기법을 사용해 배열을 통해 순열과 조합을 구현했다. 다만, 백트래킹을 사용한 순열과 조합의 구현은 복잡하기 때문에 실수할 여지가 있다. 이번 게시글에서는 algorithm 헤더파일의 next_permutation과 prev_permutation을 통해 순열과 조합을 쉽게 구현하는 방법을 알아보자.next_permutation로 순열 구하기next_permutationbool std::next_permutation(BidirIt first, BidirIt last) // STL 컨테이너 사용 가능bool std::next_permutation(T *first, T *last) // 배열 사용 가능[first, last) 범위에서 다음 수열 결과를 인수로 전달된 컨테이너 or 배..

백트래킹이란?백트래킹은 가능한 모든 경우의 수를 따라 들어가면서 탐색하는 알고리즘이다.답이 될 수 없는 경우 더 이상 탐색하지 않고 뒤로 돌아간다.주로 재귀 함수를 사용해 구현한다.시간 복잡도는 O(N!)으로 매우 큰 편이다. 그렇기 때문에 백트래킹 관련 문제에서는 N이 작게 주어진다. 백트래킹 구현에서 가장 중요한 점은 방문 상태 변화 & 상태 원상 복구 두 가지다. 로직을 작성할 때 항상 염두에 두자.백트래킹과 순열, 조합순열과 조합을 구할 때, 가능한 모든 경우의 수에 대해 검사하기 때문에 백트래킹을 사용할 수 있다.아래에서 설명하는 순열과 조합은 오름차순으로 정렬된 집합을 기준으로 한다. 아래 코드에서 공통적으로 나오는 변수들은 다음을 나타낸다.isUsed[i]: i번째 수가 사용되었는 지 여부를..