[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

2022. 1. 20. 02:59ㆍAlgorithm/1강

1. 시간, 공간복잡도

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

빅오표기법 - 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법을 의미한다.
ex) O(N) : 5N + 3

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

시간복잡도 - O(N)

for문 1번을 돌아 O(N).

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

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

(N-1) + (N-2) + ... + 3 + 2 + 1 = N(N-1)/2 => O(N^2)

for문 2번을 돌아 O(N^2)

int func3(int N)
{
    for (int i = 1; i < N / 2; i++)
    { // i * i <= N is better for the time complex.
        if (i * i == N)
        {
            return (1);
        }
    }
    return (0);
}

시간복잡도 - O(√N)

사실 내 코드에서는 N/2 => O(N) 의 시간복잡도를 가지지만 i * i <= N 을 조건으로 활용하면 최대 √N의 시간복잡도를 가진다.

처음 코드. 2번째 테스트 케이스에 대해 wrong answer이 떴다. i*2 를 이용하다보니 거듭제곱도 충족하지 못한 코드이다.

int func4(int N)
{
    int ret = 1;
    for (int i = 1; i * 2 <= N; i++)
    {
        ret = i * 2;
    }
    return (ret);
}

while 문을 돌려서 ret 값을 바로 2씩 곱하여 조건 충족이 끝났을 때 바로 리턴하게 수정했다.

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

시간복잡도 - O(lgN)

N이 2^k 이상 2^(k+1) 미만이라고 할 때 while문 안에서 ret은 최대 k번 커지게 된다. 그러니까 N이 2^k 이상 2^(k+1) 미만이라고 할 때 시간복잡도가 O(k)이고 로그의 정의에 입각해서 생각할 때 k는 lgN이니 결국 시간복잡도는 O(lgN)이 된다.

바킹독님이 올려주신 테스트 코드

#include <bits/stdc++.h>
using namespace std;

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

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

int func3(int N)
{
    for (int i = 1; i < N / 2; i++)
    { // i * i <= N is better for the time complex.
        if (i * i == N)
        {
            return (1);
        }
    }
    return (0);
}

int func4(int N)
{
    int ret = 1;
    for (int i = 1; i * 2 <= N; i++)
    {
        ret = i * 2;
    }
    return (ret);
}

void test1(){
  cout << "****** func1 test ******\n";
  int n[3] = {16, 34567, 27639};
  int ans[3] = {60, 278812814, 178254968};
  for(int i = 0; i < 3; i++){
    int result = func1(n[i]);
    cout << "TC #" << i << '\n';
    cout << "expected : " << ans[i] << " result : " << result;
    if(ans[i] == result) cout << " ... Correct!\n";
    else cout << " ... Wrong!\n";
  }
  cout << "*************************\n\n";
}

void test2(){
  cout << "****** func2 test ******\n";
  int arr[3][4] = {{1,52,48}, {50,42}, {4,13,63,87}};
  int n[3] = {3, 2, 4};
  int ans[3] = {1, 0, 1};
  for(int i = 0; i < 3; i++){
    int result = func2(arr[i], n[i]);
    cout << "TC #" << i << '\n';
    cout << "expected : " << ans[i] << " result : " << result;
    if(ans[i] == result) cout << " ... Correct!\n";
    else cout << " ... Wrong!\n";
  }
  cout << "*************************\n\n";
}

void test3(){
  cout << "****** func3 test ******\n";
  int n[3] = {9, 693953651, 756580036};
  int ans[3] = {1, 0, 1};
  for(int i = 0; i < 3; i++){
    int result = func3(n[i]);
    cout << "TC #" << i << '\n';
    cout << "expected : " << ans[i] << " result : " << result;
    if(ans[i] == result) cout << " ... Correct!\n";
    else cout << " ... Wrong!\n";
  }
  cout << "*************************\n\n";
}

void test4(){
  cout << "****** func4 test ******\n";
  int n[3] = {5, 97615282, 1024};
  int ans[3] = {4, 67108864, 1024};
  for(int i = 0; i < 3; i++){
    int result = func4(n[i]);
    cout << "TC #" << i << '\n';
    cout << "expected : " << ans[i] << " result : " << result;
    if(ans[i] == result) cout << " ... Correct!\n";
    else cout << " ... Wrong!\n";
  }
  cout << "*************************\n\n";
}

int main(void){
  test1();
  test2();
  test3();
  test4();
}

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

공간복잡도는 시간복잡도에 비해 크게 신경쓰지 않아도 괜찮지만 몇 가지는 유의하자.

메모리 제한이 512MB일 때 int 변수를 대략 1.2억개 정도 선언할 수 있다는 것을 기억해두시는게 좋다. 만약 떠올린 풀이가 크기가 5억인 배열을 필요로 할 때 해당 풀이는 주어진 메모리 제한을 만족하지 못하므로 틀린 풀이라는 것을 빠르게 깨닫고 다른 풀이를 고민할 수 있다.

2. 정수 자료형

char - 1 Byte(8 bit) (-127 ~ 126)
unsigned char - 1 Byte (0 ~ 255)
short - 2 Byte (2^15 - 1 = 32767)
int - 4 Byte (2^31 - 1 = 2.1×109 = 21억)
long long - 8 Byte (2^63 - 1 = 9.2×1018)

Interger Overflow

interger overflow 가 발생하는 함수는?

1, 3번이다

func1 - s가 127이 된 후에 1이 더해질 때 127에서 1이 더해지면 -128이기 때문에 의도한대로 동작하지 않고 무한루프에 빠진다. 이를 해결하려면 s의 자료형을 char에서 int로 바꿔야 한다.

func3 - a가 10^9일 때 여기서 10이 곱해지는 순간 int의 최대 범위를 넘어서서 Integer Overflow가 발생한다. 이걸 막으려면 a의 자료형을 long long으로 바꾸거나, 07번 줄에서 10 대신 10ll 혹은 (long long)10으로 강제 형변환을 시키면 해결할 수 있다.

3. 실수 자료형

float - 4 Byte
double - 8 Byte

실수를 만드는 방법

2^1+2^0+2^(-1)+2^(-2) 과 같이 계산한다.

실수의 과학적 표기법

1.xxxx * 2^x

실수를 저장하는 방식

IEEE-754 format 방식 사용.

double 64개의 bit를 각각 다음과 같이 나눈다.

sign(1) exponent(11) fraction(52)

실수의 성질들

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

대표적인 예로 0.1+0.1+0.1이 0.3과 다르다고 출력된다. 유효숫자가 들어가는 fraction field가 유한하기 때문에 2진수 기준으로 무한소수인걸 저장하려고 할 때에는 어쩔 수 없이 float은 앞 23 bit, double은 앞 52 bit까지만 잘라서 저장할 수 밖에 없다. 0.1은 이진수로 나타내면 무한소수여서 애초에 오차가 있는 채로 저장이 됐고 그걸 3번 더하다보니 오차가 더 커져서 이상한 결과가 나온다.

fraction field를 가지고 각 자료형이 어디까지 정확하게 표현할 수 있는지 보면 float은 유효숫자가 6자리이고 double은 유효숫자가 15자리다. 즉, float은 상대 오차 10^(-6)까지 안전하고 double은 10^(-15)까지 안전하다는 소리.

위에서 보듯 실수 자료형이 필요하면 꼭 float 대신 double을 써야한다. float이 메모리를 적게 쓴다는 장점은 있지만 알고리즘 문제를 풀때 영향이 크지는 않음. 오히려 overflow 발생 가능하니까 double 사용을 권고한다.

또 실수 자료형은 필연적으로 오차가 있으니까 실수 자료형이 필요한 문제면 보통 문제에서 절대/상대 오차를 허용한다는 단서를 준다. 그런데 만약 이런 표현이 없다면 열에 아홉은 실수를 안쓰고 모든 연산을 정수에서 해결할 수 있는 문제일 것이다.

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

double은 유효숫자가 15자리인데 long long은 최대 19자리니까 1018+1과 1018을 구분할 수가 없고 그냥 같은 값이 저장된다. 즉, double에 long long 범위의 정수를 담을 경우 오차가 섞인 값이 저장될 수 있다. 다만 int는 최대 21억이기 때문에 double에 담아도 오차가 생기지 않는다.

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

0.1+0.1+0.1과 0.3이 일치하지 않았던걸로 이미 봤듯이, 오차 때문에 두 실수가 같은지 알고 싶을 때에는 둘의 차이가 아주 작은 값, 대략 10^(-12) 이하면 동일하다고 처리를 하는게 안전하다.

1e-12 = 10^(-12)

참고자료