Subset sum1 9. Backtracking ㅣ Subset sum 문제 Backtracking ? 기존에 알아보았던 Divide＆conquer, Dynamic programming 그리고 나중에 알아볼 Greedy 등의 알고리즘은 문제를 효율적으로 풀기 위해 사용했지만, Backtracking은 효율성보단 정확성에 조금 더 초점에 둔 알고리즘이다. Backtracking은 해를 찾는 도중 해가 아니어서 막히면, 이전으로 되돌아가서 다시 해를 찾아가는 기법인데, 미로찾기 예제를 들어서 조금 더 자세히 설명해보겠다. ㆍn x n 미로를 나타내는 이차원배열 M 설정. ㆍM[i][j] = 1 이면 길이고, 0이면 장애물이라고 가정. ㆍ오로지 길로만 가야하며, 아래쪽과 오른쪽에 이웃한 길로만 갈 수 있다고 가정. ㆍM[0][0]에서 출발해 M[n-1][n-1]로 도착해야 탈출 성공!.. 2021. 8. 12. 이전 1 다음
