3.5 요약¶
1. 핵심 정리¶
- 자료 구조는 논리적 구조와 물리적 구조라는 두 관점에서 분류할 수 있다. 논리적 구조는 데이터 원소 사이의 논리적 관계를 설명하고, 물리적 구조는 컴퓨터 메모리에 데이터를 저장하는 방식을 설명한다.
- 대표적인 논리적 구조에는 선형, 트리형, 네트워크형 등이 있다. 보통 논리적 구조에 따라 자료 구조를 선형(배열, 연결 리스트, 스택, 큐)과 비선형(트리, 그래프, 힙)으로 나눈다. 해시 테이블 구현에는 선형과 비선형 자료 구조가 함께 포함될 수 있다.
- 프로그램이 실행되면 데이터는 컴퓨터 메모리에 저장된다. 각 메모리 공간에는 대응하는 메모리 주소가 있으며, 프로그램은 이 주소로 데이터에 접근한다.
- 물리적 구조는 주로 연속 공간 저장(배열)과 분산 공간 저장(연결 리스트)으로 나뉜다. 모든 자료 구조는 배열, 연결 리스트 또는 둘의 조합으로 구현된다.
- 컴퓨터의 기본 자료형에는 정수형
byte,short,int,long, 부동 소수점형float,double, 문자형char, 불리언형bool이 있다. 값 범위는 차지하는 공간의 크기와 표현 방식에 따라 결정된다. - 부호와 크기, 1의 보수, 2의 보수는 컴퓨터에서 수를 인코딩하는 세 가지 방식으로, 서로 변환할 수 있다. 정수의 부호와 크기 표현에서 최상위 비트는 부호 비트이고, 나머지 비트는 수의 크기를 나타낸다.
- 정수는 컴퓨터에 2의 보수 형태로 저장된다. 이 표현에서는 양수와 음수의 덧셈을 똑같이 처리할 수 있어 뺄셈만을 위한 별도 하드웨어 회로가 필요 없으며, 양의 0과 음의 0의 모호함도 없다.
- 부동 소수점 인코딩은 부호 1비트, 지수 8비트, 가수의 소수부 23비트로 이루어진다. 지수 비트 덕분에 정수보다 훨씬 넓은 값 범위를 갖는 대신 정밀도를 희생한다.
- ASCII 코드는 가장 초기에 등장한 영어 문자 집합으로, 길이가 1바이트이며 128개의 문자를 수록한다. GBK는 널리 쓰이는 중국어 문자 집합으로 2만 자 이상의 한자를 수록한다. Unicode는 전 세계 여러 언어의 문자를 담은 완전한 문자 집합 표준을 제공하여 인코딩 방식의 차이로 발생하는 글자 깨짐을 해결하고자 한다.
- UTF-8은 가장 널리 쓰이는 Unicode 인코딩 방식으로 범용성이 매우 좋다. 확장성이 뛰어난 가변 길이 인코딩이며 저장 공간을 효율적으로 활용한다. UTF-16과 UTF-32는 고정 길이 인코딩 방식이다. 중국어를 인코딩할 때 UTF-16은 UTF-8보다 공간을 적게 차지한다. Java, C# 등의 언어는 기본적으로 UTF-16을 사용한다.
2. Q & A¶
Q: 해시 테이블에는 왜 선형 자료 구조와 비선형 자료 구조가 함께 포함되는가?
해시 테이블의 기반은 배열이며, 해시 충돌을 해결하기 위해 ‘체이닝’을 사용할 수 있다(뒤의 ‘해시 충돌’ 절에서 다룬다). 배열의 각 버킷은 연결 리스트를 가리키며, 연결 리스트 길이가 일정 기준을 넘으면 트리(보통 레드-블랙 트리)로 바뀔 수 있다.
저장 관점에서 해시 테이블의 기반은 배열이고, 각 버킷의 슬롯에는 값 하나, 연결 리스트 또는 트리가 들어갈 수 있다. 따라서 해시 테이블에는 선형 자료 구조(배열, 연결 리스트)와 비선형 자료 구조(트리)가 함께 포함될 수 있다.
Q: char 자료형의 길이는 1바이트인가?
char의 길이는 프로그래밍 언어가 사용하는 인코딩 방식에 따라 정해진다. 예를 들어 Java, JavaScript, TypeScript, C#은 모두 UTF-16 인코딩으로 Unicode 코드 포인트를 저장하므로 char의 길이는 2바이트다.
Q: 배열로 구현한 자료 구조를 ‘정적 자료 구조’라고 부르면 모호하지 않은가? 스택에서도 원소를 꺼내거나 넣을 수 있는데, 이런 연산은 모두 ‘동적’이다.
스택은 동적으로 데이터를 조작할 수 있지만 자료 구조는 여전히 ‘정적’이다. 즉, 길이를 바꿀 수 없다. 배열 기반 자료 구조는 원소를 동적으로 추가하거나 삭제할 수 있지만 용량은 고정되어 있다. 데이터 양이 미리 할당한 크기를 넘으면 더 큰 배열을 새로 만들고 기존 내용을 복사해야 한다.
Q: 스택이나 큐를 만들 때 크기를 지정하지 않았는데, 왜 ‘정적 자료 구조’인가?
고급 프로그래밍 언어에서는 스택이나 큐의 초기 용량을 직접 지정하지 않아도 클래스 내부에서 자동으로 처리한다. 예를 들어 Java ArrayList의 초기 용량은 보통 10이다. 용량 확장도 자동으로 이루어진다. 자세한 내용은 뒤의 ‘리스트’ 절에서 설명한다.
Q: 부호와 크기 표현을 2의 보수로 바꾸려면 ‘반전한 뒤 1을 더한다’. 그렇다면 반대 변환은 역연산인 ‘1을 뺀 뒤 반전하기’여야 할 텐데, ‘반전한 뒤 1을 더하기’로도 가능한 이유는 무엇인가?
두 표현의 상호 변환은 실제로 ‘보수’를 구하는 과정이기 때문이다. 먼저 보수를 정의하자. \(a + b = c\)라면 \(a\)를 \(c\)에 대한 \(b\)의 보수라 하고, 반대로 \(b\)도 \(c\)에 대한 \(a\)의 보수라고 한다.
\(n = 4\)비트 이진수 \(0010\)이 주어졌다고 하자. 이를 부호와 크기 표현으로 보면(부호 비트는 고려하지 않는다), 2의 보수는 ‘반전한 뒤 1을 더해’ 얻는다.
원래 표현과 2의 보수의 합은 \(0010 + 1110 = 10000\)이다. 즉, 2의 보수 \(1110\)은 \(10000\)에 대한 원래 수 \(0010\)의 ‘보수’다. 따라서 ‘반전한 뒤 1을 더하기’는 실제로 \(10000\)에 대한 보수를 계산하는 과정이다.
그렇다면 \(10000\)에 대한 2의 보수 \(1110\)의 ‘보수’는 무엇일까? 똑같이 ‘반전한 뒤 1을 더해서’ 얻을 수 있다.
즉, 원래 표현과 2의 보수는 \(10000\)에 대해 서로의 ‘보수’다. 따라서 두 방향의 변환에 같은 연산인 ‘반전한 뒤 1을 더하기’를 사용할 수 있다.
물론 역연산인 ‘1을 뺀 뒤 반전하기’로도 2의 보수 \(1110\)에서 원래 표현을 구할 수 있다.
정리하면 ‘반전한 뒤 1을 더하기’와 ‘1을 뺀 뒤 반전하기’는 모두 \(10000\)에 대한 보수를 구하는 연산이므로 서로 동등하다.
본질적으로 ‘반전’은 \(1111\)에 대한 보수를 구하는 연산이다(항상 부호와 크기 표현 + 1의 보수 = 1111이 성립하기 때문이다). 여기에 1을 더해서 얻은 2의 보수는 \(10000\)에 대한 보수다.
위 설명은 \(n = 4\)를 예로 들었지만, 자릿수가 임의의 값인 이진수에도 일반화할 수 있다.