개인공부/알고리즘
오늘 알게된 내용 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 문제: 답이 주어졌을 때 이것이 정답인지를 다항시간 내에 확인할 수 있는 문제
