[자료구조] 완전탐색

[LEE-DA-EUN]

• 완전탐색은 어떤 방법인지, 장점, 단점과 함께 설명해주세요.
• 완전탐색의 문제점을 해결하기 위한 기법 중 백트래킹과 가지치기의 차이점은 무엇이며, 각각 어떤 상황에 유용한지 알려주세요.
• 순열 및 조합을 사용하는 문제에서 경우의 수가 많아질 때 시간 복잡도를 줄일 수 있는 방법을 알려주세요.

[JaeJunday]

완전탐색은 가능한 모든 경우의 수를 탐색하는 기법으로 선형/비선형 자료구조에서 접근 가능한 모든 경로를 탐색하는 기법입니다. 장점은 재귀를 사용한 구현 로직이 단순하고 해법을 구하기 쉽다는 점에 있고, 단점은 경로의 수가 많은 경우 재귀를 사용했을때 메모리 오버플로우가 날수있으며 성능이 저하될 가능성이 있다는 점입니다. 백트래킹은 조건에 맞지않는 경로를 조건으로 제거하여 방문한 노드를 더 이상탐색하지 않고 이전경로로 돌아가 다시 탐색하는기법입니다. 가지치기는 불필요한 조건을 미리 제거하여 탐색하는 경우의 수를 줄여 최적화하는 방법입니다. 순열 및 조합을 사용하는 문제에서는 경우의 수가 많아질 때는 중복계산이 많이 일어나는 부분을 찾아서 캐싱하여 사용하거나 가지치기 기법을 사용해서 최대한 경우의 수를 줄여볼 수 있습니다. 또는 연산자체를 비트를 활용해서 가볍게하는 방법도 존재합니다.

[1013115]

• 완전 탐색은 가능한 모든 경우의 수를 탐색하여 문제의 답을 찾는 방법입니다. 모든 경우의 수를 탐색하므로 문제의 해답을 놓칠 확률이 없고 구현이 비교적 단순합니다. 그러나 경우의 수가 많아지면서 탐색에 소요되는 시간이 기하급수적으로 증가하고 시간복잡도가 매우 높아집니다.
• 백트래킹은 모든 경우의 수를 탐색하는 과정에서 더이상 유효한 해를 기대할 수 없는 경로를 발견하면 그 경로를 즉시 포기한고 다른 경로로 이동하는 방식이며 가지치기는 탐색 도중 불필요한 경우를 미리 제거하여 탐색범위를 줄이는 기법입니다. 백트래킹의 경우 대규모 문제를 효과적으로 처리할 수 있고, 가지치기의 경우는 최적의 해답을 찾는데 도움이 되며 효율적인 탐색을 가능하게 합니다.
• 백트래킹을 사용하거나 가지치기를 사용하여 시간 복잡도를 줄일 수 있습니다.

[rimeir]

1. 완전탐색은 가능한 모든 경우의 수를 탐색하여 문제의 답을 찾는 방법입니다. 장점으로는 모든 경우의 수를 탐색하여 정확한 해답을 보장하고 알고리즘의 논리가 단순하고 명확하여 구현이 비교적 쉽다는 점이 있습니다. 단점으로는 경우의 수가 많아지면 탐색에 소요되는 시간이 증가하여 시간복잡도가 매우 높아지는 문제가 발생하여 문제를 시간 내에 해결하기 어려울 수 있다는 점이 있습니다.
2. 완전탐색의 단점을 보완하기 위해 백트래킹과 가지치지 기법을 이용합니다. 백트래킹은 모든 경우의 수를 탐색하는 과정에서 더 이상 유효한 해를 기대할 수 없는 경로를 발견하면 그 경로를 즉시 포기하고 다른 경로로 이동하는 방식입니다. 이를 이용하여 탐색 시간을 단축할 수 있습니다. 가지치기 기법은 백트래킹과 달리 탐색 도중 불필요한 경우를 미리 배제하여 탐색 범위를 줄입니다. 최적의 해답을 찾고 효율적인 탐색이 가능합니다.
3. 백트래킹을 이용하여 탐색하는 과정에서 더 이상 유효한 해를 기대할 수 없는 경로를 발견하면 그 경로를 즉시 포기하고 다른 경로로 이동하는 방식으로 시간 복잡도를 줄일 수 있습니다.