백준-브루트포스

1. 브루토 포스(brute force)

brute: 무식한, force: 힘
완전탐색 알고리즘. 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
이 알고리즘의 장점은 예외 없이 100% 확률로 정답만을 출력한다.

• 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.
• 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
• 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 가장 기본적인 도구이다.

2. 예제: 백준 1436번

방법1

n = int(input())
lst = []
i = 0

while len(lst) < n:
    if '666' in str(i):
        lst.append(i)
    i += 1

print(lst[n-1])

방법2

n = int(input())
cnt = 0
num = 666

while True:
    if '666' in str(num):
        cnt += 1
        if cnt == n:
            print(num)
            break
    num += 1

📖 두 코드 비교

<방법1> 코드의 시간 복잡도는 다음과 같다.
1. i를 0부터 시작해 1씩 증가시키며 '666'이 포함된 숫자를 찾는다.
2. '666'이 포함된 숫자를 찾을 때마다 'lst'에 추가한다.
3. 'lst'의 길이가 n이 될 때까지 반복한다.

이 코드의 문제점은 lst에 모든 '666'이 포함된 숫자를 저장한다는 점이다. 이는 메모리 사용 측면에서 비효율적이다. 리스트에 숫자를 계속 추가하면서 공간을 차지하고, 그 리스트의 길이를 계속 확인해야 한다.

<방법2> 코드의 시간 복잡도는 다음과 같다.
1. num은 '666'부터 시작해 1씩 증가시키면서 '666'이 포함된 숫자를 찾는다.
2. '666'이 포함된 숫자를 찾을 때마다 cnt를 증가시킨다.
3. cnt가 n이 되면 루프를 종료하고 해당 숫자를 출력한다.

이 코드는 리스트를 사용하지 않고, 단순히 cnt만 증가시키기 때문에 메모리 사용 측면에서 효율적이다. 또한 cnt가 n이 되는 시점에서 루프를ㄹ 종료하므로 불필요한 메모리 할당이 없다.