끄적끄적

이 글에서 우리는 완전 탐색 알고리즘과 이것의 장단점에 대해 다룹니다. 완전 탐색 알고리즘은 다음과 같은 장단점을 갖고 있습니다:

• 주어진 문제에 대한 가능한 모든 방법을 열거하는 직관적이고 직접적인 문제해결 기술입니다.

• 완전 탐색 알고리즘을 이용하여 일상 생활의 많은 문제를 해결해왔습니다. 예를 들어 최단 경로를 찾기 위해 인근 시장으로 가는 모든 경로를 탐색합니다.

• 선반 공간 등을 최적화하기 위해 모든 가능성을 사용하여 선반에 책을 배열 합니다.

• 사실 일상 생활 활동은 최적 알고리즘도 가능하지만 무차별 대입 방식을 사용합니다.

완전 탐색 알고리즘의 장점과 단점:

장점:

• 완전 탐색 접근 방식은 문제에 대한 가능한 모든 후보 솔루션을 나열하여 올바른 솔루션을 찾는 보장된 방법입니다.

• 일반적인 문제 해결 방법으로, 특정 문제 영역에 국한되지 않습니다.

• 작고 간단한 문제들을 해결하는데 이상적입니다.

• 단순성으로 유명하며 비교 벤치마크 역할을 할 수 있습니다.

단점:

• 완전 탐색 접근 방식은 비효율적입니다. 실시간 문제의 경우 알고리즘 분석은 종종 O(N!) 증가 차수를 초과합니다..

• 좋은 알고리즘 설계보다 문제를 해결하기 위해 컴퓨터 시스템의 성능을 손상시키는데 더 많이 의존합니다.

• 속도가 느립니다.

• 다른 설계 패러다임을 사용하여 구성된 알고리즘에 비해 건설적이거나 창의적이지 않음

결론:

완전 탐색 알고리즘은 모든 영역의 문제에 대한 솔루션을 보장하는 기술입니다. 간단한 문제를 해결하는데 도움이 되며 다른 설계 기술을 평가하는 벤치마크 역할을 할 수 있습니다. 하지만 실행 시간이 많이 걸리며 비효율적입니다.

원문

• Brute Force Approach and its pros and cons - GeeksforGeeks

🗝 키 포인트

• 길찾기 문제가 나온다면 완전탐색을 구현 해야함
• 동,서,남,북 등 이동할 수 있는 경우의 수를 완전탐색
• 완전탐색을 구현하는 대표적인 방법은 BFS, DFS가 있음

DFS 

• 깊이 우선 탐색 , 한 우물을 깊게 판다.
• Stack, 재귀 함수를 통해 구현

 

BFS

• 너비 우선 탐색, 얇고 넓게 본다.
• Queue를 이용하여 구현
• 최단거리를 찾는 경우 효율적

• 장애물, 이동 가능한 범위 등이 있다면 잊지 말고 예외 처리할 것

✏ 예제