BigO 알고리즘의 증가 추세로 표시하는 시간 복잡도 표기 방법 2n^2도, 3n^2도 O(n2)로 같다. loop를 한번 쓰면 최악의 경우 모든 계산을 한다. 즉 n번을 계산하게 되므로 루프 시 n*n⇒ n^2가 된다. Big O -upper bound Big Omega - lower bound Big Theta - Tight bound 어떤 경우? 최악의 경우 최선의 경우 ≤ ≥ == 알고리즘의 성장 속도 특정 값보다 작거나 같음 특정 값보다 크거나 같음 특정 값과 같 무엇을 표시? 알고리즘의 상한을 표시 알고리즘의 하한을 표시 상한과 하한의 The bounding of function 을 표시 asymptotic bound(점근적 결합) asymptotic upper bound를 제공 asympto..
🧾 1과 자신 이외의 자연수로는 나눌 수 없는 자연수 1은 소수가 아니다. 소수의 성질을 이용하여 소수를 판별한다. 소수 판별 문제 유형 소수 판별이 필요한 문제 유형은 크게 두가지로 보인다. 소수를 반별 특정 범위 내에서 소수를 찾아 반환하기 소수 판별 (True/False) N을 이용하기 2부터 n-1까지 나누기 def isPrimeNum(n): for i in range(2,n): #2~n-1까지의 모든 수를 나누어 확인 if n%i==0: return False return True 시간복잡도 : O(n) n이 1,000,000(백만)일 때 2~999,999의 모든 수를 하나씩 나누기 때문에 비효율적이다. n/2 까지 나누기 def isPrimeNum(n): ref=int(n/2)+1 for i ..
반복: 어떤 조건이 성립하는 동안 반복해서 처리하는 구조를 반복 구조(repetition structure)라 하고 Loop라고도 한다. loop : while과 for while 조건식이 참일 동안 명령문이 반복되다가 false가 뜨는 순간 반복 종료 실행하기 전에 반복을 계속할 것인지 판단한다. (사전 판단 반복 구조) while ( condition) { statements; //body of the loop } for for(initialization; condition; iteration){ //body of the 'for' loop } while vs for While for 언제 사용하나? 반복 횟수(umber of iterations)가 정해지지 않을 때 반복의 횟수를 이미 알고 있을 때..
