[알고리즘] 완전탐색(브루트 포스)

완전 탐색(브루트 포스)

• 모든 경우의 수를 시도하는 방법
• 경우의 수가 매우 많아지는 문제에 대해서는 제한 시간 내에 해결이 힘들 수 있다.

 

완전 탐색을 사용하는 경우

1. 입력으로 주어지는 데이터의 크기가 작은 경우
2. 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있는 경우

 

사용되는 알고리즘 기법

1. 단순 브루트 포스
   • 단순히 반복문과 조건문을 사용하는 방법이다.
   • 난이도가 높은 문제에서 단독으로 사용되는 경우는 거의 없다.
2. 비트마스크(Bitmask)
   • 2진수를 이용하는 컴퓨터의 연산을 이용하는 방법이다.
   • 각 요소가 두 가지 상태만을 가질 수 있을 때 사용한다.
   • 각 원소가 포함되는지 0 or 1(존재하지 않는 경우 or 존재하는 경우) 등으로 구분하여 저장하는 식으로 사용할 수 있다.
3. 재귀 함수
   • 자기 자신을 호출하는 재귀 함수를 사용하는 방법이다.
   • 조건을 만족하면 함수를 호출하고, 아니면 호출하지 않는 식으로  사용할 수 있다.
4. 순열
   • 서로 다른 N개를 일렬로 나열하는 방법을 말한다.
   • 순열에 원소를 하나씩 채워가는 방식으로 사용할 수 있다.
5. BFS/DFS
   • 길 찾기에 주로 사용하는 방법으로, 추가적 연산(장애물 등)이 필요할 때 완전탐색을 병용하기도 한다.
   • 주로 모든 경로를 확인할 때는 DFS, 최단 경로를 확인할 때는 BFS를 주로 사용한다.
   • https://comhwang.tistory.com/19

[알고리즘] DFS/BFS

 

---

완전탐색 문제

 

프로그래머스 Lv1. 최소 직사각형

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

def solution(sizes):
    answer = 0

    list2 = list(map(lambda x: [x[1],x[0]] if x[1]>x[0] else [x[0],x[1]],sizes))
    max_val = [0,0]
    for a,b in list2 :
        if max_val[0] < a :
            max_val[0] = a
        if max_val[1] < b :
            max_val[1] = b
    answer = max_val[0] * max_val[1]
    return answer

 

 

프로그래머스 Lv1. 모의고사

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

def solution(answers):
    answer = []

    students = [[1,2,3,4,5], [2,1,2,3,2,4,2,5], [3,3,1,1,2,2,4,4,5,5]]
    students_answer = [0,0,0]

    for i in range(3):
        for j in range(len(answers)) :
            if answers[j] == students[i][j%len(students[i])] :
                students_answer[i]+=1

    max_value = max(students_answer)
    for i in range(3) : 
        if students_answer[i] == max_value :
            answer.append(i+1)
            
    return answer

 

프로그래머스 Lv2. 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

from collections import deque

def solution(n, wires):

    answer = n

    # {1 : [1,2], 2: [3,4]} 등으로 각 송전탑과 이어진 송전탑의 관계 그래프를 만드는 코드
    graph_arr = [[] for _ in range(n)]
    for x,y in wires :
        graph_arr[x-1].append(y)
        graph_arr[y-1].append(x)
    graph_dict = {i+1 : graph_arr[i] for i in range(n)}

    # 각각의 wire를 끊었을 때 나뉘는 두 전력망 수의 차이를 bfs로 구현
    for x,y in wires :
        # 방문여부와 해당 wire를 끊었을때 한쪽의 전력망 수를 저장할 변수
        visited = [0]*(n+1)
        visited[x] = 1
        cnt=1
        graph_dict[x].remove(y)
        graph_dict[y].remove(x)
        queue = deque([x])

        while queue :
            cur = queue.popleft()
            for nx in graph_dict[cur] :
                if not visited[nx] :
                    queue.append(nx)
                    cnt+=1
                    visited[nx]=1
                    
        if abs(cnt - (n-cnt)) < answer :
            answer = abs(cnt - (n-cnt))

        # 끊었던 wire 복구
        graph_dict[x].append(y)
        graph_dict[y].append(x)

    return answer

 

프로그래머스 Lv2. 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

def solution(word):
    answer = 0
    list_char = ['A', 'E', 'I', 'O', 'U']

    # 문자의 인덱스별 증가하는 양
    # 경우의 수가 AEIOU 에 공백이 있다 : x5+1
    list_up = [781,156,31,6,1]

    # 문자를 하나씩 가져와 계산한 값을 answer에 더해준다.
    for i in range(len(word)) :
        answer+=list_char.index(word[i])*list_up[i]+1

    return answer