시간복잡도

완전탐색 ( Complete Search) 이란? 완전탐색을 알기 전에 상위 개념인 탐색에 대해 알아야 하는 탐색(Search) 알고리즘은 많은 데이터 중 목적에 맞는 데이터를 찾기 위한 방법이다. 탐색 알고리즘에는 여러 가지 탐색 방법이 존재하는데 완전 탐색은 그중 대표적인 알고리즘 중 하나이다. 완전탐색(Complete Search) 은 말그대로 "모든 경우의 수를 검사" 하는 방식으로 브루트포스( Bruth-Force) 알고리즘으로 불리기도 한다. "brute"는 "무식한", "force"는 "힘"을 의미하는데 무식한 힘 즉 무식하게 전체 모든 경우의 수를 검사하는 알고리즘을 의미한다. 완전탐색(Complete Search)은 전체 모든 경우의 수를 검사하기 때문에 매우 큰 메모리를 사용하며, 시간..

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 정답 소스코드 (Python) def if_decimal(num): if num==1: return for i in range(2,int(num**0.5)+1): if num%i==0: return count.append(num) m,n=map(int,input().split()) count=[] # 몇 개 해당하는지 for i in range(m,n+1): if_decimal(i) # m과 n사이에 숫자 하나씩 확인 print(*count) 풀이 (Python) 어떤 수 n이 소수라는 ..

알고리즘 공부를 시작하기 앞서 기본적으로 먼저 다뤄야 할 수학 부분에서는 대표유형으로 크게 나누면 약수, 소수, 최대공약수와 최소 공배수 유형으로 나누어 볼 수 있다. 각 유형별로 알아야 할 포인트를 다뤄보도록 하겠다. 약수 약수를 구하는 방법은 어떤 자연수N이 존재하는 경우 N이하의 자연수로 N을 나누었을 때 나머지가 0이면, 해당 N이하의 자연수는 자연수N의 약수이다. 어떤 자연수 N이 37일 때 코드로 작성하면 다음과 같다. n=36 for i in range(1,n+1): if n%i==0:print(i,end=" ") 결과: 1 2 3 4 6 9 12 18 36 하지만 이와 같이 작성하면 시간 복잡도는 O(n)으로 자연수 N이 10^8이 되는 경우 1초의 시간이 걸리게 된다. 더 적은 시간이 걸..