스파르타 코딩클럽(부트캠프) 11장 공간자원과 공간 복잡도

공간자원

컴퓨터 구조

레지스터 = CPU
캐시메모리(SRAM), 메인 메모리(DRAM) = 주 기억장치
하드디스크(HDD) = 보조 기억장치

출처 : 스파르타 코딩클럽

---

캐시메모리(L2, L3)

캐시메모리는 컴퓨터 시스템 향상을 위해서 CPU와 주 기억장치 사이에 있는 아주 작은 비싼메모리
컴퓨터 전원이 꺼지면 지워지지만 제일 빠르게 조회할 수 있는 저장공간

CPU 구성에 있는 캐시메모리 = L1
메모리 그룹에 속한 캐시메모리 = L2, L3

L2, L3 캐시메모리

• 메인 메모리에 있는 데이터를 캐시메모리에 불러와 놓은 후 CPU가 필요한 데이터를 캐시에서 먼저 찾도록 하여 시스템 성능을 향상시켜준다.(레지스터와 비슷하지만 다르다)
• CPU와 별도의 공간이며 메인 메모리와 CPU간 속도차이를 극복하기 위한 것이다.

CPU레지스터

• CPU안에서 연산을 처리하기 위하여 데이터를 저장하는 공간이다.

---

주 기억장치

컴퓨터가 전원이 꺼지면 지워지지만 조금 더 빠르게 조회 할 수 있는 공간이다
메인메모리 = 주 기억장치 = RAM(Random Access Memory)

• RAM은 DRAM과 SRAM이 있는데 주 기억장치는 주로 DRAM을 의미(SRAM은 캐시 or 레지스트리)
• 컴퓨터의 CPU가 현재 처리중인 데이터나 명령만을 일시적으로 저장하는 휘발성 메모리이다
• 보조기억장치(하드디스크)보다 접근속도가 빠르다.
• 모든 프로그램은 컴퓨터에서 실행되기 위해 메모리의 일부를 사용한다.
• HDD - RAM -CPU와 유사한 방식으로 연산과정의 중간에 위치한다.
• HDD에 비해서 월등히 빠른 속도로 CPU가 정보를 원활히 이용할 수 있게 한다.
• CPU가 사용하기 좋도록 각종 정보를 임시 저장하는 휘발성 장치이다.

전원이 꺼지면 메인 메모리에 저장된 내용들은 모두 사라지기에 컴퓨터가 꺼진 이후에도 데이터를 유지하고 싶을 경우 하드디스크에 저장 해야한다.

SRAM (Static RAM)

• 정적 메모리
• 전원 공급이 되는 동안 기록된 내용이 지워지지 않기 때문에 재충전이 필요없다.
• 접근 속도가 빠르고 가격이 비싸다는 특징이 있으며 주로 캐시메모리나 레지스터로 사용 된다.

DRAM(Dynamic RAM)

• 동적 메모리
• 전원이 계속 공급되더라도 주기적으로 재충전되어야 기억된 내용을 유지할 수 있다.
• 주로 대용량의 기억장치에 사용되고 가격이 저렴하다.
• 주 기억장치를 RAM으로 표한할 때 DRAM을 가리킨다.

---

보조 기억장치

컴퓨터 전원이 꺼져도 지워지지 않는 저장공간

• 사용자가 사용하고자 하는 데이터와 프로그램을 반영구적으로 저장한다.
• 전원을 끄더라도 저장된 데이터나 정보가 날아가지 않는 비휘발성 메모리이다.
• 설치하는 모든 프로그램이나 파일들은 보조기억장치에 반영구적 저장된다.

---

공간 복잡도

공간복잡도 란

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

총 필요 저장 공간

• 고정 공간(알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수
• 가변 공간(알고리즘 실행과 관련 있는 공간) : 실행 중 동적으로 필요한 공간
• S(P) = c + Sp(n)

• c : 고정 공간
• Sp(n) : 가변 공간

고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.

---

프로그램 복잡도

• 시간 복잡도 : 얼마나 빠르게 실행되는지
• 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지

알고리즘 = 좋은 프로그램은 실행 시간도 짧고, 저장 공간도 적게 쓰는 프로그램이다.

• 둘다 만족 시키기는 어렵다.
• 시간과 공간은 반비례적 경향이 있다.
• 최근 대용량 시스템이 보편화되면서 공간 복잡도 보다는 시간 복잡도가 우선이다.
• 허나 공간 복잡도는 기본이다.

---

공간 복잡도 예시

• 공간 복잡도와 시간 복잡도 모두 빅 오 표기법으로 표현한다.=O(n)

O(n) 공간 복잡도 예시

n! 팩토리얼 구하기

1. 재귀 함수를 통하여 구현하므로 변수 n에 따라 변수 n이 n개가 만들어지게 된다.
2. factorial 함수를 재귀 함수로 1까지 호출 하였을 경우에 n부터 1까지 스택에 쌓이게된다.
3. 따라서 공간 복잡도는 O(n)

public int factorial(int n) {

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

    return n*factorial(n-1);
}

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

1. 사용되는 변수는 a[], n, result, i 이다.
2. (a[]의 n개의 원소를 저장할 공간) + ( 변수 n, i, result를 위한 공간)이 필요하다.
3. 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;
}

---

O(n) 공간 복잡도 예시

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

1. 반복문을 통하여 구현하므로 result에 저장하기 때문에 공간 복잡도는 O(1)이다.
2. 사용하는 변수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;
}

---

공간 복잡도 적용

• 공간 복잡도는 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계를 의미한다.
• N짜리 2차원 배열은 O(N^2), 배열이 없다면 O(N)이라고 보면 된다.
• 보통 데이터 영역이 스택 영역보다 더 크기 때문에 큰 배열은 전역변수에 선언을 한다. 스택 영역에 큰 배열을 저장하는 경우 메모리 초과가 나는 경우가 있다.
• 메모리는 직접 계산해보면되고 512MB의 경우 1.2억개의 int가 들어간다.

보통 100MB 이상이 주어지면 메모리를 신경쓰지 않아도 된다. 2MB처럼 적게 주어진다면 최적화를 해주어야되고 50만 정도밖에 쓰지못하기 때문에 배열도 신경써주어야한다.

출처 : 스파르타 코딩클럽

위 그림에서 "제한 조건 확인" 시 공간 복잡도를 계산하여야 한다.

컴퓨터 과학자는 시,공간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위한 수학적 개념을 형식화한 표현이 빅 오 표기법이라 한다.

---

빅 오 표기법

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

• 빅 오 표기법을 사용하여 주어진 알고리즘의 효율성을 쉽게 분류 할 수 있다.
• 빅 오 표기법을 알면 일간되고 간결한 방법으로 어떤 알고리즘이든 분석할 수 있는 도구가 생긴 것이다.

데이터가 몇개든 항상 3단계가 걸리는 알고리즘을 가정할 때 O(3) == O(100) == O(1)

1. 원소가 N개이면 알고리즘에 항상 3단계가 필요하다.
2. 빅 오 는 O(1)이다.
3. 빅 오가 알고리즘에 필요한 단계 수를 알려주는 것 말고도 한 가지 더 역할을 한다는 것이다.
4. O(1)과 O(3) 두 알고리즘 모두 데이터 증가에 영향을 받지 않고 단계 수가 변하지 않는 유형이므로 본질적으로 같은 알고리즘 유형이다.
5. N이 얼마든 항상 상수 단계만 필요하다.

O(1) 알고리즘을 상수시간 constant time을 갖는 알고리즘이라고도 표현한다.

 

---

출처 : 스파르타 코딩클럽

O(N)은 완벽한 대각선을 그린다.

• 데이터가 하나씩 추가 될 때 알고리즘이 한 단계씩 더 걸리기 때문에 데이터가 많아질수록 알고리즘에 필요한 단계수도 늘어난다.

O(1)은 완벽한 수평선을 그린다.

• 데이터의 증가나 감소에 영향을 받지 않고 단계수가 일정하다.

변화가 생기는 일정량의 데이터가 있을것이며 O(N)은 그 순간 부터 무한대까지 더 많은 단계가 걸리기에 O(1) 알고리즘에 실제로 몇 단계가 걸리든 O(N)이 전반적으로 O(1)보다 덜 효율적이라 볼 수 있다.

 

복잡도는 최악의 시나리오를 의미 = 빅 오 표기법

• 선형 검색이 항상 O(N)은 아니다
• 검색값이 배열 맨 처음에 있는 최선의 시나리오에서는 O(1)이다.
• 검색값이 배열의 맨 끝에 잇는 최악의 시나리오에서는 O(N)이다.

최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 정확히 알게 된다면 최악을 대비함과 동시에 알고리즘 선택에 중요한 영향을 미칠 수 있기 때문이다.

---

로그 (log) 란

로가리즘(logarithm)의 줄임말

 

• 지수(Exponent)와 역(Inverse) 의 관계
• 2를 몇 번 곱하면 N이 나올 때 = log₂N
• 1이 될 때 까지 N을 2로 몇번 나눠야 할지= log₂N
• log₂8은 2³의 역converse 관계다.
• log₂64은 2⁶의 역이다.

2를 몇 번 곱해야 N이 나올지

• 2를 3번 곱해야 8이 나오므로 log₂8 = 3
• 2를 6번 곱해야 64가 나오므로 log₂64 = 6

1이 될 때까지 N을 2로 몇번 나눠야 할지

• 8 / 2/ 2 / 2 = 1
• 8이 1이 될 때까지 2를 3번 나눠야 하므로 log₂8 = 3
• 64 / 2/ 2/ 2/ 2/ 2/ 2 = 1
• 64가 1이 될 때 까지 2를 6번 나눠야 하므로 log₂64 = 6

---

O(logN) == O(log₂N)

컴퓨터 과학에서 O(logN)은 O(log₂N)을 줄여 부르는 말이다.

 

데이터 원소가 N개일 때 알고리즘은 log₂ 단계가 걸린다.
Ex) 원소가 8개면 log₂8 = 3 이 알고리즘은 3단계

 

이진 검색은 정확히 O(logN) 알고리즘 방식으로 동작한다.

이진 검색 -> 빅 오 표기법 관점

• 배열의 크기 3 -> 이진 검색 2단계
• 배열의 크기 7 -> 이진 검색 3단계
• 배열의 크기 15 -> 이진 검색 4단계
• 배열의 크기 100 -> 이진 검색 7단계
• 배열의 크기 10,000 -> 이진 검색 13단계
• 배열의 크기 1,000,000 -> 이진 검색 20단계

데이터가 커질수록 단계 수는 늘어나기에 이진 검색은 O(1)이라 할 수 없다.
검색하고 있는 배열의 원소 수보다 단계수가 훨씬 적으므로 O(N)이라 할 수도 없다.

이진 검색은 O(1)과 O(N)사이에 있다. 이것을 빅 오 O(logN)이라 한다.

• 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘이다.
• 데이터 원소가 N개 있을 경우 알고리즘에 log₂단계가 걸린다.

---

공간자원의 한계

컴퓨터의 공간자원

프로그램의 저장공간

• 프로그램이 저장되는 곳 = 보조 기억장치 = 저장된다 = 실행할 정보를 저장한다.
• 프로그램이 실행되는 곳 = 주 기억장치 = 실행된다 = 실행중인 정보를 저장한다.
• 프로그램이 동작하는 곳 = 레지스터 + 캐시 메모리 = 동작한다 = 실행순서에 따라 수행되는 명령어를 저장한다.

 

---

주 메모리의 공간자원

프로세스의 주소공간

프로그램(Program)은 어떤 작업을 위해 실행할 수 있는 파일을 의미
이 프로그램을 실행하는 것이 프로세스이다.

• 컴퓨터에서 연속적으로 실행하고 있는 컴퓨터 프로그램
• 메모리에 올라와 실행되고 있는 프로그램의 인스턴스(독립적인 개체)
• 운영체제로부터 시스템 자원을 할당받는 자원의 단위

출처: 스파르타 코딩클럽

각각 독립된 메모리 영역(Code, Data, Stack, Heap)을 할당 받는다.

• 코드영역(Code Area) : 프로그래머가 작성한 프로그램이 저장되는영역(전역변수가 코드로 저장된다)
• 데이터 영역(Data Area) : 코드가 실행되며 사용한 환경 or 파일들의 각종 데이터들이 모여있다.
• 스택 영역(Stack Area) : 호출한 함수가 종료되면 되돌아올 메모리의 주소나 지역변수 등이 저장된다.(메소드 내에서만 사용하는 지역변수가 메소드 실행단위로 저장되고 해제된다)
• 힙 영역(Heap Area) : 동적으로 할당되는 데이터를 위해 존재한다.(메소드 참조형으로 전달할 참조형 변수들이 저장되고 해제된다)

출처 : 스파르타 코딩클럽

• 최소 1개 이상의 스레드(메인 스레드)를 갖고 있다.
• 각 프로세스는 별도의 주소 공간에서 실행, 기본적으로 다른 프로세스 자원의 접근이 불가능하다.
• 한 프로세스가 다른 프로세스 자원에 접근하려면 프로세스 간 통신 IPC를 사용해야한다.Ex)파이프, 파일 ,소켓 등

그림에서 여러 프로세스가 동시에 실행, 관리되는 것처럼 보이나 CPU는 한 가지 명령만 처리가 가능하기에 빠르게 프로세스들을 번갈아가며 실행, 관리하는 것이다.

Heap 영역

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

Stack 영역

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

---

스레드의 주소공간

스레드의 사전적 정의

• 프로세스 내에서 실행되는 여러 흐름의 단위
• 프로세스의 특정한 수행 경로
• 프로세스가 할당받은 자원을 이용하는 최소 실행단위

출처 : 스파르타 코딩클럽

스레드의 특징

• 프로세스 내에서 각 필요한 Stack만 할당받아 Code, Data, Heap 영역은 공유하여 각 스레드끼리 공유한다.
• 같은 프로세스 내 스레드끼리 자원(Heap 등) 을 공유하며 실행된다.(공유자원 Heap영약 변수를 수정이 가능하다)
• 프로세스 하나만을 사용해서 프로그램을 실행하기에는 메모리 낭비가 발생한다

• 스레드는 프로세스와 다르게 스레드 간 메모리를 공유하며 작동한다.
• 프로세스가 할당받은 자원을 이용하는 처리 작업(실행의 흐름)의 단위이다.

출처 : 스파르타 코딩클럽

---

일반적인 주 메모리 공간자원 (512MB 내외하며 그 이상은 메모리가 초과한다)

 

최소한 컴퓨터 환경에서 프로그램에 할당해주는 메모리 용량이 512MB가 일반적이다.

• AWS 환경에서 EC2를 띄우면 0.5Gib 에 해당하는 경우
• 512MB를 할당받아도 연산에 모든 메모리를 사용할 수 있지 않아 1G까지는 프리로 제공해준다.
• 고정공간을 남겨두기 위해 여유공간을 넉넉히 잡아 계산해야한다

출처 : 스파르타 코딩클럽

---

숫자 자료형의 한계

부호 없는 정수(Unsigned Integer)

• Java 또는 Python에서는 부호 없는 정수를 직접적으로 지원하지 않는다.
• 부호 없는 정수값을 표현하고 싶은 경우 더 큰 데이터 유형 long(Python은 int)을 사용
• 비트연산자와 함께 부호 없는 비트 연산을 수행할 수 있다.
• 8Byte로 표현된다.

Ex) 비트연산자를 사용하여 두 개의 부호 없는 정수 값을 비트로 논리적 AND 연산 예시

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

1. a 와 b는 부호 없는 정수
2. 각각 부호 없는 64비트 정수값 할당
3. a&b는 비트 AND 연산 수행
4. 결과는 result 변수에 저장
5. 결과는 4

---

부호 있는 정수(Signed Intefer)

• Java 에서 byte, short, int, long (Python은 int) 데이터 유형으로 표현한다.
• 양수와 음수의 정수 값을 표현할 수 있다.
• 4Byte 나 8Byte로 표현된다.

Ex) 부호 있는 정수를 사용하여 두 개의 정수 값을 더한다.

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

1. a와 b는 부호 있는 정수
2. a는 10, b는 -5 할당
3. 두 값을 더한다.
4. 결과는 sum에 저장
5. 결과는 5

---

실수(Floating - point number)

• Java에서 float, double 데이터 유형으로 표현
• 소수점을 가지는 수를 표현한다.
• 4Byte 나 8Byte로 표현

Ex) 실수를 사용, 두개의 수를 나눈다.

double a = 10.5;
double b = 3.2;
double result = a / b;
System.out.println("Result: " + result);

1. a와 b는 실수
2. a는 10.5, b는 3.2 할당
3. 두 값을 나눈다.
4. 결과는 result에 저장
5. 결과는 3.28125

출처 : 스파르타 코딩클럽

---

자료형 한계의 중요성

• 자료형의 표현 범위를 초과할 시 양수가 음수로 바뀌거나 음수가 양수로 바뀔 수 있는데 이를 Overflow라 한다.
• 결과적으로 의도하지 않은 값으로 바뀌며 Overflow가 발생하면 오답이 나온다.
• int가 표현 불가능한 범위를 저장한 후 비교하려고하면 다른 값이 나온다.
• float가 표현 불가능한 범위를 연산 한 후 값을 지려고하면 다른값이 나온다.

---

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

 

아래와 같이 단순 등호 비교는 false가 나온다

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
*****************/

c언어도 안된다.

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
*****************/

---

배열 자료형의 한계

배열의 저장공간 할당

1차원 배열은 연속적 공간에 할당되며 주소값(i) 기준 0부터 주소가 1씩 더해진다.

크기가 3인 int 배열 예시

• 공간 복잡도는 O(3)이며 메모리 사용량은 4Byte * 3 = 12Byte

출처 : 스파르타 코딩클럽

---

2차원 배열은 2개의 index를 가지지만 저장공간은 연속된 공간에 저장된다.

1차원 크기는 2, 2차원 크기는 3인 int배열 예시

• 공간 복잡도는 O(2*3), 따라서 메모리 사용량은 4Byte * 2 * 3 = 24Byte이다.

출처&nbsp; 스파르타 코딩클럽

---

배열의 저장 한계

2차원 배열(arr)의 메모리 계산

• Byte, KB, MB, GB 순으로 3자리 씩 쉼표 단위로 끊어 계산

출처 : 스파르타 코딩클럽

arr 배열 할당 메모리 (10억 개 int)

• 100,000 * 10,000 * 4Byte(int) = 4,000,000,000 = 4(GB)000(MB)000(KB)000(Byte) = 4GB

일반 int 형 자료길이 4Byte로 가정한다면

출처 : 스파르타 코딩클럽

100만개 이상의 배열을 선언하는 경우가 드물기에 1000만개(10^7)이상의 배열을 선언한다면 알고리즘 설계점검이 필요하다.

 

int형이 2억 개 이상이면 거의 100%메모리가 초과한다.(512MB, 1G 둘다 초과가능하다)

 

• int 형의 연산 속도가 가장 빠르기에 int를 사용한다.
• 더 넓은 범위의 변수가 필요하여  long, double 같은 자료형을 사용한다면 시간초과가 발생할 수 있다.
• 알고리즘이 아닌 보통 프로그래밍을 하면 ID값 같은 필드는 확장성을 위해서 long을 사용한다.

시간 초과뿐만 아닌 메모리 초과도 정답으로 간주하지 않아서 문제 풀이법을 고민하거나 배열을 선언한다면 시,공간 복잡도를 함께 고려해야한다.