개발자의 미국살이

알고리즘 문제를 풀고나서 설명을 할때 꽤 자주 면접에 들어온 엔지니어들이 해당 코드의 시간 복잡도나 공간 복잡도에 대해서 물어볼때가 있다. 그래서 시간 복잡도는 무엇인지 그리고 공간 복잡도는 무엇이고 계산을 어떻게 하는지 적어보려고 한다. 

1. 시간  복잡도란?

코드를 작성했다고 치자. 해당 코드의 실행시간을 수학적으로 풀어쓴 것이라고 보면 된다. 좀더 정확히 말해서, 코드의 실행 시간이 얼마나 걸릴것인지를 시간 복잡도라고 한다. 입력 크기 n에 따라 알고리즘이 실행되는 데 필요한 연산 횟수이다. 

보통은 최악의 경우를 기준으로 분석하고 빅오 표기법을 사용한다.

2. 시간 복잡도 계산법

- 코드에서 반복문과 연산 횟수를 기준으로 연산량을 세어보면된다. 

int getFisrtElement(int arr[], int n) {
	return arr[0]; // 항상 0번째 요소를 반환
}

만약 위처럼 단순히 배열이 들어오면 0번째 요소를 반환하는 함수가 있다고 가정한다면. 해당 함수의 실행시간은 배열의 길이에 상관없이 항상 한번만 연산을 하면 된다. 따라서 위 함수의 시간 복잡도는 O(1)이다. 이는 "상수 시간"으로 읽기도 한다. 

코드 상에서는 반복문을 실행할 일이 많다. for문, while문들이 있는데 이 경우에도 총 연산횟수로 계산하면된다. 

int sumArray(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) { // n번 반복
        sum += arr[i];
    }
    return sum;
}

반복문이 n번 실행되기 때문에 O(n)으로 볼 수 있다. 이럴 경우 이 sumArray함수의 시간 복잡도는 n에 선형적으로 비례한다고 말할 수 있다. 그리고 만약 for문 안에 for문이 하나 더 있다면 n의 제곱이 된다.

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

Binary Search(이진 탐색)를 할 경우에는 범위가 매번 절반으로 줄어든다. 따라서 이 경우 시간은 log n으로 표기한다.

3. 공간 복잡도란?

입력 크기 n에 따라 알고리즘이 사용하는 메모리 공간의 양을 나타낸다. 보통 사용하는 변수, 배열, 재귀 호출 스택 등을 기준으로 계산한다. 

4.  공간 복잡도 계산법

고정 공간, 가변 공간으로 나눠서 계산할 수 있는데 고정 공간이란 입력 크기와 무관하게 항상 사용되는 공간이고 가변 공간은 입력 크기에 따라 변하는 공간을 말한다. 

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1); // 재귀 호출
}

재귀 호출이 n에서 0까지 호출 스택에 쌓이기 때문에 O(n) 공간을 사용한다. 

C++로 Array, Structure, Pointer, Function 관련해서 정리를 해보았다.

Array란?

배열(Array)은 하나의 자료구조로 "연속적인" 자료구조이다. 그게 무슨 말이냐 하면, 메모리에 저장될때 순서대로 물리적인 공간 상에 저장된다는 말이다.

예를 들어..

int foo [5] = { 16, 2, 77, 40, 12071 }; // 초기화

16, 2, 77, 40, 12071은 모두 메모리상에 실제로 순서대로 저장된다. 하지만 이건 언어들에 따라 다르다. 아마 Python같은 언어들은 이미 List같은 자료형들이 Linked List같은 형태로 되어있는걸로 알고있다. Linked List는 참고로 하나의 자료구조로 각 요소들이 주소로 연결되어있는 연속적인 자료구조이다.

C++에서 Array의 요소에 접근할때는 index로 접근이 가능하다, 다른 언어들처럼.

foo[1] // 16

초기화하지 않은 요소들은 모두 0으로 초기화된다

int main() {

    int foo[5] = {1,2,3};

    for(int i : foo)
    {
        cout<<i<<endl;
    }

    return 0;
}

위 코드의 출력화면은 다음과 같다.

1
2
3
0
0

Structure란?

영어로는 Structure, 한국어로는 구조체이다.

C언어에서는 Class가 없기 때문에 구조체로 객체와 비슷하게 만들어서 사용할 수 있는데 C++에서도 C언어의 기능을 사용할 수 있다. struct라는 키워드를 사용해서 선언한다.

struct Circle
{
    double x; // 좌표점 x
    double y; // 좌표점 y
    double radius; // 반지름
};

Circle이라고 하는 구조체의 예시.

그럼 구조체를 정의했으니 구조체 하나를 선언후 값들을 출력해보자.

int main() {

    struct Circle c = { 0, 0, 5}; // 선언과 동시 초기화

    cout<<c.x<<endl<<c.y<<endl<<c.radius<<endl;

    return 0;
}

출력 결과는 다음과 같다.

0
0
5

만약 우리가 Circle c의 area값을 출력하고 싶다면 3.14를 곱해서 할 수 있다.

cout<<c.radius*c.radius*3.14<<endl;

Pointer란?

포인터라는 개념은 C,C++에서 가장 중요한 개념이다. 사실 이걸 배우기 위해서 Reference라는 개념도 배우고 문자열, Stack, Heap이라고 하는 단어들을 알고 있어야 한다. 그래서 혹시 용어들을 모른다면 반드시 Reference, Stack, Heap에 대해서 검색하고 찾아봐라.

포인터란 주소 변수로 메모리 주소에 들어가있는 실제 데이터를 저장하지 않는다. 즉, 메모리 주소만 저장하는 변수이다.
포인터는 데이터를 직접적으로 접근하지 않을때 사용하고 또한 유용하다. 특히, Heap영역에 있는 데이터에 접근할때 포인터가 사용된다.

int main() {

    int num1 = 100;
    int arr[5] = {10, 20, 30, 40, 50};

    int *p1; // p1라고 하는 포인터 변수 선언
    int *p2; // p2 포인터 변수 선언

    p1 = arr; // arr변수의 주소를 p1에 할당
    p2 = &num1; // num1의 주소를 p2에 할당

    cout<<p1<<endl; // arr의 첫번째 메모리 주소가 출력됨.
    return 0;
}

위의 예시에서 arr는&를 앞에 붙이지 않았는데 이건 배열의 경우 arr가 이미 주소를 담고 있기 때문에 그렇다. 그래서 p2에 num1의 주소를 할당할때는 int형 num1변수의 주소를 참조(reference)하기 위해서 &(주소연산자)를 넣어준다.

결국 메인메모리 바깥에 접근하기 위해서는 포인터를 사용할 수 밖에 없다.

구조체와 포인터

 struct Rectangle r = {10, 5};
 struct Rectangle *p;

 p = &r; // 0x7ffd1fdb4970 메모리 주소
 r.length = 15;
 p->breadth = 20;

 cout<<p<<endl<<p->length<<endl<<p->breadth<<endl;

위의 출력 결과는

0x7ffd1fdb4970
15
20

이다

메모리 접근 -> 문법은 익숙해져놓는게 좋다.

Function

함수는 가장 기본적인 형태의 모듈로 어떠한 값을 return하는 구조이다. 코드를 작은 단위로 쪼갤때 사용하고 function을 사용해서 각 코드의 기능을 작게 나누는건 좋은 코딩습관이다.

int add(int a, int b) {
    return a + b;
}

int main() {

    int x = 5;
    int y = 10;

    printf("%d", add(x, y));

    return 0;

}