빅오(big - O)에 대하여 빅오는 점근적 실행 시간(Asymptotic Running time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 가운데 하나다. 점근적 실행 시간이랑 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 lim 함수의 실행 시간의 추이를 의미한다. 알고리즘은 궁긍적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안한다면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 점근적 실행 시간은 달리 말하면 시간 복잡도라 할 수 있다. 시간 복잡도(Time Complexity)의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 ..

2021. 3. 23.

알고리즘

[BOJ/백준] 1929번 소수 구하기 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 풀이 a,b = map(int,input().split()) #두개의 값을 띄어쓰기로 구분지어서 입력 def prime(num): #소수 찾는 함수 if num == 1: #1이면 False return False elif num ==2: #2부터는 True return True for i in range(2,int(num**0.5)+1): #에라토스테네스의 체를 안다면 제곱근을 이용해서 푸는것이 시간 단축에 좋음 if..

2021. 2. 5.

알고리즘