컴퓨터 공학/알고리즘
[알고리즘] Backtracking / 백트래킹
📕Backtracking이란? 영어 사전에서 backtrack이란 단어를 검색하면 나오는 결과이다. '(방금 왔던 길을) 되짚어 가다' 미로찾기를 한다고 생각해보자, 두갈래 갈림길이 나왔을때 왼쪽으로 가다가 막히면 어떻게 하는가? 다시 갈림길이 있는 곳으로 돌아와서 오른쪽으로 가지 않겠는가? 이것이 바로 백트래킹의 핵심이다. 길이 막혔을 경우 다시 돌아가는 것을 원하는 결과가 나올때까지 반복하는 것이 바로 백트래킹이다. 간간단한 예제를 살펴보자. S = {W1 = 5, W2 = 6, W3 = 10, W4 = 11, W5 = 16} and W = 21 S에 있는 수를 뽑아 W를 만드려고 한다. 이때 생기는 조합은 여러가지가 있다. {W1, W2, W3} , {W1, W5}, {W3, W4} = 21 이러한..
