[바킹독 실전 알고리즘 0x01] 기초 코드 작성 요령 I

시간, 공간복잡도를 고려하라

• 대략적인 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)

• 코드를 짤 때 풀이가 주어진 시간 내에 실행될 수 있는지, 즉, 풀이의 시간복잡도가 올바른지 반드시 고려해야 한다.
• 예를 들어, N이 500인데 O(2^N)의 시간복잡도를 가지는 풀이를 떠올렸다면 코드가 실행되는 데 시간이 너무 오래 걸릴 것이다. (코딩 테스트의 경우 시간초과가 생긴다.) 따라서 풀이법이 생각났다고 무작정 구현하기보다는 적절한 시간 복잡도를 가지는 풀이인지 먼저 확인해야 한다.

 

• 연습문제 1
  • N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 10만 이하의 자연수이다. 
  • Test Case: func1(16) = 60, func1(34567) = 278812814, func1(27639)

#include <stdio.h>
#include <stdlib.h>

func1(int N) {
	int i;
	int sum = 0;
	for (i = 1;i <= N;i++) {
		if ((i % 3 == 0) || (i%5 ==0)) {
			sum += i;
		}
	}
	return sum;
}
void main() {
	printf("func1(16) = %d\n", func1(16));
	printf("func1(34567) = %d\n", func1(34567));
	printf("func1(27639) = %d\n", func1(27639));
}

빅오표기법으로 표현한 시간복잡도는 O(N)이다.

 

• 연습문제 2
  • 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 하수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.
  • Test Case: func2({1,52,48},3) = 1, func2({50,42},2) = 0, func2({4,13,63,87},4) = 1

func2(int arr[],int N) {
	int i, j;
	int res =0;
	for (i = 0;i < N;i++) {
		for (j = i + 1;j < N;j++) {
			if (arr[i] + arr[j] == 100) {
				res= 1;
			}
		}
	}
	return res;
}

빅오표기법으로 표현한 시간복잡도는 O(N^2)이다.

 

• 연습문제 3
  • N이 제곱수이면 1을 반환하고 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. N은 10억 이하의 자연수이다.
  • Test Case: func3(9) = 1, func3(693953651) =0, func3(756580036) = 1

int func3(int N){
	for(int i=1;i*i<=N;i++){
    	if(i*i == N) return 1;  //정수 1부터 1씩 증가시키면서 그 제곱수가 N과 일치하는지 비교한다.
    }
    return 0;
}

i 가 1, 2, 3, ... , N^(1/2)까지 증가할테니 시간복잡도는 O(N^(1/2))이다.

 

• 연습문제 4
  • N 이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.
  • Test Case: func4(5) = 4, func4(97615282) = 67108864, func4(1024) = 1024

func4(int N){
	int val=1;
    while(2*val <= N){
    	val *= 2;
    }
    return val;
}

빅오표기법으로 표현한 시간복잡도는 O(logN)이다.

 

공간복잡도: 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

• 예를 들어, 크기 N짜리 2차원 배열이 필요하다면 O(N^2)이고, 배열이 필요 없다면 O(1)이다.
• 코딩 테스트에서 메모리 제한이 512MB일 때, 약 1.2억개의 int를 선언할 수 있다는 것을 알아두자.(int 1개가 4byte임을 사용해 계산할 수 있다.)

 

정수 자료형

• char 자료형은 1byte(=8bit)이다. 
• signed char의 경우 MSB가 2^7이 아닌 -2^7을 나타낸다. 

• 8bit unsigned char 자료형의 범위는 0 ~ 2^8-1(=255), char 자료형의 범위는 -2^7(=-128) ~ 2^7-1(=127)이다.
• 이외에도 short형(2byte), int형(4byte), long long형(8byte)가 존재한다.

 

실수 자료형

• 실수 자료형에는 float(4byte)과 double(8byte)이 있다.
• 10진수에서도 표기상의 편의를 위해 3561.234를 3.561234 X 10^3 으로 표기하는 것처럼, 소수점을 가지는 2진수 11101.001도 1.1101001 X 2^4와 같이 표기할 수 있다. 2진수 실수를 이렇게 표기한 후 아래 사진에 나타난 구간의 자리에 맞게 표현하면 된다.

• sign 필드: 해당 수가 음수인지 양수인지 저장한다. 음수는 1, 양수는 0의 값을 가진다.
• exponent 필드: 과학적 표기법에서의 지수를 저장한다. 지수에 127을 더한 수를 이 자리에 저장한다.
• fraction 필드: 유효숫자 부분을 저장한다. 소수점 이후 부분만 저장한다.
• 예를 들어 10진수 -6.75를 float형 2진수로 기록한다고 하자. -6.75는 2진수로 -1.1011 X 2^2 라고 표현할 수 있다. 음수이므로 sign field의 값은 1, 지수는 2이므로 exponent field의 값은 2+127=129, fraction field의 값은 101100000...이다.

 

실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.

• 0.1+0.1+0.1 == 0.3 의 진리값은 false이다. 0.1은 2진수로 표현하면 무한소수이기 때문에 어쩔 수 없이 float은 앞의 23bit, double은 앞의 52bit밖에 저장하지 못한다. 애초에 부정확한 값이 메모리에 저장되고, 이를 세 번 더한 값은 오차가 더욱 커졌을테니 0.3과 값이 일치하지 않는다는 결과를 얻게 되었다.
• float은 유효숫자가 6자리이고, double은 유효숫자가 15자리이다. 이것은 float은 상대 오차 10^(-6)까지 안전하고, double은 상대 오차 10^(-15)까지 안전하다는 것을 의미한다.
• 실수 자료형은 필연적으로 오차가 발생하므로 실수 자료형을 써야 하는 문제에서는 보통 절대/상대 오차를 허용한다는 단서를 준다. 만약 이런 표현이 없다면 거의 대부분의 경우는 정수로만 문제를 해결 가능하다는 의미일 것이다.

double에 long long 범위의 정수를 함부로 담으면 안된다.

• double은 유효숫자가 15자리이고, long long은 19자리이기 때문이다. double에 long long형의 값을 저장하면 오차가 섞인 값이 저장될 수 있다. 다만 int는 double에 담아도 오차가 생기지 않는다.

실수를 비교할 때는 등호를 사용하면 안된다.

• 0.1+0.1+0.1 == 0.3 이 거짓임을 통해서도 알 수 있는 부분이다. 오차 때문에 두 실수 가 같은지 알고 싶을 때에는 보통 오차가 아주 작은 값, 예를 들어 10^(-12) 이하이면 동일하다고 처리하는 게 안전하다. 10^(-12)는 1e-12로도 표현할 수 있다. 다른 수, 예를 들어 10^9도 1e9로 표기해도 된다.