브루트 포스(brute force)

브루트 포스

---

브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다.

흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.

 

문제를 풀다가 리스트, 문자열 다른 방법보다 그냥 하나씩 세는게 더 빠르고 간단할 때 사용

사실 난생 처음 들어보는 단어라서 기록했다.

 

+ 추가

문자열에서 패턴 매칭이 어떤 문자열(target) 내부에 다른 문자열(pattern)이 존재하는지를 검증하는 과정을 표현하는 것인데, 이때 존재하는지 찾고자 하는 문자열을 패턴이라고 부른다.

 

문자열에서의 브루스 포트는 가장 기본적인 방법으로 문자열을 비교해가며 패턴 매칭을 하는 방식이다.

본문 문자열의 특정 위치부터, 패턴 문자열과 완전히 일치하는지 비교 후, 일치하지 않는다면 다음 위치에서 비교하여 검증하는 방식.

 

아래는 예시 코드이다.(참고 - 자바 코드입니다.)

public class BFPatternMatching {
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String target = reader.readLine();
        String pattern = reader.readLine();

        int tarIdx = 0;
        int patIdx = 0;

        List<Integer> foundAt = new ArrayList<>();
        while (tarIdx < target.length() && patIdx < pattern.length()) {
            if (target.charAt(tarIdx) != pattern.charAt(patIdx)) {
                // 시작점 원위치, 맞았던 만큼 돌아간다.
                tarIdx -= patIdx;
                // 다음에 패턴의 첫 위치를 다시 찾기 위해 -1로 초기화
                patIdx = -1;
            }
            // 다음 인덱스 검사
            tarIdx += 1;
            patIdx += 1;
            if (patIdx == pattern.length()) {
                foundAt.add(tarIdx - patIdx);
                tarIdx = tarIdx - patIdx + 1;
                patIdx = 0;
            }
        }

        if (foundAt.size() == 0) {
            System.out.println("404 NOT FOUND");
        } else {
            foundAt.forEach(System.out::println);
        }

    }

    // qwertyuiuiuytrertyuiopopoiuytrqwertyuytrertywqwertyuiuytrewqwertyuiiuiuiytrewert
    // qwert
    // 0, 30, 45, 59
    public static void main(String[] args) throws IOException {
        new BFPatternMatching().solution();
    }
}

 

 

 

[백준] 1436번 - 영화감독 숌

---

666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다.

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

 

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

라는 문제였는데 아래와 같이 풀 수 있다.

n = int(input())
devil = 666

while n: # 666 667 668 ... 1665 1666 이런 식으로 계속 찾게되는 알고리즘
    if "666" in str(devil): n -= 1
    devil += 1

print(devil - 1)

 

Notion Link : https://solar-textbook-084.notion.site/brute-force-a3a615c973804fc3a1f8ff91ce1dbde1