[Algorithm] 백트래킹(Backtracking)과 브루트포스(Brute Force)

 

📚

 

안녕하시렵니까앍 - ! (feat. 주우재)

오늘은 백트래킹 알고리즘에 브루트포스 알고리즘을 사알짝 곁들인 글을 가져왔습니다앍 🐓

 

 

---

 

 

백트래킹(Backtracking)

백트래킹(Backtracking)이란, 해를 찾는 도중에 현재 경로의 유망성을 판단하여 해가 될 것 같지 않으면 되돌아가서 다시 해를 찾아가는 기법이다.

백트래킹 알고리즘은 탐색 과정에서 불필요한 경우를 배제하여 실행시간을 단축시키는 특징을 가지고 있다. 즉, 가능한 경우의 수를 순차적으로 시도하다가 조건을 만족하지 않는 경우에 이전 단계로 돌아가 다음 경우를 시도한다. 이러한 과정을 재귀적으로 진행하며 최적의 해를 찾을 때까지 탐색을 진행 !

주로 조합적인 문제나 제약 조건이 있는 문제를 해결하는 데 사용된다. 대표적인 예로는 스도쿠, N-Queen 문제 등이 있다.

 

 

백트래킹 알고리즘의 구조

1. 문제의 해를 표현할 데이터 구조 정의
2. 해를 구하는 데에 필요한 제약 조건 정의
3. 해를 찾기 위해 탐색을 진행하는 함수 구현
4. 현재 상태에서 가능한 다음 단계 탐색, 조건을 만족하는지 확인 (탐색 함수 내)
5. 조건을 만족하지 않는 경우, 이전 단계로 돌아가 다음 경우 시도
6. 최적을 해를 찾았을 때 결과 반환 및 종료

 

브루트포스(Brute Force) 알고리즘

브루트포스 알고리즘은 가능한 모든 경우의 수를 탐색하여 문제를 해결하는 방법이다. 일반적으로 가장 직관적이고 간단한 접근법 중 하나이며, 주어진 문제에 대해 모든 가능성을 시도하여 정확한 해를 찾는다. 예외 없이 100%의 확률로 정답만을 찾는다. 그렇기 때문에 확실하지만 경우의 수가 많은 경우엔 시간이 오래 걸리는 단점이 있다.

 

특히, 그래프 탐색 방법인 순차 탐색, 깊이 우선 탐색, 너비 우선 탐색을 사용하여 브루트포스 알고리즘을 구현할 수 있다. 정리하면, 브루트포스 알고리즘을 적용하는 문제 중 하나로 그래프 문제가 있다는 것이다.

• 순차 탐색 : 선형 구조를 전체적으로 탐색
• 깊이 우선 탐색 (DFS) : 비선형 구조에서 깊이를 우선하여 전체적으로 탐색
• 너비 우선 탐색 (BFS) : 비선형 구조에서 너비를 우선하여 전체적으로 탐색

💡 한 번 더 정리 !@#$~!!!  브루트포스 알고리즘의 종류가 순차 탐색, DFS, BFS인 것이 아니라 그저 브루트포스 알고리즘을 구현하는 데 사용되는 대표적인 방법들 중 일부라는 것 !! 즉, DFS는 브루트포스 알고리즘이라고 할 수 있지만, 브루트포스 알고리즘은 DFS가 아니다.!!

 

 

백트래킹 알고리즘의 특징

😇 잠깐 브루트포스 알고리즘에 깊이 빠져버렸지만, 다시 돌아와 처음 가졌던 의문 !! 백트래킹이랑 브루트포스의 차이점 !!....이 궁금했는데 글을 정리하다 보니 그냥 애초에 개념부터 다르잖아 ㅋ큐ㅠㅠ 그치만,, 백트래킹만의 특징을 써보겠슴다 ㅎㅅㅎ

 

탐색 과정에서 불필요한 경우를 배제하여 실행 시간을 단축시킨다. 조건을 만족하지 않는 경우에는 이전 단계로 돌아가 다음 경우를 시도하여 최적의 해를 찾는다. 시간 단축을 위해(=가능한 경우의 수를 줄이기 위해) 가지치기(Pruning) 기법을 사용한다. 즉, 가지치기를 통해 실행시간을 최적화할 수 있다.

백트래킹 알고리즘은 보통 깊이 우선 탐색을 사용한다. 그리고 일반적으로 재귀적인 방식으로 구현된다. 재귀 호출을 통해 다음 상태로 진행하고, 결과를 확인한 후 다시 이전 상태로 돌아가는 과정을 반복한다.

(브루트포스는 모든 가능한 조합을 탐색하기 때문에 일반적으로 작은 입력 크기에 대해서만 효율적으로 동작.)

 

 

가지치기(Pruning) 기법

여기서 가지치기(Pruning) 기법이 정확히 무엇이냐 !? 어떻게 문제에 적용되는 것이냐 ? N-Queen 문제를 예로 들어 보자.

N-Queen 문제는 N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없게 놓도록 해야 한다. 여기서 백트래킹 알고리즘을 사용하여 가능한 모든 퀸의 배치를 탐색할 수 있다.

 

가지치기를 적용하여 유망하지 않은 경우를 배제하는 예시는 다음 3가지가 있다.

1. 한 행에는 하나의 퀸만 위치할 수 있으므로, 특정 행에 이미 퀸이 배치되어 있다면 다음 행으로 넘어간다.
2. 같은 열에는 2개 이상의 퀸이 위치할 수 없으므로, 특정 열에 이미 퀸이 배치되어 있다면 다음 열로 넘어간다.
3. 대각선 방향으로 퀸이 공격할 수 있으므로, 대각선 방향에 다른 퀸이 이미 배치되어 있다면 다음 위치로 넘어간다.

위 3가지 가지(?)를 침으로써 불필요한 퀸의 배치를 사전에 배제하여 탐색 과정을 효율적으로 진행할 수 있는 것 !!

 

제약 조건과 가지치기 🔎

✔️ 제약 조건(Constraint)은 문제의 조건이나 제약 사항을 나타내는 것이다. 일반적으로 문제를 해결하기 위해 만족해야 하는 조건들을 말함 ! N-Queen 문제에서는 "퀸들은 서로 공격할 수 없어야 한다." 라는 조건이 이 문제의 제약 조건이다. 우리는 이 제약 조건을 만족시키기 위해 알고리즘을 설계하는 것임 ! 즉, 구현할 때 꼭 고려해야 함.

 

✔️ 가지치기(Pruning)는 탐색 과정에서 유망하지 않은, 정답을 도출하는 데에 필요 없는 경우의 수를 배제하여 탐색 범위를 줄이는 것이다. 즉, 앞서 말한 3가지 예시가 사전에 배제하는 가지치기라고 할 수 있는 것이다. 알고리즘의 효율성 향상이 목적임 !

제약 조건은 해당 문제를 해결하기 위해 반드시 고려해야 하는 사항이며, 가지치기는 실행 시간을 줄이기 위해 사용되는 백트래킹의 기법 중 하나인 것이다 ~ 가지치기는 가지들을 "내"가 도출해내야 한다는 것 ㅋㅅㅋ

 

 

---

 

 

이리저리 글이 길어졌다 🫠

개념만 간단히 정리하려 했는데

공부하고 정리하는 과정에 헷갈리는 게 계속 파생되어서 발생함 ㅎㅅㅎ

정리하고 보니 당연한 거였네 ? 머슥 ;;

이제 백트래킹 문제 풀러 가야지 🐕