Nirsa

[Algorithm] 시간 복잡도 정리

입력 제한에 따라 어떠한 알고리즘을 사용할지 정할 수 있는데 이는 아래와 같습니다.

1. n <= 20  : 웬만한건 모두 통과
   →  브루트포스 알고리즘
   → O(n!), O(2^n)
2. n <= 100 : 삼중 루프 가능
   → 폴로리드 와샬 알고리즘
   → O(n^3)
3. n <= 1000  : 이중 루프 가능
   → 벨만포트 알고리즘
   → O(n^2)
4. n <= 10000 : 알고리즘을 이용하여 풀어야 함
   → 동적 프로그래밍, 이분탐색, 다익스트라 알고리즘, 유니언 파인드, 세그먼트 트리, 투포인터
   → O(n), O(nlogn)
5. n <= 10^8
   → 유클리드의 호제법
   → O(logn)

[Algorithm] 완전 탐색, 브루트포스 알고리즘 (Brute Force)

완전 탐색, 브루트포스 알고리즘은 이름 그대로 모든 경우를 탐색하여 답을 도출하는 알고리즘입니다.

이러한 특징 때문에 정답을 당연히 찾아 맞출수는 있지만, 모든 경우를 탐색하는 만큼 정답이 도출될 때 까지의 시간은 장담할 수 없는 큰 단점이 있습니다. 즉, 시간 복잡도가 매우 큽니다. 즉, 만약 123456789라는 정답이 있을 경우 아래와 같이 동작하게 되는 알고리즘 입니다.

1. 숫자 1 탐색
2. 숫자 2 탐색
3. 숫자 3 탐색
4. ....
5. 숫자 123456787 탐색
6. 숫자 123456788 탐색
7. 숫자 123456789 탐색 후 정답 도출

이러한 특징으로 인해 브루트포스 알고리즘의 경우 대부분 무한 루프, 중첩되는 for문과 if문을 조합하여 사용하게 됩니다. (모든 경우의 수를 찾아 확인하고, if문으로 정답을 걸러낸 후 break하는 방식)

브루트포스를 활용한 코딩 테스트 문제 : https://nirsa.tistory.com/394

장점

• 복잡한 알고리즘을 사용하지 않아 빠르게 구현하고, 설계하기가 쉬움
• 모든 경우의 수를 찾아 정답을 도출하기 때문에 결국에는 정답을 찾게 됨

단점

• 시간 복잡도가 높아 정답을 도출하기 까지의 시간이 매우 오래 걸림
• 모든 경우의 수를 찾기 때문에 효율적이지 않음