완전탐색 (Brute Force)

브루트 포스 알고리즘(Brute-force algorithm)이라고도 불리며 가능한 모든 경우를 탐색해보는 알고리즘

모든 경우를 다 탐색하는 알고리즘이기에 100%의 정확도와 최악의 시간 복잡도를 가진다. 따라서 주어진 데이터가 매우 적을 때만 사용 가능하다.

대부분 다음 3가지 방법으로 풀 수 있다.

1. for문과 if 문을 활용
2. BFS/DFS를 활용 (+백트래킹)
3. 순열/조합을 활용

이 문제를 완탐으로 풀어야하는 경우를 체크해보기 위해서는 문제를 많이 풀어보는 것이 중요하다.

프로그래머스 고득점 kit

Lv 1. 최소직사각형

명함을 수납할 수 있는 가장 최적의 지갑 사이즈를 찾아야 하는 문제다. 포인트는 일단 가장 큰 값이 가로로 고정되면 세로로 들어갈 데이터는 가로, 세로 값 중 작은 값의 최댓값으로 넣어주면 된다.

def solution(sizes):
    answer = 0
    
    # 가장 큰 값으로 가로 고정
    max_val = 0
    for w,h in sizes:
        max_val = max(max_val, w, h) 
    
    # 세로는 가로, 세로 값 중 작은 값의 최댓값으로
    height = 0
    for w,h in sizes:
        height = max(height, min(w,h))
    
    answer = max_val * height
    return answer

Lv 1. 모의고사

단순히 값을 비교해서 맞았으면 count해준 뒤, 최고점인 학생 인덱스를 answer에 담아서 리턴해주면 되는 문제. 간단했다.
값을 비교해줄 때 i % len(배열) 이렇게만 적어준다면 끝!

def solution(answers):
    answer = []
    
    s1 = [1, 2, 3, 4, 5]
    s2 = [2, 1, 2, 3, 2, 4, 2, 5]
    s3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    
    count = [0, 0, 0]
    for i, v in enumerate(answers):
        
        if s1[i % len(s1)] == v:
            count[0] += 1
        if s2[i % len(s2)] == v:
            count[1] += 1
        if s3[i % len(s3)] == v:
            count[2] += 1
    
    max_score = max(count)
    
    for i,v in enumerate(count):
        if v == max_score:
            answer.append(i+1)
    return answer

Lv 2. 소수찾기

가능한 모든 경우의 수를 순열로 구해줘도 괜찮은 입력 수(7)였다. 따라서 permutaions 라이브러리를 import해서 모든 경우의 수를 뽑아낸 뒤 숫자로 바꿔 중복 제거( set 사용)했다.

소수판별 알고리즘은 자신의 제곱근까지만 판단해도 소수인지 판별할 수 있으므로 그렇게 함수를 짰다. checkPrime 함수는 0, 1은 무조건 소수가 아니라고 판단하는 것까지 넣어주어야 제대로 작동한다!

from itertools import permutations

def checkPrime(num):
    if num == 0 or num == 1:
        return False
    for i in range(2, int(num ** 0.5)+1):
        if num % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    
    data = list(numbers)
    
    case = []
    for i in range(1, len(data)+1):
        case += list(permutations(data, i))
    
    nums = []
    for i in case:
        nums.append(int("".join(i)))
    
    nums = set(nums)
    
    for i in set(nums):
        if checkPrime(i):
            answer += 1
    
    return answer

Lv 2. 카펫

노란색 격자(yellow)의 약수가 w x h이다.
갈색 격자(brown)에서 4를 빼고 2로 나눈 요소를 가지고 w, h가 될 수 있는 경우의 수를 체크해주면 된다.
최종적으로 리턴해야 하는 값은 카펫의 가로, 세로 길이이므로 +2를 해주었고, 무조건 가로가 더 크거나 같아야 한다고 했으므로 순서를 맞춰서 넣어주었다.

def solution(brown, yellow):
    answer = []
    
    number = (brown - 4) // 2
    for i in range(1, (((brown - 4) // 2) // 2) +1):
        if i * (number-i) == yellow:
            answer.append(number-i+2)
            answer.append(i+2)
    return answer

Lv 2. 피로도

순열을 고려해야하는 최대 입력 수가 8이므로 바로 모든 경우의 수 다 계산했다.

현재 피로도 k가 최소 피로도[0] 이상인 경우 던전 탐험을 진행하여 피로도를 소모 피로도[1]만큼 감소시켰다.

만약 돌 수 있는 던전 수가 최대 던전 수만큼 나오는 경우의 수가 등장했다면 반복문을 그만 돌게 만들었다. (이 부분 없어두 시간초과는 나지 않는다~!)

from itertools import permutations
def solution(k, dungeons):
    answer = 0    
    
    cases = []
    for i in range(1, len(dungeons)+1):
        cases += list(permutations(dungeons, i))
    
    origin_k = k
    
    for case in cases:
        count = 0
        k = origin_k
        for i in range(len(case)):
            if k >= case[i][0]:
                k -= case[i][1]
                count += 1
        answer = max(count, answer)
        if answer == len(dungeons):
            break
        
    return answer

Lv 2. 전력망을 둘로 나누기

BFS 복습

BFS는 모든 경로에 대한 동시 탐색이 가능하며 최대 경로를 몰라도 사용할 수 있다. BFS의 경우 큐를 사용하는 경우가 대부분이다. 방문했던 노드를 체크해야 살펴볼 노드를 큐에 넣을 때 중복이 발생하지 않기 때문이다.

python에서는 큐를 list 타입으로 사용하는 경우가 많은데, 살펴본 노드를 제거할 때, list.pop() 함수를 사용하는 경우 시간 복잡도가 O(N)이라 시간 복잡도 면으로 매우 비효율적이다.

따라서 collections 라이브러리의 deque을 사용하여 시간을 절약하는 편이 좋다. deque는 양 끝에서 접근이 가능하며, append(), extend(), pop(), popleft() 등의 함수를 통해 자료를 넣고 뺄 수 있다.

# BFS
from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)

#N:정점개수 M:간선개수
N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
start_node = input('검색을 시작할 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)

bfs(start_node)

문제 풀이

최대 경우의 수가 적기 때문에 전체 경우를 살펴봐도 된다. 각각의 그래프를 끊어가면서 정점 1에서 시작하는 그래프가 노드가 몇개인지 체크해주었다. 모든 노드를 체크해야 하므로 BFS 알고리즘을 사용했다.

graph에 양방향으로 간선에 대한 정보를 넣어주었다. BFS는 노드에 접근할 때마다 count 변수를 1씩 증가시켜 해당 그래프가 총 몇개의 노드로 이루어져있는지를 리턴한다.

wires 배열에서 한개씩 끊어가면서 BFS를 돌리면 된다. 두 그래프 간의 노드 수 차이를 계산하기 위해 절댓값 함수 abs()를 사용했다. 최종적으로 가장 작은 노드 수 차이 값을 갖는 경우를 리턴하면 된다. answer의 경우에는 조건에 명시된 최대 노드의 수(100)보다 1 큰 101 로 초기화해주고 시작했다.

from collections import deque
def solution(n, wires):
    answer = 101
    graph = [ [] for _ in range(n+1)]
    visit = [False] * (n+1)  
    
    for x, y in wires:
        graph[x].append(y)
        graph[y].append(x)
    
    
    def bfs(start):
        q = deque()
        visit[start] = True
        q.append(start)
        count = 1
        while q:
            node = q.popleft()
            for i in range(len(graph[node])):
                next_node = graph[node][i]
                if not visit[next_node]:
                    visit[next_node] = True
                    q.append(next_node)
                    count += 1
        return count
    
    for x,y in wires:
        graph[x].remove(y)
        graph[y].remove(x)
        visit = [False] * (n+1)
        result = bfs(1)
        
        answer = min(answer, abs(n-result-result))
        graph[x].append(y)
        graph[y].append(x)
        
    return answer

Lv 2. 모음사전

최대 경우의 수가 많지 않기 때문에 중복 순열을 사용해서 가능한 모든 경우를 만들어낸 뒤 정렬하여 주어진 단어가 몇번째 인덱스인지 반환하면 되는 문제다.
문제에서 인덱스는 1부터 시작하므로 결과값에 +1 해주는 것을 잊지 말자.

중복 순열

파이썬에서 중복 순열은 itertools.product를 사용하여 구현할 수 있다. 문법은 product(배열, repeat=뽑아낼 원소 개수)이다.

정답 코드는 다음과 같다. 각각의 경우를 문자열로 만들어준 뒤 ("".join(case)) 문제에서 주어진 순서로 만들기 위해 정렬한다. 정렬한 뒤 index() 메서드를 사용하여 몇번째 요소인지 리턴해주면 된다.

from itertools import product

def solution(word):
    answer = 0
    
    letters = ['A', 'E', 'I', 'O', 'U']
    cases = []
    for i in range(1, 6):
        cases += list(product(letters, repeat=i))
    
    dictionary = []
    for case in cases:
        dictionary.append("".join(case))
    
    dictionary.sort()
    
    answer = dictionary.index(word) + 1
    return answer