오늘 알게된 내용 2021.10.03

-알고리즘이란?

주어진 문제를 해결하는 한가지 방법을 명료하게 써놓은 것을 알고리즘이라 한다.

- 알고리즘의 시간복잡도에 따른 시간

O(N^3) 알고리즘: 크기 2560 이하인 입력을 1초 안에 풀 수 있다.

O(N^2) 알고리즘: 크기 40960 이하인 입력을 1초 안에 풀 수 있다.

O(NlgN) 알고리즘: 크기 대략 2천만 이하인 입력을 1초 안에 풀 수 있다.

O(N) 알고리즘: 크기 대략 1억 6천만 이하인 입력을 1초 안에 풀 수 있다.

- P/NP 문제란?

P 문제: 다항 시간 알고리즘이 존재하는 문제들의 집합

NP 문제: 답이 주어졌을 때 이것이 정답인지를 다항시간 내에 확인할 수 있는 문제