분류 전체보기(110)
-
1.시간 복잡도 빅오 표기법 O(N)
시간 복잡도(time complexity)란 가장 널리 사용되고 있는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 ㄴ수행하는 기본적인 연산의 수를 입력 크기에 대한 함수로 표한한 것이다. 그리고 표현을 할때 O표기를 하는데 역기서 O표기를 할때 변수의 차수가 큰 것을 따라간다. n^2+5n => O(n^2) n^3+100n^2 => O(n^3) n^2*m+m^2*n+3 => O(n^2*m+m^2*n) 근데 시간복잡도가 낮다고 해서 언제나 더 빠르게 작동하는 것은 아니다. 밑에 그래프를 보면 알 수 있듯이. 복잡도가 낮다고해서 더 빠르게 작동하는 것이 아니라 일정 구간 이상부터 빠르게 작동하는 것을 알 수 있다. 우리가 1부터 n까지의 합을 구할 때 int sum=0; for(int i=0; i
2021.11.05 -
백준 1018 c++ 완전탐색(Brute-force Serch)
원래 티스토리 해보려고 했는데, 귀찮아서 시작 도안하다가 잔머리? 굴려서 푸는 문제 맞히면 기분 좋잖아요? 그래서 기분 좋아져서 시작해봄 완전 탐색, 브루트 포스(Brute-force)는 그냥 쉽게말해서 가능한 경우를 일일이 다 탐색하는 방법임 근데 브루트포스 문제들은 다 탐색하면 타임 에러가 뜨겠죠? 그래서 어떻게 시간을 최소화하는지에 따라서 문제를 맞히고, 틀리고 가 결정됨 여기 문제 보면 알 수 있는 것처럼 브루트 포스 문제는 시간제한이 있음(하나씩 다 검사하다가는 틀린다는 거) 그래서 어떻게 하면 다 대입안 하고, 시간초과 안하고 찾을 수 있을까? 고민해보니까 시작점만 잘 정하면 되겠다고 생각함(어차피 8X8을 구하는 거닌까) 그래서 시작점을 string크기에 따라서 잘 조절만 하면 할 수 있겠다..
2021.11.03