[python] 단계별로 풀어보기 - 11단계

 

 

브루트 포스 알고리즘(완전 탐색 알고리즘): 가장 간단한 알고리즘. 모든 경우의 수를 검사

하나하나 다 검사하다보니 시간적인 측면에서는 비효율적이지만 정확도가 100%임.

​

암호학에서는 가장 확실한 방법으로 통용

(ex) 숫자로만 구성된 4자리수 비밀번호를 풀 때, 0000 ~9999까지 모두 입력해보는 것)

​

+ 만들기 쉬운 알고리즘

+ 문제의 복잡도에 매우 민감

 

 

 

 

---

11-1) 백준 2798번: 블랙잭

 

arr =[]

a, b = map(int, input().split())
arr = list(map(int, input().split()))
result = 0
           
for i in range(a):
    for j in range(i+1, a):
        for k in range(j+1, a):
            if arr[i] + arr[j] + arr[k] > b:
                continue
            else:
                result = max(result, arr[i]+ arr[j]+ arr[k])
print(result)

 

3개를 뽑아와야하니까 브루트 포스 알고리즘에 속한 만큼 그냥 반복문 3번 돌리기

합이 b보다 크지 않아야한다는 점 유의해서 품!

크지 않다면 result에 일단 저장해두고, 그중 가장 큰 값이 result

 

 

 

 

11-2) 백준 2231번: 분해합

 

M= int(input())
x=0

for i in range(M):
    a = list(map(int, str(i)))
    s = i + sum(a)
    if(s==M):
        x = i
        break
print(x)

 

말 그대로 M보다는 작으니까 M만큼 반복문을 돌며 수를 찾는데, 분해해서 합친 값이 M이라면 출력

 

 

 

 

 

 

11-3) 백준 7568번: 덩치

 

M= int(input())
arr =[]

for i in range(M):
    a,b = map(int, input().split())
    arr.append((a,b))

for i in arr:
    rank = 1
    for j in arr:
        if  (i[0] < j[0]) & (i[1] < j[1]):
            rank +=1
    print(rank, end=" ")

 

수를 입력받고, 자기보다 큰 사람의 수를 찾아서 그만큼 rank로 출력

 

 

 

 

 

 

11-4) 백준 1018번: 체스판 다시 칠하기

 

def check_board(SQUARE, probe, move_x, move_y):
    cnt = 0
    for i in range(8):
        for j in range(8):
            if SQUARE[move_x +i][move_y +j] != probe[i][j]:
                cnt += 1
    return cnt

def check_bw():
    N, M = map(int, input().split())
    square = [list(input()) for _ in range(N)]

    WhiteBoard = [
        ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']
    ]

    BlackBoard = [
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
        ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
         ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']
    ]

    result = 64

    for i in range(N-7):
        for j in range(M-7):
            W = check_board(square, WhiteBoard, i, j)
            B = check_board(square, BlackBoard, i ,j)

            result = min(result, W, B)

    print(result)

check_bw()

 

계속 고민해도 안풀려서 구글링해서 푼 문제..

조금은 노가다같지만 다른 풀이는 읽어도 이해가 잘 안된다.......

​

시작이 B일 때와 W일 때를 구분해서, 받은 문자열을 비교한다.

그래서 다른 문자열이 있다면 그 갯수를 센다

그래서 그 중 작은 수를 출력(시작이 B일때와 W일때 각각 바뀌어야 할 수가 다르므로)

 

 

 

 

 

 

11-5) 백준 1436번: 영화감독 숌

 

n = int(input())
cnt = 0
six_n = 666
while True:
    if '666' in str(six_n):
        cnt += 1
    if cnt == n:
        print(six_n)
        break
    six_n += 1