반응형 백트래킹2 [알고리즘&코딩테스트] 완전 탐색(Brute Force) 완전 탐색(Brute Force) · 문제를 해결하기 위해 확인하는 모든 경우를 탐색하는 방법이다 - 정답은 무조건 구하는 치트키 · 백 트래킹을 사용해야 하는 상황을 해결한다. · 모든 코딩테스트 문제에게 기본적으로 접근해 봐야 한다. · 장점: 부분점수를 얻기 좋다. · 단점: 전부 탐색하기 때문에 일반적으로 시간 복잡도가 높다. 코딩테스트에 나오는 완전 탐색 문제 종류 · 4가지: (중복없이 or 중복을 허용해서) N개 중 M개를 (고르기 or 순서 있게 나열하기) · 완전 탐색은 함수 정의가 50% // Recurrence Function (재귀 함수) // 만약 M 개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것! // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건.. 2022. 1. 4. [알고리즘] 백트래킹 문제 - Sum of Subsets 백트래킹 문제 - Sum of Subsets 백트래킹(Backtracking) 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻한다. 즉, 탐색하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 백트래킹이라는 이름이 붙었다. Sum of Subsets 백트래킹을 사용하여 해결할 수 있는 문제 중 Sum of Subsets이 있다. Sum of Subsets은 집합 w의 부분집합 중 그 합이 숫자 K와 같은 부분 집합들을 찾는 문제다. 이때, 집합에 음의 값과 중복 값은 없다고 가정한다. 예제를 통해 문제를 이해해보자. 집합 w는 w₁ = 2, w₂ = 10, w₃ = 13, w₄ = 17, w₅ = 22, w₆ = 42 이다. K = 52일때, K와 값이 같은 집합 w의 부분 .. 2021. 1. 1. 이전 1 다음 반응형
