브루트 포스 (Brute Force)

컴퓨터 공학에서의 브루트 포스 알고리즘을 다룹니다.

완전탐색 알고리즘으로 많이 알려져 있습니다. 가능한 모든 경우의 수를 탐색하여 100% 정답을 도출하며, 무식하게(brute) 탐색하는 만큼 단점은 속도입니다.

백준 알고리즘: #1436 영화감독 숌

이 문제는 solved.ac에서 silver5단계로 마크되어 있습니다.

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

풀이

6이 세 개 이상 연속해서 나오는 수는 666 앞에 자리만 바꿔서 될 게 아니라는 것을 명심합시다.

처음엔 규칙이 있으려니 하고 노트에 하나하나 다 적어보았는데요.. 그 나름의 규칙은 있었지만 N번째 숫자를 받아서 이걸 계산할 엄두가 나지 않았습니다.

그래서 브루트 포스의 정수(..)인 노가다로 구해보았습니다! (너무 간단해서 전체 코드에 주석으로 설명을 조금 붙여보았습니다.)

• 너무너무너무 간단함에도 이 포스팅을 하는 이유는 저도 이 방법까지 오는데는 시간을 좀 썼기 때문입니다.. 혹시 너무 답답하셔서 오신 분들은 이 방법 사용해 보세요!

전체 코드

N = int(input())
number = 666

while N:
    if "666" in str(number):
        N -= 1                        # N번째 수를 구하면 루프 종료
    number += 1                        # 수를 1씩 늘려가며 루프 돌기 (666, 667, ...)

print(number - 1)

사담

역시 너무 간단하게 막 풀어서일까... 시간이 어마어마합니다.

지금은 실버단계라 시간도 널널해서 통과될지 모르겠지만, (일단 이런 문제가 나중에 나오긴 할까..)

좀 더 빨리 찾을 수 있는 방법이 있을지 저도 구글링해보러 가렵니다🤣🤣

브루트 포스 (Brute Force)

컴퓨터 공학에서의 브루트 포스 알고리즘을 다룹니다.

완전탐색 알고리즘으로 많이 알려져 있습니다. 가능한 모든 경우의 수를 탐색하여 100% 정답을 도출하며, 무식하게(brute) 탐색하는 만큼 단점은 속도입니다.

백준 알고리즘: #1018 체스판 다시 칠하기

이 문제는 solved.ac에서 silver5단계로 마크되어 있습니다.

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M * N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8 * 8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8 * 8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8 * 8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

풀이

범위 내의 모든 8 * 8 사각형을 검사하는 방법을 찾아봅니다. 그리고 어떻게 최솟값을 알아낼지도 생각해야 합니다.

미리 White로 시작하는 체스판과 Black으로 시작하는 체스판 (이하 W체스판, B체스판) 을 만들어 두고 비교하는 방법과, 체스판의 규칙을 파악한 후 그 칸에 있어야 하는 색인지 체크하는 방법이 있을 것입니다.

저는 후자의 방법을 이용했습니다.

• 가로, 세로의 인덱스가 모두 홀수이거나 모두 짝수인 경우: 각 체스판의 메인 색
  • W체스판일 경우 W, B체스판일 경우 B
• 그 외: 메인의 반대 색

이 규칙을 이용하여 체스판 위 모든 index의 색을 비교하고, 고쳐야 하는 칸의 수를 나타내는 cnt변수를 증가시켰습니다.

cnt = 0
for i in range(8):                        # 8 * 8 체스판 인덱스 탐색
    for j in range(8):
        if ((i % 2 == 0) and (j % 2 == 0)) or ((i % 2 and j % 2)):
            if s[i][j] == 'W':            # 인덱스가 모두 홀수거나 모두 짝수일 경우
                cnt += 1
        else:
            if s[i][j] == 'B':
                cnt += 1

위의 함수를 W체스판과 B체스판이라는 2가지 경우의 수에 따라 체크한 후, 더 작은 값의 cnt를 반환하는 check()함수를 만들었습니다.

그리고 입력되는 보드의 칸 수에 따라 이 check()함수를 반복하고, 함수 호출마다 한 번씩 반환되는 cnt들을 result리스트에 저장한 후 그 안에서 최소값을 출력하는 코드를 완성했습니다.

이 때 반복 범위 설정에 주의해야 합니다! for i in range(N - 7): for j in range(M - 7):

또한 check()함수에 넣을 sample도 적절한 slicing을 통해 만들어주어야 합니다. 다음은 전체코드에서 확인하실 수 있습니다.

전체 코드

N, M = map(int, input().split())
boards = [list(input()) for i in range(N)]
result = []                                # 각 case별 최솟값을 저장할 리스트

def check(s):
    cnt1 = 0                            # B가 시작점인 체스판일 경우
    for i in range(8):
        for j in range(8):
            if ((i % 2 == 0) and (j % 2 == 0)) or ((i % 2 and j % 2)):
                if s[i][j] == 'W':
                    cnt1 += 1
            else:
                if s[i][j] == 'B':
                    cnt1 += 1

    cnt2 = 0                            # W가 시작점인 체스판일 경우
    for i in range(8):
        for j in range(8):
            if ((i % 2 == 0) and (j % 2 == 0)) or ((i % 2 and j % 2)):
                if s[i][j] == 'B':
                    cnt2 += 1
            else:
                if s[i][j] == 'W':
                    cnt2 += 1
    return min(cnt1, cnt2)

for i in range(N - 7):
    for j in range (M - 7):
        sample = [board[0 + j : 8 + j] for board in boards[0 + i : 8 + i]]
        result.append(check(sample))        # 반환값 저장

print(min(result))

사담

처음에 어떻게 해야 될 지 감이 안 와서 한참 생각하다 구글링을 했더랍니다..

브루트 포스가 가장 단순하고 빨리 짤 수 있다는데 왜 저한텐 브루트 포스가 더 어려울까요!! (가이드 보고도 스스로 코드 이해하는데 시간 많이 씀🤦‍♀️)

그래도 이렇게 포스팅하면서 제대로 이해하고 쓰는 만큼 실력도 얼른 향상되었으면 좋겠습니다🥰

브루트 포스 (Brute Force)

컴퓨터 공학에서의 브루트 포스 알고리즘을 다룹니다.

완전탐색 알고리즘으로 많이 알려져 있습니다. 가능한 모든 경우의 수를 탐색하여 100% 정답을 도출하며, 무식하게(brute) 탐색하는 만큼 단점은 속도입니다.

백준 알고리즘: #7568 덩치

이 문제는 solved.ac에서 silver5단계로 마크되어 있습니다.

문제

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k + 1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

입력

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다. 단, 2 ≤ N ≤ 50, 10 ≤ x, y ≤ 200 이다.

출력

여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.

풀이

모든 경우의 수를 탐색하는 방법을 생각해 봅니다.

N개의 정보를 받아 각 정보를 다른 정보들과 비교하여 자신보다 덩치가 큰 사람이 몇 명인지 확인할 수 있습니다.

1. 두 개씩 제공되는 정보를 tuple형식으로 받아 info리스트에 저장했습니다.
2. 결과값을 저장할 rank리스트를 생성하고, 초기값을 1로 설정하여 자기보다 큰 사람의 숫자를 더하면 등수가 나올 수 있게 했습니다.
3. for문을 2번 중첩해서 전체 원소를 확인하였으며, 이미 비교한 원소끼리는 다시 비교하지 않도록 범위를 조정하였습니다. (탐색속도 향상을 위함)

전체 코드

N = int(input())
infos = []
rank = [1 for i in range(N)]                                                        # N개의 원소를 1로 초기화하여 생성

for i in range(N):
    x, y = map(int, input().split())
    infos.append((x, y))                                                            # tuple로 받아서 infos에 저장

for i in range(N):
    for j in range(i + 1, N):
        if infos[j][0] > infos[i][0] and infos[j][1] > infos[i][1]:
            rank[i] += 1                                                            # 뒤가 크면 앞사람 등수 + 1
        elif infos[j][0] < infos[i][0] and infos[j][1] < infos[i][1]:
            rank[j] += 1                                                            # 앞이 크면 뒷사람 등수 + 1

for i in range(N):
    print(rank[i], end = " ")

사담

역시 브루트 포스는 메모리와 시간이 많이 쓰이는 것을 체감했습니다..

더 충격적인 것은 같은 유형의 문제 중에서 이 문제가 그나마 빨랐다는 것🤣🤣

재귀 (Recursion) 함수

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻합니다.

백준 알고리즘: #11729 하노이 탑 이동 순서

이 문제는 solved.ac에서 silver2단계로 마크되어 있습니다.

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 <= N <= 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄에서 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

풀이

하노이 탑 문제를 해결하기 위한 재귀 과정을 생각해 봅니다.

def hanoi(n, start = 1, by = 2, to = 3):    # 항상 장대가 3개이고 1 -> 3이 목표임
    if n == 1:                                # 따라서 default값 설정함
        move(start, to)                        # 원반이 1개 남고 함수가 끝난다
    else:
        hanoi(n - 1, start, to, by)            # n-1개의 원반을 2번째 장대에 두고
        move(start, to)                        # 나머지 하나를 3번째 장대에 옮긴다
        hanoi(n - 1, by, start, to)            # n-1개의 원반을 3번째 장대에 옮긴다

이 문제는 n개의 원반이 입력된 하노이 탑 문제를 n - 1, n - 2, ..., 1개의 원반을 옮기는 문제로 점점 줄여가면서 풀 수 있습니다.

자기 자신(hanoi())뿐만 아니라 move()라는 실제로 원반을 옮기는 함수가 하나 더 필요하기 때문에, 저 역시 처음부터 효율적인 코드를 짜기는 어려웠습니다.

구글링을 하면서도 직관적인 것이 장점이라는 말이 무색해질 정도로 한 눈에 들어오지도 않았던 것 같아 이번 포스팅을 계기로 확실히 공부하게 되었습니다.

위 그림은 n이 3일 경우에 하노이의 탑이 어떻게 재귀적으로 구현 가능한지 나타냅니다.

1. hanoi(3)를 호출하면 1번째 장대에 크기순으로 3개가 쌓인 초기 상태가 됩니다.
   • 이 때, hanoi() 함수의 start,by,to 인자는 default값으로 자동처리해도 됩니다.
   • 어차피 출발은 1장대고 도착은 3장대이기 때문입니다. by인자는 출발과 도착을 제외한 다른 숫자를 넣어주는 거라고 생각하면 됩니다.
2. hanoi(3)을 호출하면 n이 1이 아니기 때문에 else문으로 갑니다. 여기서 hanoi(2, 1, 3, 2)의 자기 자신을 호출하게 되는데, 제일 큰 원반을 제외한 나머지 2개의 원반을 1번째 장대에서 2번째 장대로 옮긴다는 뜻입니다.
   • 이 부분에서 원반 1개씩 옮기지 않는 것은 큰 틀을 보기 위해서입니다! 실제로 hanoi(2, 1, 3, 2)를 호출할 경우 다시 자기 자신이 호출되며 결국 원반을 1개씩 옮기는 단계로 내려갑니다.
3. 다음 줄에 호출되는 move(1, 3)은 1번째 장대에 남아있는 가장 큰 원반을 3번째 장대(목표)로 옮깁니다.
4. 마지막으로 hanoi(2, 2, 1, 3)을 호출하여 아까 2번째 장대에 옮겨놓았던 2개의 원반을 3번째 장대(목표)로 옮길 수 있습니다.

이러한 순서를 통해 결국 hanoi(1, ...)이 호출될 경우, 원반 하나를 1번째 장대에서 3번째 장대로 옮기고 재귀가 끝이 나게 됩니다.

또한 이 문제에서 고려해야 할 것은 출력값입니다.

하노이의 탑을 해결한 이후에 이것이 최소 몇 회의 이동이 일어나는지를 첫 번째 줄에 출력해준 다음, 그 과정을 정해진 형식에 맞춰 순서대로 출력해야 합니다.

따라서 저는 move()함수를 다음과 같이 구성해 보았습니다.

result = []
def move(start, to):
    result.append((start, to))            # tuple 형식으로 저장

1. move()함수를 호출할 때마다 바로바로 과정을 출력해주면 편하겠지만, 출력 순서가 지정되어 있으므로 전역 공간에 빈 리스트인 result를 선언해줍니다.
2. move()함수의 인자로 받는 출발지와 목적지를 tuple형식으로 묶어 result에 추가합니다.
   • 리스트(List)는 순서가 있는 자료구조이므로 추가된 순서대로 저장이 됩니다. (list.append()함수는 list에 요소를 추가할 때 사용하는 빌트인 함수입니다.)

이렇게 hanoi()를 호출한 이후에 result에 움직인 과정을 넣고, len(result)(이동과정 횟수)와 result의 요소를 한 개씩 출력해 주면 문제가 해결됩니다.

전체 코드

result = []                        # 결과값 저장할 빈 리스트 생성

def move(st, to):
    result.append((st, to))

def hanoi(n, st = 1, by = 2, to = 3):
    if n == 1:                    # base case (재귀 종료 조건)
        move(st, to)
    else:
        hanoi(n - 1, st, to, by)
        move(st, to)
        hanoi(n - 1, by, st, to)

N = int(input())                # N을 정수로 받아옴
hanoi(N)
print(len(result))                # 이동 횟수 출력
for x in result:
    print(x[0], x[1])            # 요소가 2개인 tuple이므로 indexing하여 숫자만 출력

사담

생각보다 메모리나 시간면에서 매우 비효율적으로 보여 맞았지만 조금 슬펐습니다.

최적화할 수 있는 방안이 있을지 찾아봐야겠다는 생각과 동시에 파이썬이라 그런게 아닐까라는 합리화를 조금 했습니다..😃😃