Brute Force Algorithm과 시뮬레이션

구현 능력을 보는 대표적인 사례

brute force ( 완전 탐색 ) 과 simulation ( 시뮬레이션 )

 

시뮬레이션

문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠뜨리지 않고 코드로 옮겨 마치 시뮬레이션 하는 것과 같은 모습을 그리는 것입니다.

 

- 예시
메신저로 대화할 때, 아래의 조건을 충족해야 한다.
1) 아이디는 닉네임, 소속이 담긴 배열이여야 한다.
2) 소속은 false, true, null 중 하나
3) 소속이 셋 중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 모두 X로 표시
4) 아이디와 닉네임은 길이를 2진수로 바꾼 뒤, 바뀐 숫자를 더함
5) 닉네임과 대화 내용은 공백 : 공백 으로 구분 [ ex. 'blue', 'Green', 'null' : hello. ]

이러한 과정들을 소스코드로 옮겨 담는 것입니다.

 

 

 

Brute-Force Algorithm (BFA)

순수 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 무차별 대입 방법입니다.

 

따라서 Brute Force를 사용한다는 것은 최적의 솔루션이 아니라는 것을 의미하기도 합니다.

 

공간복잡도, 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하기 때문입니다.

 

그렇다면 브루트 포스 알고리즘을 왜 사용할까요?

 

 

BFA 사용하는 경우

1. 프로세스를 높이는데 사용하는 다른 알고리즘이 없을 때
2. 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

[ 예시 : 어떤 문서 중 'park' 란 문자열을 찾아야 한다고 가정 ]
문서는 사전처럼 정렬되어 있지 않기 때문에, 문서에 있는 모든 단어 들을 반복해서 비교해야합니다.
그래서 시간 복잡도는 O(n) 이 됩니다.

이처럼 브루트 포스 알고리즘은 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법입니다.
그러나 데이터 범위가 점점 커질수록 상당히 비효율적입니다.
따라서 프로젝트 규모가 커진다면 더 효율적인 알고리즘을 사용해야 할 것입니다.

 

BFA는 어디서 사용하고 있을까?

반복문을 통해 범위를 줄이지 않고 하나하나 비교하는 것은 Brute Force 를 활용한 Algorithm입니다.

 

 1. 순차 검색 알고리즘

 

배열 안에 특정 값이 존재하는 0번 인덱스부터 차례로 검색

 

2. 문열 매칭 알고리즘

 

[ 길이가 n인 전체 문자열 ] 과 [ 길이가 m인 문자열 ] 을 비교해

길이가 m인 문자열 패턴을 포함하는지를 검색합니다.

 

3. 선택 정렬 알고리즘

 

 전체 배열을 검색해 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지

현재 요소보다 더 작거나 큰 요소를 교환하는 정렬 알고리즘입니다.

 

4. 그 밖의 Brute Force 활용 알고리즘

 - 버블 정렬

 - BFS, DFS

 - DP