CS 강의 11. 공간 자원과 공간 복잡도

출처 : 내일배움캠프

 

1. 공간 복잡도

1 - 1. 공간 복잡도 개요

- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다

= > 프로그램 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다

시간 복잡도 : 얼마나 빠르게 실행되는지

공간 복잡도 : 얼마나 많은 저장 공간이 필요한지

 

~ 통상 둘 다를 모두 만족하기는 어렵다

- 시간과 공간 복잡도는 반비례하는 경향이 있다

- 최근 대용량 시스템이 보편화되며, 공간 복잡도보다 시간 복잡도가 낮은 것이 우선되는 추세

- 알고리즘 풀이시, 시간 복잡도를 우선하자

- 다만, 그렇다고 공간 복잡도를 소홀히 하면 안된다

 

총 필요한 저장공간

- 고정 공간(알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수

- 가변 공간(알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간

S(P) = c + Sp(n) ~ c : 고정 공간, Sp(n) : 가변 공간

- 고정 공간은 상수이므로 공간 복잡도는 가변 공간의 크기에 따라 달라진다

1 - 2. 공간 복잡도 예시 : 빅 오 표기법

1) O(n) 공간 복잡도 예시

n! 팩토리얼 구하기

- 재귀 함수를 통해 구현하므로 변수 n에 따라 변수 n이 n개 만들어진다

- factorial 함수를 재귀 함수로 1까지 호출한 경우, n부터 1까지 스택에 쌓인다

- 따라서 공간 복잡도는 O(n)

public int factorial(int n) {

    if(n == 1) {
        return n;
    }

    return n*factorial(n-1);
}

 

배열에서 n인덱스 이전까지 합 구하기

- 사용되는 변수는 a[], n, result, i이다

- (a[]의 n개의 원소를 저장할 공간) + (변수 n, i, result를 위한 공간)이 필요하다. a[]가 n보다 큰 공간을 할당해야하므로 O(n)만큼의 공간 복잡도가 필요하다

public int sum(int a[], int n){
    int result =0;
    for(int i=0; i<n ; i++){
        result += a[i];
    }

    return result;
}

 

2) O(n) 공간 복잡도 예시

n! 팩토리얼 구하기 (반복문 버전)

- 반복문을 통해 구현하므로 result에 저장하기 때문에 공간 복잡도는 O(1)이다

- 사용하는 변수 n, i, result

public int get_factorial(int n)
{
    int i = 0;
    int result = 1;

    for(i = 1; i <= n; i++)
    {
        result = result * i;
    }
    return result;
}

1 - 3. 공간 복잡도 적용

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

- 크기 N의 2차원 배열은 O(N^2), 배열이 없다면 O(N)이다

- 보통 데이터 영역이 스택 영역보다 크기 때문에 큰 배열은 전역 변수로 선언한다. 스택 영역에 큰 배열을 저장하면 메모리 초과가 발생할 수 있기 때문이다

- 메모리는 직접 계산해보면 된다. 512MB의 경우 1.2억 개의 int가 들어간다

- 보통 100MB 이상이 주어지면 메모리를 신경쓰지 않아도 되는 수준이다. 하지만 2MB처럼 메모리가 적게 주어지는 경우 메모리 최적화를 해줘야 한다. 2MB를 int로 나누면 50만 개 정도빆에 들어가지 못하므로 스택 내 배열 사용을 주의해야 한다

- 문제풀이 시 "제한조건 확인"시 공간 복잡도 계산을 해야한다

1) 빅 오 표기법

- 빅 오 표기법은 데이터가 늘어날 때 단계 수가 어떻게 증가하는 지를 의미한다

 

** O(3) == O(100) == O(1)

~ 데이터(원소)가 몇 개던지 항상 3단계인 알고리즘이 있을 때, 빅 오 표기법에 따르면 무조건 O(1)이다

O(1)은 원소 개수에 관계없이 수행에 상수 시간을 가지는 알고리즘이다

O(N)은 데이터가 추가될 때마다 알고리즘도 한 단계씩 추가된다

 

=> O(N)은 데이터의 수가 같아도 알고리즘의 단계가 다르기 떄문에 항상 O(1)보다 비효율적이다

 

+ 선형 검색이 항상 O(N)은 아니다. 찾는 값이 배열의 맨 앞에 있으면 O(1), 맨 마지막에 있을 때 O(N)이다

~ 일반적으로 최악의 경우를 말한다

 

2) O(logN) == O(log2N) ~ 같은 말

- O(logN)데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?

= 알고리즘 단계가 log2 N이다

~ 원소가 8개면 log2 8이므로 3단계

* 이진 검색이 정확하게 O(logN)으로 작동한다

=> 데이터가 커질 수록 단계도 증가하므로 O(1)이라고 할 수 없으며, O(N)보다 단계가 느리게 증가하므로 O(N)도 아니다

=> 데이터가 두배로 증가할 때마다 단계는 한 단계씩 증가한다

 

// 예시 1번
public static void main(String[] args) {
  // n 입력
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += i;
  }
  System.out.println(sum);
}

=> O(1) 공간 복잡도 : 입력 값 n에 관계없이 동일한 메모리를 사용

 

// 예시 2번
public static void main(String[] args) {
  // n 입력
  int[] arr = new int[n];
  for (int i = 0; i < arr.length; i++) {
    arr[i] = i;
  }
  for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
  }
}

=> O(n) 공간 복잡도 : 입력 값 n에 따라 메모리(배열)의 크기가 달라지므로 O(n)

 

// 예시 3번
public static void main(String[] args) {
  // n 입력
  int[][] arr = new int[n][n];
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr[i].length; j++) {
      arr[i][j] = i * j;
    }
  }
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr[i].length; j++) {
      System.out.println(arr[i][j]);
    }
  }
}

=> 2차원 배열의 경우 : O(n^2), 입력 값 n에 따라 배열 크기가 n^2로 증가한다

 

public static void main(String[] args) {
  // n 입력
  boolean[] isPrime = new boolean[n + 1];
  for (int i = 2; i <= n; i++) {
    if (!isPrime[i]) {
      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = true;
      }
    }
  }

  for (int i = 2; i <= n; i++) {
    if (!isPrime[i]) {
      System.out.println(i);
    }
  }
}

=> O(n log n) : 소수 판별에 사용하는 배열의 크기가 n log n으로 증가

 

import java.util.HashSet;

public class FindDuplicateNumbers {
    public static int[] findDuplicates(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> duplicates = new HashSet<>();

        for (int num : arr) {
            if (set.contains(num)) {
                duplicates.add(num);
            } else {
                set.add(num);
            }
        }

        int[] result = new int[duplicates.size()];
        int index = 0;
        for (int num : duplicates) {
            result[index] = num;
            index++;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4, 2, 3 ...}; // k개가 중복된 n개의 숫자
        int[] duplicates = findDuplicates(arr);
        System.out.print("중복된 숫자: ");
        for (int num : duplicates) {
            System.out.print(num + " ");
        }
    }
}

=> O(k), k개가 중복된 n개의 숫자에 비례하는 알고리즘이므로 k에 따라 메모리의 크기가 결정된다

 

+ n이 10만 이상일 경우, 가장 공간을 적게 쓰는 순서는?

1. O(n) = 2^n
2. O(n) = n^(3/2)
3. O(n) = n Log n
4. O(n) = n^(Log n)
5. O(n) = n!

=> 3, 2, 4, 1, 5

2. 공간 자원의 한계

2 - 1. 컴퓨터의 공간 자원

복잡도 계산을 실제 메모리 공간의 제한에 적용하기

- 프로그램은 주 기억장치에서 실행된다

- 프로그램은 실행되기 위해 고정 공간과 가변 공간이 필요하다 ~ S(P) = c + Sp(n)

2 - 2. 주 메모리의 공간 자원

+ 엮어보기 : https://cdaosldk.tistory.com/288

CS 강의 3. 프로세스 생명주기와 프로세스 메모리

1) 프로세스의 주소 공간

프로그램은 어떤 작업을 위해 실행할 수 있는 파일 ~ 프로세스가 프로그램을 실행한다

- 컴퓨터에서 연속적으로 실행하고 있는 컴퓨터 프로그램

- 메모리에 올라와 실행되고 있는 프로그램의 인스턴스

- 운영체제로부터 시스템 자원을 할당받는 자원 단위

 

특징

- 독립된 영역(코드, 스택, 데이터, 힙)을 할당받는다

코드 : 프로그래머가 작성한 프로그램이 저장되는 영역

데이터 : 코드 실행 시 환경이나 파일 등의 데이터가 모여있다

스택 : 호출한 함수가 종료되면 되돌아올 메모리의 주소나 지역변수 등이 저장된다

~ 메서드 내 지역변수가 메서드 실행 단위로 저장되고 해제된다

힙 영역 : 동적으로 할당되는 데이터를 위해 존재

~ 메서드에 전달되는 참조형 변수가 저장되고 해제된다

 

- 최소 1개 이상의 쓰레드(메인 쓰레드)를 가지고 있다

- 각 프로세스는 별도의 주소 공간에서 실행되며 기본적으로 다른 프로세스 자원에 접근할 수 없다

- 한 프로세스가 다른 프로세스의 자원에 접근하려면 프로세스 간 통신을 사용해야 한다

- CPU는 한 번에 하나의 프로세스만 실행 가능하다

 

+ Heap vs Stack

1) Heap : Heap은 객체를 저장하는 영역으로, 객체는 참조형 변수에 저장되는 값으로 배열, 클래스 인스턴스, 문자열 등이 있다. 메모리 공간이 동적으로 할당되고 해제되며 메모리의 낮은 주소에서부터 높은 주소로 할당이 이루어진다

 

2) Stack : 지역변수, 매개변수, 리턴 값 등을 저장하는 영역으로, 지역변수는 메서드가 실행되는 동안만 존재하기 때문에 Stack 영역에 저장된다. 메모리 공간이 선형적으로 할당되고 해제되며 메모리의 높은 주소에서 낮은 주소로 할당이 이루어진다

 

2) 쓰레드의 주소 공간

- 프로세스 내 실행되는 여러 흐름의 단위

- 프로세스 특정 수행 경로

- 프로세스가 할당받은 자원을 이용하는 최소 실행 단위

 

특징

프로세스 내 필요한 스택만 할당받으며, 이외 코드, 데이터, 힙 영역은 공유한다

~ 쓰레드는 힙의 참조형 변수를 수정할 수 있다

- 프로세스 하나만 사용해 프로그램을 실행하기엔 메모리 낭비가 발생힌디(작업을 수행하기 위해 매번 모든 프로세스가 메모리 영역을 할당받아야 하므로)

~ 쓰레드는 프로세스와 다르게 스레드 간 메모리를 공유한다

~ 프로세스가 할당받은 자원을 이용하는 처리 작업 단위

 

3) 일반적인 주 메모리 공간 자원

- 일반적으로 512MB 내외

최소한의 컴퓨팅 환경에서 프로그램에 할당하는 메모리 용량이다. 특히 AWS EC2에서 확인할 수 있고, 연산할 때 이 메모리를 모두 사용할 수 있는 것이 아니기 때문에 고정 공간보다 여유 있게 용량을 설정해야 한다

2 - 3. 숫자 자료형의 한계 : 자료형 크기로 인한 표현 범위의 한계

1. 부호 없는 정수 : 자바 또는 파이썬은 부호 없는 정수를 직접 지원하지 않는다. int가 아니라 long을 활용(파이썬은 int)해 부호를 표현하거나 비트 연산자를 사용할 수 있다. 보통 8바트로 표현한다

long a = 12L;
long b = 7L;
long result = a & b;
System.out.println("Result: " + result);

+ 비트 연산자 : https://tcpschool.com/c/c_operator_bitwise

코딩교육 티씨피스쿨

2. 부호 있는 정수 : 자바는 byte, short, int, long으로, 파이썬은 int로 표현한다. 보통 4바이트 또는 8바이트로 표현한다

int a = 10;
int b = -5;
int sum = a + b;
System.out.println("Sum: " + sum);

3. 실수 : 자바는 float, double로 표현한다. 보통 4바이트 또는 8바이트로 표현한다

 

* 자료형의 한계가 중요한 이유

자료형의 표현 범위를 초과하게 되면 양수가 음수로 바뀌거나 음수가 양수로 바뀐다(에이펙스 랭킹 1위 케이스)

=> Overflow가 발생했다

 

특히, 실수를 비교할 때

int main(void) {
  double a = 0.1 + 0.1 + 0.1;
  double b = 0.3;
  if (a == b) {
    System.out.println("same 1");
  }
  if (Math.abs(a - b) < 1e-12) {
    System.out.println("same 2");
  }
}
/**** result ****
same 2
*****************/

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";  // 1e-12 == 10^-12 / 1e9 == 10^9
}
       
/**** result ****
same 2
*****************/

2 - 4. 배열 자료형의 한계 : 변수 크기와 배열 크기에 따른 저장 범위

1) 배열의 저장 공간 할당

- 1차원 배열은 연속적 공간에 할당되며 최초 주소값을 기준으로 0부터 1씩 주소값이 더해진다

~ 크기가 3인 배열을 만들 때

~ 공간 복잡도는 O(3)

~ 메모리 사용량은 4바이트 * 3 = 12바이트

 

- 2차원 배열은 두 개의 인덱스를 가지지만 저장 공간은 연속된 공간에 할당된다

~ 1차원 크기는 2, 2차원 크기는 3인 배열을 만들 때

~ 공간 복잡도는 O(2*3)

~ 메모리 사용량은 4바이트 * 2 * 3 = 24바이트

 

2) 배열의 저장 한계

- int 메모리 계산 : 바이트, 킬로바이트, 메가바이트, 기가바이트 ~ 각각 천의 자리에서 단위 변경

~ 일반적으로 int가 4바이트이므로, 

* 보통 100만개 이상 크기의 배열을 선언하는 경우는 거의 없으므로, 이런 경우 알고리즘 설계를 다시 고려해보자

=> int 2억 개 이상일 경우 메모리 초과 ~ 여유 공간이 있는 1GB의 경우에도 초과 가능

 

int의 연산이 가장 빠르므로 int를 많이 사용하지만, long이나 double을 사용해 더 넓은 범위를 활용할 수도 있다. 다만 이 경우 시간 초과를 고려해야 한다

+ 일반 프로그래밍 시 ID 같은 필드의 경우는 long을 많이 활용함(확장성 고려)

 

** 메모리 초과도 정답으로 인정되지 않으므로 시간 복잡도 뿐만 아니라 공간 복잡도도 고려해야 한다