Unity 내일배움캠프 TIL 1107 | 시간 복잡도와 공간 복잡도 | 자료형

오늘부터는 알고리즘 개념을 한 번 더 복습하고 정리하기 위해 아래 강의를 듣기 시작했당
[바킹독의 실전 알고리즘] 0x01강 - 기초 코드 작성 요령 1

💡 시간 복잡도와 공간 복잡도

🍰 시간 복잡도 (Time Complexity)

• 입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관 관계
• 컴퓨터는 1초에 대략 3-5억 개 정도의 연산을 처리할 수 있다.

int func1(int arr[], int n) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i] % 5 == 0) cnt++;
	}
	return cnt;
}

• 위 코드는 5n + 3의 시간 복잡도를 가진다.
  → n에 비례

🧁 빅오표기법 (Big-O Notation)

• 주어진 식을 값이 가장 큰 대표 항만 남겨서 나타내는 방법

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

• 문제 1
  • N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 10만 이하의 자연수이다.
  • 코드

    int func1(int N)
    {
    	int sum = 0;
        for (int i = 1; i <= N; i++)
        {
        	if (i % 3 == 0 || i % 5 == 0) sum += i;
        }
        return sum;
    }

    • 시간 복잡도 : $O(N)$

• 문제 2
  • 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라.
    arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.
  • 코드

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

    • 시간 복잡도 : $O(N^2)$

• 문제 3
  • N이 제곱수이면 1을 반환하고 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. N은 10억 이하의 자연수이다.
  • 코드

    int func3(int N)
    {
    	int isSquare = 0;
      for (int i = 1; i <= N / 2; i++)
      {
      	if (i * i == N)
          {
          	isSquare = 1;
              break;
          }
      }
      return isSquare;
    }

    • 시간 복잡도 : $O(\sqrt{N})$

• 문제 4
  • N 이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.
  • 코드

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

    • 시간 복잡도 : $O(logN)$

🍮 공간 복잡도

• 입력의 크기와 문제를 해결하는 데 필요한 공간의 상관 관계
• 보통 시간 복잡도 문제가 많이 나오고 많이 틀림
• 기억할 것 : 메모리 제한이 512MB일 때 int 변수를 대략 1.2억 개 정도 선언할 수 있음
  • int 1개 == 4byte

💡 자료형

🍪 정수 자료형

• 정수 표현 시에는 주로 int나 long을 사용
  • int는 long보다 연산 속도와 메모리 모두 우수하지만 , 표현 범위를 넘어서게 되면 long 자료형을 사용해야 함
• Integer Overflow
  
  • 막는 방법 : 각 자료형 범위에 맞는 값을 가지도록 연산

• 문제

  • 다음 중 Integer Overflow가 발생하는 함수는?

    // 1
    // 128번에 걸쳐 hi를 출력
    void func1() {
    	for (char s = 0; s < 128; s++) {
        	cout << "hi";
        }
    }

    //2
    // 50!을 61로 나눈 나머지를 반환
    int func2() {
    	int r = 1;
        for (int i = 1; i <= 50; i++) {
        	r = r * i % 61;
        }
        return r;
     }

    // 3
    // 10의 거듭제곱을 1000000007로 나눈 나머지를 반환
    int func3() {
    	int a = 10;
        int mod = 1000000007;
        for (int i = 0; i < 10; i++) a = 10 * a % mod;
        return a;
    }

  • 정답 : 1, 3번

    • 1번 : s의 자료형을 char에서 int로 바꿔야 함
    • 3번 : a가 $10^9$일 때 10이 곱해지는 순간 int의 최대 범위를 넘어서게 됨
      → a의 자료형을 long long으로 바꾸거나, 7번째 줄에서 10 대신 10ll 혹은 (long long)10으로 강제 형변환

🍩 실수 자료형

• float (4 byte)
• double (8 byte)
• 컴퓨터가 실수를 저장하는 방법
  
  • sign : 부호 비트
  • exponent : 과학적 표기법에서의 지수를 저장
  • fraction : 유효 숫자
  • exponent에 지수를 기록할 때 127을 더해서 기록
    • why? 음수 지수승도 표현하기 위해
• 실수 자료형의 성질
  1. 실수의 저장/연산 과정에서 반드시 오차가 발생
     (ex: 무한 소수)
     - float은 유효 숫자 6자리, double은 유효 숫자 15자리
     - double을 예로 들면, 참 값이 1일 때 $1 - 10^{-15}$ ~ $1 + 10^{-15}$ 사이의 값을 가지는 것이 보장된다는 의미
     → 실수 자료형이 필요하다면 float 대신 double을 사용할 것
     → 만약 메모리 효율이 중요하다면 float을 사용하겠지만, 웬만하면 double로 문제 해결이 됨
     

  • 위와 같은 단서가 없다면 보통 정수 자료형으로 해결되는 문제

    
    

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

     • double은 유효 숫자 15자리, long long은 19자리이므로$10^{18} + 1$과 $10^{18}$을 구분할 수 없게 됨
     • int는 최대 21억이므로 double에 담아도 오차가 생기지 않음
     
     

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

     • 두 실수가 같은지 비교하고 싶을 때는 둘의 차이가 $10^{-12}$ 이하면 동일하다고 처리하는 것이 안전

     int main(void) {
     	double a = 0.1 + 0.1 + 0.1;
         double b = 0.3;
         if (a == b) cout << "same 1\n";
         if (abs(a-b) < 1e-12) cout << "same 2\n";
     }
     
     // result : same 2

오늘은 여기까지~

끗!