완전 탐색과 문제풀이 (프로그래머스)

완전탐색 

무식해 보여도 사실은 최고의 방법일 때가 있지요.

가능한 모든 상황을 조사해 문제를 풀어보세요.

 

▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 바로 모든 경우의 수를 넣어보는 것으로 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.

▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.

▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드

 

▷ 완전 탐색 방법

1. Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
2. 비트마스크
   1. 비트를 이용한 기법으로써 알고리즘보다는 테크닉 중 하나로써, 정수의 이진수 표현을 활용한 기법
3. 순열 : 순열의 시간 복잡도는 O(N!)
   1. 원소를 순서대로 한 줄로 세우는 방법 (중복 x) { 1. 단순하게 중첩루프, 2. 재귀호출, 3.next_permutation }
4. 백트래킹
   1. DFS에 가지치기를 통해 가도되지 않는 루트를 고려하지 않고 탐색하는 완전탐색 기법 (N-Queen, 
5. BFS (너비우선탐색)

  위의 5가지 방법을 이용한 완전탐색 방법 모두를 익히는 것을 추천

  모든 경우의 수를 탐색하는 방법은 문제를 접했을 때 가장 쉬운 방법이지만, 기초라고도 할 수 있다.

  그리고 문제에서 제한조건과 위의 몇 가지 SKILL을 추가하여 푼다면 문제 해결 시간을 크게 향상 시킬 수 있다. 

=> 모든 알고리즈 문제를 풀 때 시간 복잡도와 공간 복잡도를 생각하면서 풀기 바란다. 

 

프로그래머스 완전 탐색 문제

1번.(Level1) 모의고사

코딩테스트 연습 - 모의고사

# BF_1.py
answers	= [1, 2, 3, 4, 5]  # [1]
answers1 = [1, 3, 2, 4, 2]  # [1,2,3]


def solution(answers):
    solve = [[1, 2, 3, 4, 5], [2, 1, 2, 3, 2, 4, 2, 5], [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]
    answer = [0, 0, 0]
    re_value = []
    for i, n in enumerate(answers):
        if solve[0][i % 5] == n:
            answer[0] += 1
        if solve[1][i % 8] == n:
            answer[1] += 1
        if solve[2][i % 10] == n:
            answer[2] += 1
    for i, m in enumerate(answer):
        if m == max(answer):
           re_value.append(i+1)
    return re_value


print(solution(answers1))

 

2번.(Level2) 소수 찾기

코딩테스트 연습 - 소수 찾기

이거는 라이브러리를 사용하면 너무 쉽지만

직접 구현하려니 어려웠다.

# BP_2.py
from itertools import permutations
numbers = "17"	 # "011"


def solution(numbers):
    from itertools import permutations
    pick = set()
    answer = 0

    # 소수 찾기
    def find_Prime(num):
        if num < 2:
            return False

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

    # 재귀 함수
    def permutate(base, array):
        if base:
            pick.add(int(base))

        for i, s in enumerate(array):
            permutate(base + s, array[:i] + array[i + 1:])

    for i in range(len(numbers)):
        # print(numbers)

        # 파이썬 라이브러리
        # temp = permutations(numbers, i+1)
        # for n in temp:
        #     pick.add(int(''.join(n)))

        # 재귀
        permutate("", list(numbers))

    print(pick)
    for n in pick:
        if find_Prime(n):
            answer += 1
    return answer


print(solution(numbers))

 

3번.(Level2) 카펫

코딩테스트 연습 - 카펫

이번 문제는 쉬웠다. 

# BP_3.py
brown = 24     # 8     24
yellow = 24      # 1     24
# return [4,3] [3,3] [8,6]
# brown 갯수 - 4 = yellow 모서리 수 = y의 갯수의 약수 중 (앞 + 뒤) * 2
# 출력 중 앞이 더 커야함 [앞 +2, 뒤 +2]


def solution(brown, yellow):
    yellow_edge = brown - 4
    for i in range(1, int(yellow ** 0.5)+1):
        if yellow % i == 0:
            if (i + yellow // i)*2 == yellow_edge:
                return [(yellow // i) + 2, i + 2]


print(solution(brown, yellow))


# 번외
def solution_1(brown, yellow):
    import math
    ans=((brown-4)+math.sqrt((brown-4)**2-16*yellow))//4
    return [ans+2, yellow//ans+2]