숨막히는 알고말고/개념 정리 (2) 썸네일형 리스트형 순열, 조합 알고리즘 (DFS-Backtracking) c++에는 algorithm 헤더에 순열을 구하는 next_permutation() 함수가 존재한다. 문제에 순열이나 조합이 나오면 이 함수로 쉽게 구할 수 있는데, 문제는 이 함수는 시간복잡도가 커서 N값이 커지면 시간 초과가 나는 것이다. BackTracking 그래서 순열, 조합을 다른 방식으로 푸는 방법을 찾았는데, 바로 백트래킹을 사용하는 것이다. 💡 백트래킹은 어떤 노드의 유망성, 즉 해가 될만한지 판단하고, 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가 다음 자식 노드로 가는 방식이다. 순열 구하기 Backtracking과 visit 배열을 사용하여 구현할 수 있다. (코드에 설명 첨부) #include #include #include #define MAX 5 // 1부터 5까지 .. [Algorithm] Dynamic Programming 🤔 동적 프로그래밍(Dynamic Programming) 알고리즘을 짤 때, 보통 분할 정복 기법(Divide-Conquer)을 사용하는 경우가 많다. 분할 정복 기법은 큰 문제를 작은 여러 개의 문제로 나눠 푸는 기법인데, 작은 문제들을 풀다 보면 같은 문제들을 반복해서 푸는 경우가 생기게 된다. 동적 프로그래밍(Dynamic Programming)은 이런 문제들을 매번 다시 계산하지 않고, 테이블을 사용해 계산한 값을 저장해두었다가 재사용하는 기법이다. (쉽게 생각하면, 점화식을 생각하면 된다.) 분할 정복 기법(Divide-Conquer)은 한 문제를 겹치지 않는 부분 문제들로 분할하여 해당 문제들을 재귀적으로 해결한 후, 각각의 결과를 다시 결합하여 원래의 문제를 해결한다. 동적 프로그래밍(Dyn.. 이전 1 다음
