[ps] 알고리즘 문제 풀 때, 메모리 제한? (feat. 구조체 메모리 계산)

코딩 테스트와 같이 알고리즘 문제 풀 때,

메모리 제한이 엄격한 경우가 있다.

 

이때는 문제 설계 단계에서 메모리가 얼마나 필요할지 계산해서 구현해야 한다.

Q) int는 4Byte 입니다. 그렇다면  int[] 배열 크기를 100만 (= 106) 으로 잡으면?

A) int arr[1'000'000];  → 4 × 1,000,000 = 4,000,000 = 4MB 이다.

    만약에 int 배열 크기가 1억(10^8)으로 잡는다면 → 400 MB 가 된다.

 

구조체 메모리 계산

하나의 자료형으로 이루어진 구조체 크기도 어렵지 않게 계산할 수 있다.

struct Node 
{
    int x, y, state;
} que[3000 * 3000];

→ (int) 4 byte × 3개 × 3000 × 3000 = 10^8 MB 정도 잡힘

 

Q) 여러 타입이 들어가는 구조체는 어떨까?

A) sizeof 연산자로 크기를 확인할 수 있다.

#include <stdio.h>

struct User 
{
      char name[10];  // 1 * 10 
      int age;        // 4
      char phone[10]; // 1 * 10
}user;

int main() 
{
       printf("크기: %d\n", sizeof(user));
}

Q) {char형 10byte} + {int형 4byte} + {char형 10 byte} = 24 byte ?

A) 28 byte! 구조체를 정렬할 때 멤버 중에서 가장 큰 자료형 크기의 배수로 정렬

    name과 phone이 10byte를 차지할 것 같지만 age(int)에 맞춰서 메모리가 할당되어

    각각 4 * 3 = 12byte로 맞춰집니다. 

    그렇기에 12 + 4 + 12 = 28byte

구조체를 정렬할 때 남는 공간을 "패딩 (padding)" 이라고 한다.

 

 

예시

struct Node 
{
    int x;
    short y;
}

short 타입은 2byte이지만 int 기준으로 잡혀서 

4byte × 2개 = 8 byte

 

 

예시

#include <stdio.h>

struct Node 
{
       char name[10];
       int cnt;
       int arr[20000];
} st[1000];

int main() 
{
       printf("크기: %d\n", sizeof(st));
}

① char name[10];: name[10]을 처리하기 위해서 4byte × 3 = 12byte

② int cnt;: 4byte

③ int arr[20000];: 4byte × 20000 = 80,000

(12 + 4 + 80,000) × 1000 = 12,000 + 4,000 + 80,000,000  = 80,016,000 byte

1MB = 1,000,000 (= 10^6) 이므로 약 80 MB 차지한다.

 

메모리 최적화

이러한 메모리 낭비를 변수 선언 순서를 다르게 해서 조절할 수 있다.

#include <stdio.h>

struct User 
{
       char name[10];
       char phone[10];
       int age;
}user;

int main() 
{
       printf("크기: %d\n", sizeof(user));
}

 

예시

#include <stdio.h>

struct Node
{
       char A[5], B[6], C[3];
       int D[11];
} node;

int main()
{
       printf("크기: %d\n", sizeof(node));
}

자료형이 큰 int 기준으로 {4 byte 배수}로 나머지 변수도 결정된다.

( ❌ ) 5 + 6 + 3 + (11 × 4) = 58

( ❌ ) 8 + 8 + 4 + (11 × 4) = 64

( ✔️ ) 16 + 44 = 60

        → A, B, C 는 char형(1 byte)로 5 + 6 + 3 ≤ 4 × 4 byte = 16 으로 잡힙니다.

 

이러한 데이터 타입 크기가 중요한 분야로 펌웨어 · 네트워크 프로그래밍을 예로 들 수 있다.

데이터간 패킷 통신에 있어서 정해진 규격이나 메모리 낭비는 좋지 못하기 때문이다.

 

▶ [BOJ] 13701 중복 제거

[BOJ] 백준 13701 중복 제거