[Algorithm] 가능한 모든 경우의 수를 시도하는 순진한 알고리즘, Broute Force?

이번글은 가능한 모든 경우의 수를 시도하는 알고리즘 Broute Force에 대해 알아보겠습니다.

 

 

1. Broute Force

Brute Force 알고리즘은 무차별 대입 공격으로 가능한 모든 경우를 시도하는 순진한 알고리즘입니다. 가능한 모든 경우를 시도하기 때문에 완전 탐색 알고리즘입니다. 직관적이고 명확한 알고리즘으로 답을 확실하게 알 수 있지만 input이 크면 비효율적이라는 단점을 갖고 있기 때문에 작은 경우에만 효율적입니다. 

 

Brute Force알고리즘으로 문제를 해결하는 과정은 다음과 같습니다. 이전 포스팅에서 다뤘던 순차 탐색도 Brute Force알고리즘을 이용하여 문제를 푸는 방식입니다. 선형 구조를 모두 탐색하는 방법 중 이전 포스팅에 다뤘던 선형 탐색(순차 탐색)도 Brute Force 알고리즘을 이용하여 푸는 방식입니다. 비선형 구조를 모두 탐색하는 방법인 BFS(넓이 우선 탐색), DFS(깊이 우선 탐색)도 Brute Force알고리즘을 이용하여 푸는 방식입니다.

 

2. Broute Force 문제 풀어보기

2.1. 한수(백준[1065])

 

1065번

한수는 각 자리수들이 등차수열을 이루는 것을 말합니다. 1자리인 경우 1,2,3,...,9이므로 수들을 따로 비교할 수 없어서 모두 한수가 됩니다. 2자리인 경우 구할 수 있는 공차가 1개밖에 없으므로 한수로 인정됩니다. 즉, 99 이하의 숫자들은 모두 한수입니다. 

 

3자리 이상인 경우부터는 각 자릿수의 차이가 같은지 확인합니다!

 

def hansu_fun(n):
    
    hansu = 0
    
    for n in range(1, n+1) :
        if n <= 99 : # 1부터 99까지는 모두 한수
            hansu += 1 
        
        else :     
            nums = list(map(int, str(n))) 
            
            # 1000보다 작거나 같기 때문에 인덱스값을 0, 1, 2로 설정하여 비교 
            if nums[0] - nums[1] == nums[1] - nums[2] : #등차수열 확인
                hansu+=1
    return hansu
           

 

2.2. 블랙잭(백준[2798])

2798번

입력 리스트 내 모든 값을 다 더해서 21은 넘지 않고 최대한 가깝게 만들기 위해 모든 경우의 수를 확인합니다. 

n, m = map(int, input().split())
arr = list(map(int, input().split()))

def black(n,m,arr):
  result = 0

  for i in range(n):
      for j in range(i + 1, n):
          for k in range(j + 1, n):
              if arr[i] + arr[j] + arr[k] > m:
                  continue
              else:
                  result = max(result, arr[i] + arr[j] + arr[k])
  return result
  
print(black(n,m,arr)

 

2.3. 일곱난쟁이(백준[2309번])

2309번

일곱 난쟁이들 중 2명씩 빼면서 키를 합해서 100이 되는 모든 경우의 수를 확인합니다. 모든 경우를 확인한 후 일곱 난쟁이가 아닌 다른 2명을 return 받아 제외시킵니다. 

def incorrect_person(height): 
              
    for i in range(len(height)):
        
        for j in range(i+1,len(height)):
            
            sum_height = sum(height)-height[i]-height[j]
            
            if sum_height == 100:
                
                return height[i], height[j]
            
                
height_lst = []

# 입력 받기 
for i in range(9):
    height_lst.append(int(input()))
    
height_lst.sort()  # 정렬 
            
incorrect_person_height = incorrect_person(height_lst)

for height in height_lst:
    if height not in list(incorrect_person_height):
        print(height)

이때, 주의할 점이 있습니다. 저는 처음에 일곱 난쟁이에 속하지 않는 다른 2명을 제외할 때 remove 메소드를 사용했습니다. (아래 코드 참고)

for height in height_lst:
	if height in incorrect_person_height:
		height_lst.remove(height)

 

하지만 for문을 사용할 때 remove 메소드를 사용하는 것은 주의해야 합니다. 아래 결과처럼 for문 안에서 remove 메소드로 모든 값을 빼려고 할 때 2,4는 빠지지 않죠?

remove사용 시 주의점

 remove는 원본 데이터도 바뀌기 때문입니다. for문 동작 과정을 생각해보면 i가 0일 때는 [2, 3, 4, 5]가 되고 i가 1이면 [2, 3, 4, 5]에서 1번째에 위치하는 3이 삭제됩니다. 2는 건너뛰기 때문에 원하는 대로 동작하지 않는 것이었습니다. 따로 리스트를 복제하고 사용해야 합니다.  

lst = [1,2,3,4,5]
for i in lst[:]:  # lst를 복제하는 형태로 사용 
  print(i)
  lst.remove(i)
print(lst)

# copy메소드로 복제하여 사용 
lst = [1,2,3,4,5]

lst_copy= lst.copy() 

for i in lst:
  print(i)
  lst_copy.remove(i)
print(lst_copy)

remove 뿐만 아니라 insert와 같은 원본 데이터를 훼손하는 동작을 하는지 생각하여 적용해야 합니다.