매일매일 공부하는 개발자

주먹구구식 (brute-force) 알고리즘

• 모든 가능한 경우의 수를 시도하는 알고리즘
  • 모로가도 서울만 가면 된다.
  • 최소 O(n)
• 좋은 알고리즘의 조건 중 ‘효율성’을 고려하지 않은 알고리즘
  • 문제에 따라 더 효율적인 알고리즘이 없는 경우도 있음
• 보통 가장 직관적인 문제 해결법
  • 예 : 숫자를 이용한 계산과 단순한 알고리즘 다수

주먹구구 알고리즘 : 완전 (exhaustive) 검색

• 처음 부터 끝까지 나올때 까지 검색

주먹구구식 알고리즘과 시간 복잡도

• O(N)보다 시간 복잡도가 높은 알고리즘들이 많음
• O(N^3)정도 부터 최적화를 고려하는 경우가 많음
  • N이 작은 수면 상관 없음
• 컴퓨터에서 실행하기에는 너무 느린 알고리즘들도 많음
  • 알려진 최적화 방법이 없는 것들도 존재
  • 반드시 나쁜 일은 아님
  • 보안 붕야가 이에 많이 의존

주먹구구식 비밀번호 꺠기

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

주먹구구식 비밀번호 깨기의 시간 복잡도

• O(K^N)
  • N : 비밀번호 자릿수(계속 늘릴 수 있음)
    • 증가할 수록 기하학적 증가
  • K : 각 자리에 들어갈 수 있는 문자 수 ( 상식적으로 100자 미만)

외판원 문제 (traveling salesman problem)

• 줄여서 TPS 라고 부름
• 여러 도시를 방문해야 하는 외판원
• 각 도시를 최소 한번씩 방문해야 함
• 가장 짧은 거리를 이동해서 다음을 완료해야 함
  • 한 도시에서 시작
  • 모든 도시를 방문
  • 원래 도시로 돌아옴
  • 이동 방법은 운전

주먹구구식 TSP 알고리즘

• 시작할 도시를 고른다
• 모든 방문 순서 목록들을 만든다 (모든 경우의 수)
• 각 목록의 총 이동거리를 계산한다
• 그 결과 중 총 이동거리가 가장 짧은 목록을 선택한다.

 TSP 주먹구구식 시간 복작도 : O(N!) **기하급수적 증가

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

• N이 커질수록 문제를 푸는 속도가 매우 느려짐
• 실무에 사용하기 어려운 경우가 많음
  • 예 : 무한루프는 아닌데 몇 분 안에 결과가 안 나오는 코드
• 기하급수적 증가 ( exponential grwoth)

문제 해결에 지수 시간이 걸리면 비 실용적

• 지수 시간 알고리즘은 실무에 적용 불가능한 경우가 매우 많음
• 다항식 (polynomial) 시간이 걸리는 알고리즘을 선호
  • 다항식 시간 vs 지수 시간
• 해결에 다항식 시간이 걸리는 문제를 P 문제

재귀 ( recursive ) 함수

알고리즘을 공부하려면 작성할 수 있어야 한다. 

큰 문제를 반복 적용 가능한 작은 문제로 나워 푸는 방법이다. 즉, 어떤 함수가 매개변수만 바뀌어 자기 스스로를 호출하는 방식으로 구현

재귀가 필요한 알고리즘이 많음

• 이진 검색
• 트리 검색
• 퀵 정렬
• 그래프 알고리즘

재귀 함수의 장단점

꼬리 호출

• 기존 재귀 함수를 보완하는 방식
• 함수 코드 제일 마지막에서 다른 함수를 호출하는 경우
• 그 후에 실행하는 명령어가 없음

꼬리 호출과 시택 프레임

• 스택 프레임이 존재하는 이유
  • 함수에서 사용 중인 변수 값을 유지하기 위해
  • 타 함수 호출 후 반환되면 스택에 저장했던 값을 되덜려 사용
• 꼬리 호출의 경우는 타 함수로 부터 반환 후 더 이상 연산이 없음
  • 곧바로 호출자로 반환
• 따라서 스택 프레임에 저장해 놓은 변수 값을 재상용하지 않음
  • 이러한 경우 컴파일러가 스택 프레임을 따로 안 마드는 최적화를 하기로 함
    • 꼬리 호출 제거 ( tail call elimination)
    • 꼬리 호출 최적화 (tail  call optimization)

꼬리 재귀 (tail recursion)

• 꼬리 호출의 특수한 경우
• 마지막 에 호출하는 함수 ( 꼬리 호출) 가 자기 자신 (재귀)
• 꼬리 호출과 똑같은 최적화가 적용됨

꼬리 재귀 함수 작성하기

• 보통 꼬리 재귀 함수가 덜 직관적
• 그러나 이런 식으로 작성된 코드가 종종 보임
• 가장 큰 이유는 앞에서 말했던 최적화

꼬리 호출 최적화를 지원 안 하는 언어라면?

• 안 돼도 충분한 의미가 있음
• 꼬리 재귀는 반복문으로 쉽게 변경 가능

점근 표기법 (asymptotic notation)

점점 점, 가까울 근 : 점점 가까워짐

• 정수론과 해석학의 방법
• 어떤 함수가 증가하는 모습을 또 다른 함수와 비교
• 알고리즘의 복잡도를 논하거나 단순화 시킬 때 사용

컴퓨터 공학에서의 빅오 표기법

• 대문자 O를 이용해 표기
• 주로 알고리즘을 분류하기 위해 사용

O의 의미는 order of the function ( 대략 그 함수 정도)

분류하는 기준

입력 데이터가 많아짐에 따라 다음 둘이 얼마나 늘어나는지 측정

• 실행 시간 ( 시간 복잡도)
  • 알고리즘에서 주로 신경쓰는 부분
• 필요한 공간 ( 공간 복잡도)

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)

'대략 그 정도'의 의미

• 알고리즘의 실행 시간을 일반화하여 표현해서 쉽게 분류
  • 실행 시간의 예 : T(n) = 5n^2 - 5n + 3 <- 다항식의 결과가 나온다
  • 그중 최대 차항만 가지고 이야기 한다. 즉, 상기 실행 시간은 O(n^2)이 된다.

최선 vs 평균 vs 최악

• 데이터에 따라 실제 알고리즘의 실행 속도가 달라질 수 있음
• 하기 이미지는 교육 차원의 O 표기법의 성능

실무 차원에서 N^2 까지는 OK 
N^3 부터는 고민해봐야할 문제