1. 정수

1.1 약수

특정 수를 나누어 떨어지게 하는 수

1.1.1 약수 구하기 구현

1.2 소수

약수가 1과 자기자신인 수

1.2.1 소수 구하기 구현

1.2.2 에라토스테네스의 체(소수 구하기) 구현

1.3 소인수 분해

숫자N을 소수의 곱으로 나타냄

1.3.1 구현

1.4 공약수와 공배수

A,B 공약수, A와 B의 공통된 약수
AB 공배수 A와 B의 공통된 배수

1.4.1 최대공약수(GCD), 최소공배수(LCM)

1.4.2 유클리드 호제법

a, b, r(a/b)
b, r(a/b) , r(b, r(a/b))
… a, b, r==0일때, b 가 최대공약수

1.4 파스칼 삼각형

1
2
3
4
5

1
121
1331
3C0, 3C1, 3C2, 3C3
14641

콤비네이션 값 구할때 사용(20C11)

1. 시간복잡도

문제가 얼마나 빠르게 해결되는지 나타냄
대략적으로 몇개의 명령을 수행하는지?

1.1 for문

1
2
3

for(int i=0 ; i<n; i++){
  int a=0;
}

int a=0;명령을 n번 수행 >> 시간복잡도 O(n)

1.2 n*n 이중for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  for(int j=0 ; j<n; j++){
    int a=0;
  }
}

int a=0;명령을 n*n번 수행 >> 시간복잡도 O(n^2)

1.3 n(n-1)(n-2) …2*1 이중for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  for(int j=0 ; j<i; j++){
    int a=0;
  }
}

int a=0;명령을 n(n-1)/2번 수행 >> 1/2nn >> 상수는 무시 >> 시간복잡도 O(n^2)

1.4 if절 있는 for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  if(i==1){
    int a=0;
   }
}

최악의 경우 n번 수행(if절 결과에 따라) > O(N)
최고차항만 체크

2. 입력크기에 따른 수행시간

1. n의 입력 값에 따라 수행시간 다름
2. 컴퓨터 사양에 따라 다름

2.1 O(N) 시간복잡도

• n이 9000만개일때 보통 1초

2.2 O(N^2) 시간복잡도

• n이 10000개일때 보통 1초 > 명령어 실행수 대략 1억에 1

3. 정렬의 시간복잡도

3.1 선택정렬

최소값 1번 찾는데 O(N)번 * N번 > O(n^2)

3.2 삽입정렬

원소 하나 삽입 시 O(N)걸림 * N번 > O(n^2)

3.3 버블 정렬

인접한 원소 비교해서 뒤로 보냄 O(n) 걸림 * n번 > O(n^2)

• 선택, 삽입, 버블 정렬은 시간복잡도가 안 좋은편!!