[Python] 완전탐색_카펫(2단계)

EunBi Na·2022년 3월 25일

[Python] 프로그래머스_코딩테스트 고득점 Kit

목록 보기

16/60

링크텍스트

① 완전탐색이란?

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

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

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

1.Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
2.비트마스크
3.순열 : 순열의 시간 복잡도는 O(N!)
4.백트래킹
5.BFS

위의 5가지 방법을 이용한 완전탐색 방법 모두를 익히는 것을 추천합니다!!!
모든 경우의 수를 탐색하는 방법은 문제를 접했을 때 가장 쉬운 방법이지만, 기초라고도 볼 수 있습니다.

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

링크텍스트

문제설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때
카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
-> 세로 <= 가로

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

연습

식을 간소화하게 정리하기

1) a >= b
2) brown = 2a + 2b - 4
3) yellow = (a-2) * (b-2)

--> ab = yellow + brown

풀이

링크텍스트

def solution(brown, yellow):
    answer = []
    total = brown + yellow                  # a * b = total
    for b in range(1,total+1):
        if (total / b) % 1 == 0:            # total / b = a
            a = total / b
            if a >= b:                      # a >= b
                if 2*a + 2*b == brown + 4:  # 2*a + 2*b = brown + 4 
                    return [a,b]
            
    return answer

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

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

처음에는 이중 for문으로 숫자를 하나씩 검사하며 row col 이 brown과 red의 총 갯수 인 것을 리턴하도록 구현했다. 하지만 이 방법은 시간초과가 나고 반례가 존재한다는 것을 알게되었고 그래서 규칙을 찾게 되었다. col 2 + row *2 + 4 가 brown의 갯수가 되면 col+2 , row+2가 카펫의 가로 , 세로가 된다는 것을 이용하여 for문을 red의 절반의 +1 만큼을 돌려 검사하며 구현했다.

def solution(brown, yellow):    
    total = brown + yellow
    for i in range(3, int(total**0.5) + 1):
        if not total % i and (i-2) * ((total//i)-2) == yellow:
            return [total//i, i]