Algorithm

시간복잡도

• 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것.

Big O notation으로 표현하며 지배적인 항만 살린다.
마스터 정리를 사용하면 쉽게 시간복잡도를 계산할 수 있다.

마스터 정리

https://ko.wikipedia.org/wiki/%EB%A7%88%EC%8A%A4%ED%84%B0_%EC%A0%95%EB%A6%AC

계산복잡도 클래스

• P
  • 다항 시간에 풀 수 있는 문제들의 집합
• NP
  • 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제들의 집합
  • P 문제도 NP 문제에 포함됨
• NP-hard
  • NP에 속하는 모든 문제를 다대일 환산할 수 있는 문제들의 집합
  • ex) SAT
• NP-complete
  • NP-hard이면서 NP인 문제

풀려하는 문제가 어떤 변환을 거치면 NP-hard, NP-complete 문제를 풀 수 있다면,
곧 이 문제는 NP-hard 이상으로 어려우며 이 문제를 다항 시간에 푸는 것은 인류 역사상 아무도 못한 문제이다.
따라서 모델링을 바꾸거나 근사해를 구하는 것이 현명하다.

알고리즘의 정당성 증명

• 귀납법과 반복문 불변식
• 귀류법
• 비둘기집의 원리
• 구성적 증명

무식하게 풀기

알고리즘을 배우다보면 쉽게 풀 수 있는 문제도 굳이 복잡하게 풀려고 할 때가 있다.
컴퓨터의 최대 장점인 계산 속도를 잘 활용하는 것은 무식하고 간단한 방법으로 풀 수 있는 문제는 그냥 그렇게 푸는 것이다.

Brute Force를 이용해 풀 수 있는 문제인지 확인하고 총 계산량을 계산한다. 1초에 약 1억개의 계산을 할 수 있다고 가정하고 대략 몇초가 걸리는 지 계산하여본다.