주먹구구식 알고리듬

주먹구구식 알고리듬(Brute Force)

모든 가능한 경우의 수를 시도하는 알고리듬

왜 주먹구구식 알고리듬이 필요한가?

문제에따라 더 효율적인 알고리듬이 없는 경우가 있기때문!

주먹구구식 알고리듬의 예

• 완전검색(배열에서 20을 찾기)
• 배열에서 어떤 값의 첫 번째 / 마지막 색인 찾기
• 배열에 들어있는 정수들의 합 or 평균 구하기
• 배열에서 최대값 or 최소값 찾기
• char[]에 저장된 문자열 뒤집기(사본생성 금지!)
• 그 외 다수..
• 시간복잡도는 모두 O(N)

주먹구구식 알고리듬의 시간복잡도

• O(N)보다 시간복잡도가 높은 알고리듬들이 많음.
• O(N^3) 정도부터 최적화를 고려하는 경우가 많음
  - N이 작은 수면 상관없음.
• 컴퓨터에서 실행하기엔 너무 느린 알고리듬들이 많다.
  - 보안분야에서 많이 사용됨(현실적으로 불가능해보일정도의 컴퓨팅 파워를 사용하여 주먹구구식으로 풀어야만 풀릴 수 있게 만드는 것들)
  

주먹구구식 비밀번호 깨기

1. 비밀번호 규칙에 맞는 새로운 비밀번호를 하나 만든다.
2. 그 비밀번호가 올바른 비밀번호인지 시도해본다.
3. 올바르지 않다면 1번단계로 돌아간다.

   시간복잡도: O(K^N)
   N: 비밀번호 자리수
   K: 각 자리에 들어갈 수 잇는 문자 수

외판원 문제(T.S.P)

• 여러 도시를 방문해야하는 외판원
• 각 도시를 최소 한번씩 방문해야 함
• 가장 짧은 거리를 이동해서 다음을 완료해야함.

  1. 한 도시에서 시작
  2. 모든 도시를 방문
  3. 원래대로 돌아옴

외판원 문제를 주먹구구식으로 푼다면?

1. 시작할 도시를 고른다.
2. 모든 방문 순서 목록들을 만든다.
3. 각 목록의 총 이동거리를 계산한다.
4. 그 결과 중 총 이동거리가 가장 짧은 목록을 선택한다.
   => 시간복잡도는? O(N!)
   => 사용할 수 없는 알고리듬이다..

기하급수적 증가 알고리듬의 문제점

1. 기하급수적(exponential) 이란 지수시간을 뜻함
   -> O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) 에서 O(2^n) 및 O(n!)을 뜻함.
2. 이에 반대되는 개념은 다항식(polynomial)시간이 걸리는 알고리듬이고 이를 선호한다.

본 내용은 Udemy의 알고리듬 및 자료구조(Java)강의를 듣고 정리한 내용입니다.