03. Brute-force Search(1)

완전 탐색. 모든 경우를 다 생각하는 것입니다. 수학을 배울 때 끔찍한 기억이 떠오르는군요. 분명히 뭔 이야기를 하는지는 알겠는데 간단하게 풀자니 자신이 없어서 모든 경우를 다 고려해서 문제를 풀었던 기억 말입니다.

 

물론 완전탐색으로 원하는 시간 안에 다 풀리진 않습니다. 우리가 시간복잡도라는 것을 고안한 이유죠.

 

https://www.acmicpc.net/problem/1912

1912번: 연속합

위의 문제가 좋은 예시가 될 수 있겠네요. 입력값이 최대 10만이죠. 모든 구간에 시도하면 10만C2이고 O(N^2)입니다. 완전 탐색으로 풀 수 없는 거죠. Order를 보시면 O(1), O(N), O(NlogN)등으로 풀리게 노력해야 하는 것이죠.(O(1)이 있을까요?)

 

언뜻 쉬워보이지만 어려운 완전탐색 문제도 존재합니다. 또한 문제의 크기가 의외로 작을 경우 다 시도해보는 것이 좋을 때도 있지요.

 

저는 문제 SET를 라이님의 Ries 마법의 슈퍼마리오 블로그를 참고하였습니다. 상당히 좋은 글과 문제들을 엄선해 놓으셨더라고요.

 

읽어주시는 분들의 편의(?)를 위해서 알고리즘 카테고리는 tag에 신경쓰겠습니다. 아무래도 추가적인 글을 작성하면 여러분이 보시기에 정렬되어 있지 않아 보기 불편하실겁니다. 게시글 순서를 바꾸려면 날짜변경을 일일이 해주어야 해 관리에 번거로움이 있습니다. 그래서 쉽게 검색하시려면 이런식으로 하시면 됩니다. 알고리즘 카테고리 안의 brute-force 알고리즘과 관련된 모든 글은 brute-force tag를 사용하였습니다. 도움되시길 바라겠습니다. 다른 알고리즘 파트를 설명하는 글을 작성할 때도 어떠한 tag를 사용할지 하단에 작성해 두겠습니다.

https://ku320121.tistory.com/tag/brute-force

SONGANG