[JUNGLE] TIL_8. CSAPP 2.1, Queue, Stack

모깅·2025년 9월 12일
jungle

JUNGLE

목록 보기
9/56
post-thumbnail

2.1.2 데이터 크기 (Data Sizes)

1. 워드 크기와 가상 주소 공간

모든 컴퓨터는 포인터 데이터의 기본 크기를 나타내는 워드 크기(word size)를 가집니다. 워드 크기가 결정하는 가장 중요한 시스템 매개변수는 가상 주소 공간의 최대 크기입니다.

  • w-비트 워드 크기: 가상 주소는 0부터 2w−12^w−1까지의 범위를 가지며, 프로그램은 최대 2w 바이트의 메모리에 접근할 수 있습니다.
    • 32비트 워드 크기: 가상 주소 공간은 최대 4 기가바이트(GB)로 제한됩니다.
    • 64비트 워드 크기: 가상 주소 공간은 최대 16 엑사바이트(EB)로, 사실상 거의 무한에 가까운 크기입니다.

최근에는 과학 계산, 데이터베이스, 데스크톱, 스마트폰에 이르기까지 32비트에서 64비트 시스템으로의 전환이 널리 이루어졌습니다. 대부분의 64비트 컴퓨터는 하위 호환성을 위해 32비트용으로 컴파일된 프로그램도 실행할 수 있습니다. 프로그램이 32비트인지 64비트인지는 실행되는 기계가 아니라 어떻게 컴파일되었는지에 따라 결정됩니다.

2. C언어의 데이터 자료형 크기

컴퓨터와 컴파일러는 다양한 길이와 방식으로 데이터를 표현합니다. C언어는 정수와 실수를 위한 여러 자료형을 지원하며, 그 크기는 32비트 또는 64비트 프로그램으로 컴파일하는지에 따라 달라질 수 있습니다.

C언어 기본 자료형의 일반적인 크기 (바이트 단위)

C 선언32비트 프로그램64비트 프로그램설명
char11단일 바이트 또는 작은 정수를 표현
short22작은 정수
int44기본적인 정수 (64비트에서도 보통 4바이트)
long48큰 정수 (64비트 프로그램에서 크기가 변하는 대표적인 자료형)
char * (포인터)48포인터는 항상 해당 프로그램의 워드 크기를 따름
float44단정밀도 실수
double88배정밀도 실수

Sheets로 내보내기

3. 고정 크기 정수형과 이식성

컴파일 환경에 따라 자료형의 크기가 달라지는 문제를 피하기 위해, ISO C99 표준에서는 크기가 고정된 자료형을 도입했습니다.

  • int32_t: 부호 있는 32비트(4바이트) 정수
  • uint32_t: 부호 없는 32비트(4바이트) 정수
  • int64_t: 부호 있는 64비트(8바이트) 정수
  • uint64_t: 부호 없는 64비트(8바이트) 정수

이러한 고정 크기 자료형을 사용하는 것은 프로그램의 이식성(portability)을 높이는 가장 좋은 방법입니다. 프로그래머는 다른 컴퓨터나 컴파일러에서도 데이터가 항상 동일한 크기를 가질 것이라고 확신할 수 있습니다.

과거 32비트 시대에는 많은 프로그래머들이 포인터를 저장하기 위해 int 자료형을 사용하곤 했습니다. 이는 32비트 프로그램에서는 포인터와 int가 모두 4바이트로 크기가 같았기 때문에 문제없이 동작했습니다. 하지만 이런 코드를 64비트 환경으로 옮기면, 포인터는 8바이트인데 int는 여전히 4바이트이므로 심각한 버그가 발생하게 됩니다.

2.1.3 주소 지정과 바이트 순서 (Addressing and Byte Ordering)

여러 바이트로 구성된 데이터를 메모리에 저장할 때는 두 가지 규칙이 필요합니다.

  1. 그 데이터의 주소를 무엇으로 할 것인가?
  2. 여러 바이트를 어떤 순서로 나열할 것인가?

거의 모든 컴퓨터에서 여러 바이트로 이루어진 데이터는 연속된 메모리 공간에 저장되며, 그중 가장 작은 주소가 해당 데이터의 주소로 사용됩니다.

1. 빅 엔디언 (Big Endian) vs. 리틀 엔디언 (Little Endian)

데이터를 구성하는 바이트들을 메모리에 나열하는 방식에는 두 가지가 있습니다.

  • 빅 엔디언 (Big Endian): 가장 중요한(큰 자리) 바이트를 먼저(낮은 주소에) 저장하는 방식입니다. 우리가 숫자를 읽고 쓰는 방식과 동일하여 사람이 이해하기 편합니다.
  • 리틀 엔디언 (Little Endian): 가장 덜 중요한(작은 자리) 바이트를 먼저(낮은 주소에) 저장하는 방식입니다.

예를 들어, 4바이트 정수 0x01234567을 메모리 주소 0x100에 저장한다고 가정해 봅시다.

  • 가장 중요한 바이트: 01
  • 가장 덜 중요한 바이트: 67

빅 엔디언 방식 (주소 순으로 01 23 45 67)

주소0x1000x1010x1020x103
값01234567

리틀 엔디언 방식 (주소 순으로 67 45 23 01)

주소0x1000x1010x1020x103
값67452301

인텔 호환(x86, x86-64) 머신은 대부분 리틀 엔디언 방식을 사용하며, IBM이나 Oracle(Sun)의 머신들은 전통적으로 빅 엔디언 방식을 사용해왔습니다. 최근의 ARM 프로세서처럼 두 방식을 모두 지원하는 바이 엔디언(bi-endian) 칩도 있지만, 안드로이드나 iOS 같은 운영체제가 리틀 엔디언으로 작동하기 때문에 사실상 방식이 고정됩니다.

두 방식 사이에 기술적인 우위는 없으며, 일관되게 한 가지 방식을 사용하는 것이 중요합니다. 이 용어는 조너선 스위프트의 소설 '걸리버 여행기'에서 달걀을 큰 쪽으로 깨는 '빅 엔디언'과 작은 쪽으로 깨는 '리틀 엔디언' 파벌의 싸움에서 유래했습니다.

2. 바이트 순서가 중요해지는 경우

대부분의 경우 프로그래머는 자신의 컴퓨터가 어떤 바이트 순서를 사용하는지 신경 쓸 필요가 없습니다. 하지만 다음과 같은 특정 상황에서는 문제가 될 수 있습니다.

  1. 네트워크 통신: 서로 다른 바이트 순서를 사용하는 컴퓨터끼리 이진 데이터를 주고받을 때 문제가 발생합니다. 리틀 엔디언 기계가 보낸 데이터를 빅 엔디언 기계가 받으면 숫자를 완전히 잘못 해석하게 됩니다. 이를 막기 위해 네트워크 프로토콜에는 '네트워크 바이트 순서(Network Byte Order)'라는 표준(빅 엔디언)을 정해두고, 각 컴퓨터가 데이터를 보내기 전에 이 표준에 맞춰 변환하고 받을 때 자신의 방식에 맞게 다시 변환합니다.
  2. 기계어 프로그램 분석: 디스어셈블러로 기계어를 분석할 때, 리틀 엔디언 기계에서는 숫자 값이 뒤집혀 보이는 경우가 많습니다. 예를 들어, 기계어 코드에 43 0b 20 00이라고 쓰여있다면, 실제 숫자 값은 이를 뒤집은 0x00200b43일 수 있습니다.
  3. 타입 시스템 우회: C언어에서 캐스팅(casting)이나 공용체(union)를 사용해 데이터의 바이트를 직접 들여다보는 시스템 프로그래밍을 할 때 바이트 순서가 드러납니다.

2.1.4 문자열의 표현 (Representing Strings)

C언어에서 문자열은 널(null) 문자(\0, 값이 0)로 끝나는 문자(char) 배열로 표현됩니다. 각 문자는 보통 아스키(ASCII) 코드와 같은 표준 인코딩 규칙에 따라 표현됩니다.

예를 들어, "12345"라는 문자열의 바이트를 살펴보면 다음과 같은 16진수 값을 얻게 됩니다.
31 32 33 34 35 00

  • 31 32 33 34 35: 각각 아스키 코드에서 문자 '1', '2', '3', '4', '5'에 해당하는 값입니다. (숫자 x의 아스키 코드는 0x3x입니다.)
  • 00: 문자열의 끝을 알리는 널(null) 종료 문자 \0 입니다.

플랫폼 독립성 (Platform Independence)

이러한 표현 방식은 빅 엔디언/리틀 엔디언과 같은 바이트 순서나 워드 크기에 전혀 영향을 받지 않습니다. 문자열은 단순히 1바이트짜리 문자들의 연속일 뿐이기 때문입니다.

결과적으로, 정수나 실수 같은 이진 데이터(Binary Data)에 비해 텍스트 데이터(Text Data)가 훨씬 더 플랫폼 독립적이며 호환성이 높습니다.

2.1.5 코드의 표현 (Representing Code)

아래와 같은 간단한 C 함수가 있다고 가정해 봅시다.

int sum(int x, int y) {
    return x + y;
}

이 함수를 서로 다른 컴퓨터에서 컴파일하면, 아래와 같이 완전히 다른 바이트(기계어) 코드가 생성됩니다.

  • Linux 32: 55 89 e5 8b 45 0c 03 45 08 c9 c3
  • Windows: 55 89 e5 8b 45 0c 03 45 08 5d c3
  • Sun: 81 c3 e0 08 90 02 00 09
  • Linux 64: 55 48 89 e5 89 7d fc 89 75 f8 03 45 fc c9 c3

핵심 내용

  1. 기계어는 호환되지 않는다: 서로 다른 종류의 컴퓨터(CPU 아키텍처)는 서로 다르고 호환되지 않는 명령어와 인코딩 방식을 사용합니다. 위 예시에서 Sun 컴퓨터의 기계어는 다른 컴퓨터들과 완전히 다른 것을 볼 수 있습니다.
  2. 운영체제도 영향을 미친다: 심지어 동일한 프로세서(Intel CPU)를 사용하더라도, 윈도우와 리눅스처럼 서로 다른 운영체제는 코딩 규약이 달라 약간 다른 기계어 코드를 생성합니다. 따라서 이진 코드(Binary Code)는 컴퓨터 기종과 운영체제의 조합이 다르면 거의 호환되지 않습니다.
  3. 컴퓨터에게 프로그램이란?: 컴퓨터의 관점에서 프로그램은 그저 바이트(byte)의 연속일 뿐입니다. 기계는 원래의 소스 코드가 어땠는지에 대한 정보를 전혀 가지고 있지 않습니다.

이처럼 소스 코드가 기계어로 번역되고 나면, 그 결과물인 이진 코드는 특정 하드웨어와 운영체제에 매우 종속적이어서 다른 환경에서는 실행될 수 없습니다.

2.1.6 불 대수 입문 (Introduction to Boolean Algebra)

컴퓨터가 정보를 저장하고 다루는 핵심에 이진 값(0과 1)이 있기 때문에, 이 값들을 연구하는 풍부한 수학적 지식 체계가 발전해 왔습니다. 이는 1850년경 조지 불(George Boole)의 연구에서 시작되었으며, 그의 이름을 따 불 대수(Boolean Algebra)라고 불립니다.

불은 참(true)과 거짓(false)이라는 논리 값을 1과 0이라는 이진 값으로 표현함으로써, 논리적 추론의 기본 원리를 대수학으로 공식화할 수 있다는 것을 발견했습니다.

1. 기본 불 연산

가장 단순한 불 대수는 {0, 1} 두 원소에 대해 정의됩니다. C언어의 비트 연산자와 일치하는 기호를 사용하여 다음과 같은 연산들을 정의할 수 있습니다.

  • ~ (NOT): 논리 부정(¬)에 해당합니다. 0은 1로, 1은 0으로 바꿉니다.
  • & (AND): 논리곱(∧)에 해당합니다. 두 입력이 모두 1일 때만 결과가 1이 됩니다.
  • | (OR): 논리합(∨)에 해당합니다. 두 입력 중 하나라도 1이면 결과가 1이 됩니다.
  • ^ (XOR): 배타적 논리합(⊕)에 해당합니다. 두 입력이 서로 다를 때만 결과가 1이 됩니다.

정보 이론의 창시자인 클로드 섀넌(Claude Shannon)은 그의 1937년 석사 논문에서 불 대수와 디지털 논리 회로의 연관성을 처음으로 증명했습니다.

2. 비트 벡터로의 확장

이 네 가지 불 연산은 비트 벡터(bit vector), 즉 고정된 길이의 0과 1로 이루어진 문자열에도 확장하여 적용할 수 있습니다. 각 연산은 비트 벡터의 같은 위치에 있는 비트끼리 수행됩니다.

예를 들어, 4비트 벡터 a = [0110]와 b = [1100]가 있을 때, 연산 결과는 다음과 같습니다.

  0110      0110      0110
& 1100    | 1100    ^ 1100    ~ 1100
-------   -------   -------   -------
  0100      1110      1010      0011

3. 비트 벡터의 활용: 집합 표현

비트 벡터는 유한 집합(finite set)을 표현하는 데 유용하게 사용될 수 있습니다. {0, 1, ..., w-1}의 부분집합 A를 비트 벡터로 표현할 때, i번째 원소가 집합 A에 포함되면 i번째 비트를 1로, 아니면 0으로 설정합니다.

  • 예시:
    • 집합 A = {0, 3, 5, 6} → 비트 벡터 a = [01101001]
    • 집합 B = {0, 2, 4, 6} → 비트 벡터 b = [01010101]
  • 연산의 대응:
    • | (OR) 연산은 합집합(Union, ∪)에 해당합니다.
    • & (AND) 연산은 교집합(Intersection, ∩)에 해당합니다.
    • ~ (NOT) 연산은 여집합(Complement)에 해당합니다.

위 예시에서 a & b를 계산하면 [01000001]이 나오는데, 이는 집합 {0, 6}을 의미하며, 이는 A와 B의 교집합인 A ∩ B와 같습니다. 이러한 집합 표현은 프로그램 실행을 중단시키는 여러 신호(signal) 중 어떤 것을 활성화할지 결정하는 마스크(mask)를 지정하는 등 실제 프로그래밍에 널리 사용됩니다.

2.1.7 C언어의 비트 수준 연산 (Bit-Level Operations in C)

C언어의 유용한 특징 중 하나는 비트 단위(bitwise) 불 연산을 지원한다는 것입니다. C언어는 불 대수에서 사용된 기호와 동일한 기호, 즉 | (OR), & (AND), ~ (NOT), ^ (XOR) 를 사용합니다. 이 연산자들은 char, int, long 등 모든 '정수형' 데이터 타입에 적용될 수 있습니다.

비트 수준 연산의 결과를 확인하는 가장 좋은 방법은, 16진수 값을 2진수 비트 형태로 확장하여 비트 단위로 연산을 수행한 뒤, 다시 16진수로 변환하는 것입니다.

  • 예시 (char 타입 기준):
    • ~0x41 (NOT 연산)
      • ~[0100 0001] → [1011 1110] → 0xBE
    • 0x69 & 0x55 (AND 연산)
      • [0110 1001] & [0101 0101] → [0100 0001] → 0x41
    • 0x69 | 0x55 (OR 연산)
      • [0110 1001] | [0101 0101] → [0111 1101] → 0x7D

비트 연산의 활용: 마스킹(Masking)

비트 수준 연산의 일반적인 용도 중 하나는 마스킹(Masking) 연산입니다. 마스크는 특정 비트들만 선택하거나 변경하기 위해 사용하는 비트 패턴입니다.

  • 예시: 특정 바이트만 골라내기
    • 마스크 0xFF는 8개의 비트가 모두 1인 값(1111 1111)입니다.
    • 어떤 정수 x에 x & 0xFF 연산을 수행하면, x의 다른 모든 바이트는 0으로 바뀌고 가장 낮은 자리의 1바이트 값만 남게 됩니다.
    • x = 0x89ABCDEF 일 때, x & 0xFF의 결과는 0x000000EF 입니다.
  • 예시: 모든 비트가 1인 마스크 만들기
    • int가 32비트일 때 0xFFFFFFFF라고 직접 쓸 수도 있지만, 코드의 이식성을 높이려면 ~0을 사용하는 것이 더 좋습니다. ~0은 데이터 타입의 크기와 상관없이 항상 모든 비트가 1인 값(예: 1111....1111)을 생성합니다.

2.1.8 C언어의 논리 연산 (Logical Operations in C)

C언어는 논리 연산을 위한 연산자 || (OR), && (AND), ! (NOT) 을 제공합니다. 이 연산자들은 앞서 설명한 비트(bit) 연산자 (|, &, ~)와 비슷해 보이지만, 동작 방식은 완전히 다릅니다.

논리 연산자는 인자를 '참(True)' 또는 '거짓(False)'으로만 판단합니다.

  • 0이 아닌 모든 값은 '참(True)'으로 간주합니다.
  • 0은 '거짓(False)'으로 간주합니다.
  • 연산의 결과는 항상 1(참) 또는 0(거짓)으로만 나옵니다.

비트 연산과의 차이점

1. 값의 해석 방식

비트 연산은 숫자의 각 비트(0과 1) 하나하나에 대해 연산하지만, 논리 연산은 숫자 값 전체를 참 또는 거짓으로만 판단합니다.

  • 예시:
    • 논리 AND: 0x69 && 0x55 → 참 && 참 → 결과는 1 (0x01)
    • 비트 AND: 0x69 & 0x55 → 01101001 & 01010101 → 01000001 → 결과는 65 (0x41)

두 연산의 결과가 완전히 다른 것을 볼 수 있습니다.

2. 단락 평가 (Short-circuit Evaluation) ⭐

논리 연산자 &&와 ||의 가장 중요한 특징은 '단락 평가'를 한다는 것입니다. 이는 첫 번째 인자만으로 전체 결과가 결정되면, 두 번째 인자는 아예 평가(실행)하지 않는 동작 방식입니다.

  • && (AND) 연산:
    a && 5/a
    만약 a가 0이라면, 첫 번째 인자가 '거짓'이므로 전체 결과는 무조건 '거짓'입니다. 따라서 뒤따라오는 5/a는 아예 실행되지 않습니다. 덕분에 0으로 나누는 에러가 발생하지 않습니다.
  • || (OR) 연산:
    a || b
    만약 a가 '참'(0이 아님)이라면, 전체 결과는 무조건 '참'입니다. 따라서 b는 아예 실행되지 않습니다.
  • 포인터 예시:
    p && *p++
    만약 p가 NULL 포인터(값이 0)라면, 첫 번째 인자가 '거짓'이므로 뒤의 p++(NULL 포인터를 역참조하는 위험한 연산)는 실행되지 않아 프로그램이 안전하게 유지됩니다.

이러한 단락 평가 특성은 코드를 더 간결하고 안전하게 만들어주는 매우 유용한 기능입니다.

2.1.9 C언어의 시프트 연산 (Shift Operations in C)

C언어는 비트 패턴을 왼쪽이나 오른쪽으로 이동시키는 시프트(Shift) 연산을 제공합니다.

1. 왼쪽 시프트 (Left Shift): <<

x << k는 변수 x의 비트 패턴을 왼쪽으로 k칸 이동시키는 연산입니다.

  • 동작: 왼쪽으로 밀려나는 상위 k개의 비트는 버려집니다. 비어있는 오른쪽 끝 k개의 비트는 0으로 채워집니다.

2. 오른쪽 시프트 (Right Shift): >>

x >> k는 변수 x의 비트 패턴을 오른쪽으로 k칸 이동시키는 연산입니다. 오른쪽 시프트에는 두 가지 종류가 있습니다.

논리적 오른쪽 시프트 (Logical Right Shift)

  • 동작: 오른쪽으로 밀려나는 하위 k개의 비트는 버려집니다. 비어있는 왼쪽 끝 k개의 비트는 무조건 0으로 채워집니다.
  • 용도: 주로 부호 없는 정수(unsigned)나 논리적인 비트 마스크를 다룰 때 사용됩니다.

산술적 오른쪽 시프트 (Arithmetic Right Shift)

  • 동작: 오른쪽으로 밀려나는 하위 k개의 비트는 버려집니다. 비어있는 왼쪽 끝 k개의 비트는 원래 숫자의 최상위 비트(MSB, 부호 비트)와 같은 값으로 채워집니다.
  • 용도: 주로 부호 있는 정수(signed)를 다룰 때 사용됩니다. 이 방식은 숫자를 2로 나누는 효과를 부호를 유지한 채로 얻을 수 있게 해줍니다.
  • 예시 (8비트 기준):
연산0110001110010101
x << 4[00110000][01010000]
x >> 4 (논리)[00000110][00001001]
x >> 4 (산술)[00000110][11111001]

기울임꼴은 새로 채워진 비트를 의미합니다. 음수를 산술 시프트할 때 왼쪽이 1로 채워지는 것을 볼 수 있습니다.

C언어와 Java의 차이점

  • C언어: 부호 있는 숫자에 대한 오른쪽 시프트가 논리적일지 산술적일지 표준에 명확히 정의되어 있지 않습니다. 이는 코드의 이식성 문제를 일으킬 수 있습니다. 하지만 실제로는 거의 모든 컴파일러가 부호 있는 숫자에는 산술 시프트를, 부호 없는 숫자에는 논리 시프트를 사용합니다.
  • Java: 표준에 명확히 정의되어 있습니다.
    • >>: 산술 오른쪽 시프트
    • >>>: 논리 오른쪽 시프트

Stack

LIFO 구조를 갖는 자료구조이다.

배열로 구현

TOP을 항상 가르키는 변수를 하나 지정한다. (head라고 하자)

push

head가 가르키는 곳에 값을 넣고 head를 하나 증가시킨다.
시간 복잡도는 O(1)이 될 것이다.

pop

head-1의 값을 출력하고 head를 하나 감소시킨다.
시간 복잡도는 O(1)이 될 것이다.

peek

head-1의 값만 출력하면 된다.
시간 복잡도는 O(1)이 될 것이다.

count

원소의 개수를 출력하는 함수이며 head를 출력하면 된다.

Queue

FIFO 구조를 갖는 자료구조이다.

배열로 구현

맨 앞(head), 맨 뒤(rear)을 가르키는 변수를 지정한다.

push

rear에 데이터를 넣고 rear-1을 하자.
시간 복잡도는 O(1)이 될 것이다.

pop

head에 데이터를 빼자.
모든 원소를 앞으로 한 칸씩 이동시켜야 하기 때문에 O(N)의 시간복잡도가 걸린다.

링 버퍼로 구현

배열로 구현했을 때 pop의 문제점을 해결하기 위해서 나왔다. 모듈러 연산을 통해 head와 rear을 관리하자.

자세한 내용은 이전에 정리해놓았다! 여기서 확인해보자

profile
모깅
멈추지 않기
이전 포스트

[JUNGLE] TIL_7. 1주차 첫 시험, 새로운 조편성, 이분 탐색, 해시 테이블

다음 포스트

[JUNGLE] TIL_9. CSAPP 2.2, 우선순위 큐

0개의 댓글