[Python] 프로그래머스 고득점 kit - 완전 탐색

 

완전 탐색은 그 자체로 알고리즘이 아니며,

완전 탐색을 이용하기 위해 여러 알고리즘 기법들이 사용됨

• Brute-Force
• Bitmask
• 순열
• 백트래킹 (주로 DFS를 이용)
• DFS/BFS

대부분 for문과 if 문을 활용하거나 BFS/DFS를 활용하는 경우가 대부분

순열/조합을 활용해 완전 탐색 문제를 푸는 방법도 꽤 자주 나옴

 

 

순열

재귀적으로 순열 구현

def permutation(arr, r):
	result = []
    
    def permute(p, index):
    	if len(p) == r:
        	result.append(p)
            return 
        
        for idx, data in enumerate(arr):
        	if idx not in index:
            	permute(p + [data], index + [idx]) # 재귀
    permute([], [])
    return result
    
 for r in permutation(['A', 'B', 'C', 'D'], 2):
 	print(r)

 

itertools.permutations 사용해서 구현

from itertools import permutations

data = "ABCD"
result = permutations(data, 2)

for r in result:
	print(r)

# --- Result ---
'''
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'A')
('B', 'C')
('B', 'D')
('C', 'A')
('C', 'B')
('C', 'D')
('D', 'A')
('D', 'B')
('D', 'C')
'''

 

+ 조합

def combination(arr, r):
	result = []
    
    def combinate(c, index):
    	if len(c) == r:
        	result.append(c)
            return
            
        for idx, data in enumerate(arr):
        	if idx > index:
            	combinate(c + [data], idx)
    
    combinate([], -1)
    return result
    
 for r in combination(['A', 'B', 'C', 'D'], 2):
 	print(r)

 

from itertools import combinations

data = "ABCD"
result = combinations(data, 2)

for r in result:
    print(r)
    
# --- Result ---
'''
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'C')
('B', 'D')
('C', 'D')
'''

 

 

완전 탐색 시간 복잡도

비트마스크 > DFS/BFS > Brute-Force > 재귀함수 > 순열 > 백트래킹

알고리즘 종류	시간복잡도
Brute-Force	O(n^m)
Bitmask	O(2^n*n)
순열	최악의 경우 O(n!)
재귀함수	O(n)
DFS/BFS	O(V+E)

 

💡 소수 찾기 (Lv.2)

 

내 코드

from itertools import permutations

def is_prime(n):
    if n < 2: # 0, 1은 항상 소수가 아님
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
        
    return True

def solution(numbers):
    answer = 0
    answer_list = []
    
    for i in range(1, len(numbers)+1):
        result_list = permutations(numbers, i)
        for result in result_list:
            answer_list.append(int("".join(result)))
    
    answer_list = set(answer_list)
    print(answer_list)
    
    for num in answer_list:
        if is_prime(num):
            answer += 1
            print(num)
    
    return answer

 

📌 join 함수

리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 변환하는 함수

• ''join(리스트) ex. ''.join(['a', 'b', 'c'])  → abc
• '구분자'.join(리스트) ex. '_'.join(['a', 'b', 'c']) → a_b_c 

다른 풀이

 

 

 

[ 풀면서 느낀 점 & 깨달은 점 ]

• 튜플에 있는 원소를 어떻게 합칠지 고민이었는데 → join 함수로 해결
• 소수 찾기에서 한자리수는 어떻게하지가 고민이었는데 range(2, 9)로 하는게 아니라 range(2, x) (여기서 x는 해당 숫자)를 의미

 

💡 테트로미노 (BOJ 14500번)

 

https://www.acmicpc.net/problem/14500