재귀함수 사용 시 코드 실행시간을 단축하는 방법 (C++)
재귀 문제를 풀면서 분명 같은 로직인데 실행시간이 많게는 10배이상 차이나는 것을 보았다. https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 14889번 문제는 N제한이 20이하이므로 순열을 사용하여 스타트팀과 링크팀으로 나눈다면 시간복잡도가 최대 20! = 2,432,902,008,176,640,000 이 되어버리기 때문에 재귀(백트래킹)를 사용하여 풀어야한다. void solve(vector a, vector b, int idx) { if (idx == n + 1..
2023. 7. 14.