완전탐색 (For 반복문, 백준 19532, 2503)

 

 

완전탐색이란?

 

말그대로, 무식한 방법으로 알고리즘 문제를 푸는 방법, Brute Force

이는 알고리즘 풀이의 근본이며, 시작이라고 한다.

 

Python의 경우 1초에 약 1억번의 연산이 가능하다.

 

조건을 고민하고, 컴퓨터를 위해 생각하고

또, 컴퓨터를 배려하고.. 할 필요가 없다는 것이다.

 

물론 나중에 비지니스와 연결됐을때의 문제는 다른 얘기지만

단순하게 메모리, 시간이 넉넉하다면 무식하게 풀어도 상관없다는 것.

 

나처럼 야매로 풀다가 알고리즘을 제대로 배우기 시작한 뉴비들은

완전탐색을 이용하면 for문과 if문만 알아도 문제가 풀리는 신기한 경험을 해볼 수 있었다.

 

아래는 이번에 풀어본 예제들이다.

 

문제 1. 

백준 #19532

 

 

 

접근 :

 

입력값도 6개에 정수 범위도 있고.. 음..

고민하지 말고 문제가 알려준대로 for문과 if문을 돌려보자.

 

a, b, c, d, e, f 가 공백으로 구분되어 차례대로 주어지기 때문에

a, b, c, d, e, f = map(int, input().split())

a, b, c, d, e, f = map(int, input().split())

 

x, y는 -999 부터 999 이하의 정수이다.

이를 연립방정식에 대입해서 만족하는 x, y 를 찾는 건데 무식하게 전부 대입하면 된다

 

따라서,

for x in range(-999, 1000) :
    for y in range(-999, 1000) :
        if (a * x) + (b * y) == c and (d * x) + (e * y) == f :
            print(x, y)
            break

 

문제에 있는 조건을 그대로 for문과 if문으로 코드로 바꿔 적은 것이다.

 

 

 

 

 

문제 2 :

백준 #2503

 

 

접근 :

 

민혁이가 영수에게 몇번이나 질문했는지 질문횟수 = N이므로

N = int(input())

 

이 후 나오는 줄에 대한 숫자들은 '세자리수 스트라이크 수 볼의 수' 로 숫자야구 답을 찾기위한 단서들이 되므로

hint = [list(map(str, input().split())) for _ in range(N)]

 

이렇게하면 [[123, 1, 1], [345, 1, 0], [327, 2, 0], [489, 0, 1]] 이런식으로 배열안의 배열 형태로 값이 저장 된다.

 

여기서 int 가 아닌 str(문자열)로 받은 이유는 hint의 세자리수를 각각 쪼개서 스트라이크, 볼을 판단하기 위함이다.

 

숫자야구는 세자리수 100 부터 999까지의 숫자 중에서의 답을 찾는 게임이기 때문에

100부터 999까지 모든 자리수를 비교해보면 된다.

 

따라서,

 

for a in range(1, 10) :
    for b in range(1, 10) :
        for c in range(1, 10) :

 

그런데 숫자야구는 서로 자리수가 중복되지 않기 때문에

if a == b or a == c or b == c :
    continue

 

이제 단서들을 각 자리 숫자들과 비교해보면서 단서의 조건을 만족하는 숫자들을 찾아야한다.

 

숫자게임은 단서들을 기반으로 단서들을 만족하는 새로운 숫자들을 제시하면서 정답을 찾는 게임이기 때문!

 

이제 각 힌트들을 돌면서 100부터 999까지의 모든 자리수들을 무식하게 비교하면 된다.

 

for arr in hint :
                check = list(arr[0])
                strike = int(arr[1])
                ball = int(arr[2])

                strike_cnt = 0
                ball_cnt = 0

                if a == int(check[0]) :
                    strike_cnt += 1
                if b == int(check[1]) :
                    strike_cnt += 1
                if c == int(check[2]) :
                    strike_cnt += 1

                if a == int(check[1]) or a == int(check[2]) :
                    ball_cnt += 1
                if b == int(check[0]) or b == int(check[2]) :
                    ball_cnt += 1
                if c == int(check[0]) or c == int(check[1]) :
                    ball_cnt += 1

                if strike != strike_cnt :
                    break
                if ball != ball_cnt :
                    break

                counter += 1

            if counter == N:
                answer += 1

print(answer)

 

check 에는 예를들어 123 이었으면 ['1', '2', '3'] 으로 배열이 만들어지고

check의 0, 1, 2 index 번호 위치의 값들과 세자리수들을 돌아가며 스트라이크 카운터, 볼카운터를 증가시킨다.

이 후, 해당 단서의 스트라이크값, 볼 값과 증가시켰던 스트라이크 카운트값, 볼카운트값이 같다면

 

해당 단서를 모두 만족하는 숫자가 생겼으므로 카운터를 증가시킨다.

 

이 후, 모든 단서들을 만족해서 counter 값이 N (단서의 총 갯수)와 같다면

모든 단서를 만족하기 때문에 다음 숫자야구 질문값으로 적당하므로 answer의 값을 1 증가시킨다.

 

모든 for문이 종료되고 나면 answer를 답하면 된다.

 

평가 :

 

이 문제는 예제로 받고나서 이 전 예제들처럼 단순하게 생각하면 되겠지? 하고 풀었는데

단순하게 생각하면 되긴 하는데 카운터를 증가시키는게 생각이 안나서 조금 걸렸던 문제다.

어쨌든 풀이방식 자체는 무식하게 완전탐색을 하면 되는 문제였다.

 

 

앞으로 쫄지말고 완전탐색 먼저 해볼 것

 

---

참고 : 2주만에 통과하는 알고리즘 코딩테스트 (2024년)