[python][프로그래머스] 카펫, 소수 찾기, 피로도 (완전탐색 문제)

[완전탐색 깨달음]

1. 완전탐색은 무식하게 모든 상황을 돌려보는 유형이기 때문에 단순하게 생각하는 게 도움이 됨
2. 대신 시간복잡도가 높은 경우가 많으니 for loop을 돌릴 때 range 설정 잘하기

 

1. 카펫 (https://school.programmers.co.kr/learn/courses/30/lessons/42842)

(레벨 2)

• for loop을 두 번 돌려서 전체 블럭의 개수 (yellow + brown)의 모든 약수를 구하는 방식을 썼었는데, 시간 초과가 나와서 다른 방식을 채택함
• 1에서 int(yellow ** 0.5)까지 for loop을 돌려 가능한 모든 세로 길이 탐색
  • int(yellow ** 0.5)를 사용하는 이유는 세로 <= 가로 이기 때문에 int(yellow ** 0.5)가 정수가 될 때만 길이가 +1 됨

yellow	yellow**0.5	int(yellow**0.5)	가능한 yellow 크기
1	$$ \sqrt{1} $$	1	[1, 1]
2	$$ \sqrt{2} \approx 1.414 $$	1	[2, 1]
3	$$ \sqrt{3} \approx 1.732 $$	1	[3, 1]
4	$$ \sqrt{4} $$	2	[4, 1], [2, 2]
6	$$ \sqrt{6} \approx 2.449 $$	2	[6, 1], [2, 3]
9	$$ \sqrt{9} $$	3	[9, 1], [3, 3] *세로 = 2는 나눠 떨어지지않음

• 그 중 약수가 되는 가로를 찾은 후 brown의 면적과 같아지는지 확인 후 맞다면 [가로, 세로] return

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

---

2. 소수 찾기 (https://school.programmers.co.kr/learn/courses/30/lessons/42839)

(레벨 2)

1. itertools의 permutations 사용해 for loop을 돌려 모든 조합 찾기
2. 소수 판별 후 카운트 return

from itertools import permutations
def solution(numbers):
    def is_prime_num(number):
        if number <= 1:
            return False
        
        for j in range(2, number):
            if number % j == 0:
                return False
        return True
        
    perm = []
    count = 0
    for i in range(1, len(numbers)+1):
        perm.extend(list(map(lambda x: int(''.join(x)), permutations(numbers, i))))
    
    for p in set(perm):
        if is_prime_num(p):
            count += 1
    
    return count

---

3. 피로도 (https://school.programmers.co.kr/learn/courses/30/lessons/87946)

(레벨 2)

• DFS로 풀 수도 있겠다 싶어서 구현해봤는데 내 실력 부족인지 테케의 답이 2까지밖에 안나와서 기본적인 완전 탐색으로 눈을 돌림
• 아래는 사용한 완전탐색 방법

1. itertools의 permutations를 사용해 나올 수 있는 모든 순서 조합을 뽑음
2. 이중 for loop을 돌려 curr (현재 피로도 = k)가 최소 필요 피로도보다 높으면 curr을 업데이트 시켜준 뒤 count += 1
3. count > flag면 flag를 업데이트 해주는 방식으로 품

 

[DFS] (틀린 코드)

def solution(k, dungeons):
    def dfs(i, curr, count):
        visited[i] = 1
        print(dungeons[i], curr, count)
        for j in range(len(dungeons)):
            if visited[j] == 0 and curr - dungeons[i][1] >= dungeons[j][0]:
                curr -= dungeons[i][1]
                count += 1
                dfs(j, curr, count)
        return count
    
    visited = [0] * len(dungeons)
    curr = k
    count = 0
    for i in range(len(dungeons)):
        if visited[i] == 0 and curr >= dungeons[i][0]:
            count = dfs(i, curr, count)
    
    return count

 

[이중 for loop]

from itertools import permutations

def solution(k, dungeons):
    arr = list(permutations(dungeons))
    
    
    flag = 0
    for i in range(len(arr)):
        curr = k
        count = 0
        for j in range(len(dungeons)):
            if curr >= arr[i][j][0]:
                curr -= arr[i][j][1]
                count += 1
        if count > flag:
            flag = count
            
    return flag