[바킹독의 실전 알고리즘 | 0x01강] 기초코드 작성 요령1 복습

 

 

1. 시간복잡도란?

입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 말한다.

• 컴퓨터는 1초에 대략 3~5억 개의 연산 처리 가능 (연산의 종류에 따라 약간의 차이 존재)
• 코딩 테스트 문제에서 시간제한이 1초로 주어졌다면, 연산의 횟수가 3~5억 개를 넘어가지 않도록 코드를 작성해야 함.

int func1(int arr[], int n){
	int cnt = 0;		// cnt 변수 선언 및 0 할당 -> 연산 1회
    for (int i = 0; i < n; i++){ 		// i 초기값 0 대입 -> 연산 1회
    	if (arr[i] % 5 == 0) cnt++;		
        // i가 n보다 작은지 확인, 작은 경우 1 증가 -> 연산 2n회
        // 5로 나눈 나머지 계산 후, 0인지 확인 -> 연산 2n회
        // 나머지가 0인 경우 cnt 변수 1 증가 -> 연산 n회
    }
    return cnt;			// cnt 변수 반환 -> 연산 1회
}

• 위 함수는 총 연산 5n+3 번에 걸쳐 cnt 변수를 반환 → n에 비례
  • 입력되는 n의 크기가 100만인 경우 500만 번의 연산을 수행하므로, 1초 안에 충분히 동작 가능.
  • 만약 n의 크기가 10억이 넘는 경우 50억 번의 연산을 수행하므로 수행 시간이 1초를 넘게 됨
• 'n에 비례'와 같이 대표항으로 연산의 횟수를 나타내는 방법을 빅오 표기법이라 함.
  • O(N): 5N + 3, 2N + 10lgN, 10N
  • O(N^2): N^2 + 2N + 4
  • O(NlgN): NlgN + 30N + 10, 5NlgN + 6
  • O(1): 5, 16, 36
• O(1) < O(lgN) < O(N) < O(NlgN) < O(N^2) < O(2^N) < O(N!) 순으로 수행 시간 증가함

N의 크기	허용 시간 복잡도
N ≤ 11	O(N!)
N ≤ 25	O(2^N)
N ≤ 100	O(N^4)
N ≤ 500	O(N^3)
N ≤ 3,000	O(N^2lgN)
N ≤ 5,000	O(N^2)
N ≤ 1,000,000	O(NlgN)
N ≤ 10,000,000	O(N)
그 이상	O(lgN), O(1)

 

 

2. 공간복잡도란?

입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계를 말한다.

• 메모리 제한이 512MB일 때, int 변수를 대략 1.2억개 선언할 수 있다 (int 1개 = 4 byte)

 

 

3. 정수자료형

• char 자료형은 1 byte = 8bit 이다. 즉, 8자리 2진수로 표기할 수 있다.
• char의 경우, -2^7 부터 2^0 까지의 범위를 사용한다. (-128~127)

-2^7

2^6

2^5

2^4

2^3

2^2

2^1

2^0

• unsigned char의 경우, 0부터 2^7 까지의 범위를 사용한다. (0~255)

2^7

2^6

2^5

2^4

2^3

2^2

2^1

2^0

• 컴퓨터로 음수의 계산을 구현하기 위해 위와 같은 방식을 사용한다 (2's complement)
• short (2 byte): 2^15 - 1 (=32767)
• int (4 byte): 2^31 - 1 (=2.1*10^9)
• long long (8 byte): 2^63 - 1 (=9.2*10^18)

 

 

4. 실수자료형

• float (4 byte)
• double (8 byte)
• 컴퓨터는 소수를 다음과 같은 방식으로 나타냄
  • 3.75 = 2 + 1 + 0.5 + 0.25 = 2^1 + 2^0 + 2^(-1) + 2^(-2) = 11.11(2)
  • 1/3 = 2^(-2) + 2^(-4) + 2^(-6) + 2^(-8) + ... = 0.010101...(2)
• 컴퓨터는 과학적 표기법을 다음과 같은 방식으로 나타냄
  • 3561.234 = 3.561234 * 10^3 은 2진수에서 11101.001(2) = 1.1101001(2)  × 2^4
  • float의 경우 sign(1), exponent(8), fraction field(23), double의 경우 sign(1), exponent(11), fraction field(52) 의 필드에 나누어서 표기함
  • sign field는 양수/음수 표기, exponent field는 지수 표기, fraction field는 유효숫자 표기
  • 해당 방식을 IEEE-754 format이라 함
• 실수는 위와 같은 방식으로 나타내기 때문에, 연산 및 저장 과정에서 오차가 발생하여 누적되는 구조임
  • 0.1 + 0.1 + 0.1 ≠ 0.3 (0.1은 무한소수로 나타내기 때문)
  • a == b 등호 대신 abs(a - b) < 1e-12 와 같이 사용할 것
• float의 경우, 유효숫자는 6자리이고 double의 경우, 유효숫자는 15자리이다.