본문내용
1. 컴퓨터에서의 정수와 실수 표현
1.1. 정수의 표현 방식
1.1.1. 부호 없는 정수
컴퓨터에서는 정수를 2진수로 표현한다. 부호 없는 정수는 0과 1로만 표현되며, 모든 비트가 양의 수를 나타낸다. 부호 없는 정수의 표현 범위는 0부터 2^N-1까지이다. 예를 들어, 8비트를 사용할 경우 0부터 11111111(2진수), 즉 255(10진수)까지 표현할 수 있다. 비트의 개수가 N일 때, 부호 없는 정수는 0부터 2^N-1 사이의 숫자를 표현할 수 있다. 이는 컴퓨터가 정수를 2진수로 표현하기 때문이다. 부호 없는 정수는 음수를 표현할 수 없지만, 양의 정수만을 표현할 수 있기 때문에 더 큰 숫자 범위를 나타낼 수 있다는 장점이 있다.
1.1.2. 부호가 있는 정수
부호가 있는 정수는 음수와 양수를 모두 표현할 수 있는 정수이다. 부호가 있는 정수는 다음과 같은 세 가지 방식으로 표현할 수 있다.
첫 번째는 부호화 크기 방식이다. 부호 비트를 사용하여 양수와 음수를 구분한다. 최상위 비트가 0이면 양수, 1이면 음수를 나타낸다. 양수는 부호 비트를 제외한 나머지 비트로 값을 표현하고, 음수는 2의 보수 형태로 표현한다. 예를 들어, 4비트 정수에서 +5는 0101, -5는 1011로 표현된다.
두 번째는 1의 보수 방식이다. 1의 보수는 각 비트를 반대로 하여 표현한다. 즉, 0을 1로, 1을 0으로 바꾸면 된다. 예를 들어, 4비트 정수에서 +5는 0101, -5는 1010으로 표현된다.
세 번째는 2의 보수 방식이다. 2의 보수는 1의 보수에 1을 더한 값으로 표현한다. 예를 들어, 4비트 정수에서 +5는 0101, -5는 1011로 표현된다.
2의 보수 방식은 0이 두 개 존재하는 문제가 해결된다는 장점이 있어 대부분의 컴퓨터에서 부호 있는 정수를 표현할 때 사용된다. 이 방식을 사용하면 덧셈 연산 시 부호 처리를 따로 하지 않아도 되는 장점이 있다.
1.1.3. 1의 보수와 2의 보수
부호가 있는 정수를 표현하기 위해서는 일반적으로 1의 보수나 2의 보수 방식을 사용한다. 이는 음수를 표현하기 위해 고안된 방법이다.
1의 보수는 양수를 그대로 표현하고, 음수는 양수의 각 비트를 반대로 하여 표현한다. 예를 들어 10진수 5의 2진수 표현은 0101이고, 이 수의 1의 보수는 1010이 된다. 이러한 1의 보수 방식은 0이 두 개(+ 0, -0) 생기는 단점이 있다.
이를 해결하기 위해 고안된 것이 2의 보수 방식이다. 2의 보수는 1의 보수에 1을 더한 값으로 표현한다. 예를 들어 10진수 5의 2진수 표현 0101의 2의 보수는 1011이 된다. 2의 보수 방식에서는 0이 하나만 존재하기 때문에 1의 보수 방식의 단점이 해결된다.
2의 보수 방식은 뺄셈 연산을 덧셈 연산으로 처리할 수 있게 해준다. 예를 들어 5 - 7을 계산하려면 5에 -7의 2의 보수인 1001을 더하면 된다. 이처럼 2의 보수 방식은 부호 있는 정수의 표현과 효율적인 산술 연산을 가능하게 하는 장점이 있다.
1.2. 실수의 표현 방식
1.2.1. 고정 소수점 방식
고정 소수점 방식은 실수를 표현하는 방법 중 하나로, 소수부의 자릿수를 사전에 정해놓고 고정된 자릿수만큼의 소수를 표현하는 방식이다.
컴퓨터에서는 주로 4바이트(32비트) 실수를 기준으로 표현하는데, 이 경우 부호 1비트, 정수부 16비트, 소수부 16비트로 구성된다. 따라서 정수부와 소수부의 자릿수가 고정되어 있어, 정수부는 -32,768 ~ 32,767의 범위를, 소수부는 0.0000 ~ 0.9999의 범위를 표현할 수 있다.
고정 소수점 방식은 실수를 표현할 수 있는 범위가 제한적이라는 단점이 있다. 정수부의 비트 수가 늘어나면 더 큰 정수를 표현할 수 있지만, 그에 따라 소수부의 표현 범위가 줄어들게 된다. 따라서 큰 범위의 실수를 표현하기 위해서는 소수점 이하 정밀도가 낮아지게 된다.
이러한 한계 때문에 컴퓨터에서는 고정 소수점 방식보다는 부동 소수점 방식을 주로 사용한다. 부동 소수점 방식은 실수를 표현할 때 정수부와 소수부를 구분하지 않고 지수부와 가수부로 구분하여 표현함으로써, 더 넓은 범위의 실수를 표현할 수 있다는 장점이 있다.
1.2.2. 부동 소수점 방식
부동 소수점 방식은 정수부와 소수부로 나누어 표현하는 것이 아니라, 부호, 가수, 지수로 나누어 표현하는 방식이다. 부동 소수점 방식은 고정 소수점 방식보다 더 넓은 범위의 실수를 표현할 수 있다는 장점이 있다.
부동 소수점 방식은 부호 비트, 지수 부분, 가수 부분으로 구성된다. 부호 비트는 실수가 양수인지 음수인지를 나타내며, 지수 부분은 2의 지수를 표현한다. 가수 부분은 소수점 이하 부분을 표현한다.
부동 소수점 방식에는 단정도(single precision)와 배정도(double precision) 방식이 있다. 단정도 방식은 부호 1비트, 지수 8비트, 가수 23비트로 구성되며, 배정도 방식은 부호 1비트, 지수 11비트, 가수 52비트로 구성된다.
지수 부분의 구성에 있어서 bias라는 개념이 도입된다. 지수 부분에 bias를 더하여 지수를 표현함으로써, 지수 부분의 표현 범위를 늘릴 수 있다. 예를 들어 지수 부분이 8비트인 경우, bias는 127이 된다. 따라서 실제 지수 값이 -127부터 128까지 표현될 수 있다.
부동 소수점 방식은 고정 소수점 방식에 비해 보다 넓은 범위의 실수를 표현할 수 있다는 장점이 있지만, 항상 오차가 존재한다는 단점이 있다. 즉, 컴퓨터에서 실수를 정확하게 표현할 수 없다는 것이다. 따라서 부동 소수점 연산 시 정밀도에 대한 주의가 필요하다.
2. 이진 트리의 특성
2.1. 이진 트리의 정의 및 구조
이진 트리는 트리 중에서 모든 노드의 차수가 최대 2개를 넘지 않는 트리이다. 즉 노드의 차수가 하나 또는 두 개이고, 따라서 루트를 기준으로 최대 두 개의 서브트리를 가지고 왼쪽 서브트리와 오른쪽 서브트리로 구분된다.
서브트리가 최대 두 개를 가질 수 있으니 서브트리가 한 개인 이진트리도 가능한데 이렇게 차수가 모두 1인 한쪽으로만 치우친 이진 트리와 차수가 모두 2인 이진트리를 구성할 수 있는 이진트리의 특성으로 이진트리의 최대 높이와 최소 높이를 계산할 수 있다.
노드의 개수가 N인 경우 최대 높이는 노드의 개수와 같은 N이 되고 최소 높이는 [log₂N]+1이 된다. 이진트리는 주요 연산은 삽입, 삭제, 순회인데 그 중에서 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 순회 연산이 가장 대표적이다.
2.2. 이진 트리의 순회 방법
이진 트리의 순회 방법은 루트 노드(D), 왼쪽 서브트리(L), 오른쪽 서브트리(R)를 어떤 순서로 방문하느냐에 따라 전위(preorder), 중위(inorder), 후위(postorder) 순회로 구분된다.
전위 순회는 루트 노드(D)를 먼저 방문한 뒤 왼쪽 서브트리(L), 오른쪽 서브트리(R)를 차례대로 방문하는 방식이다. 즉, D-L-R의 순서로 순회한다. 이를 통해 얻은 결과는 루트 노드, 왼쪽 서브트리, 오른쪽 서브트리의 순서대로 나열된다.
중위 순회는 왼쪽 서브트리(L)를 먼저 방문한 뒤 루트 노드(D), 오른쪽 서브트리(R)를 차례대로 방문하는 방식이다. 즉, L-D-R의 순서로 순회한다. 이를 통해 얻은 결과는 왼쪽 서브트리, 루트 노드, 오른쪽 서브트리의 순서대로 나열된다.
후위 순회는 왼쪽 서브트리(L), 오른쪽 서브트리(R)를 먼저 방문한 뒤 루트 노드(D)를 마지막으로 방문하는 방식이다. 즉, L-R-D의 순서로 순회한다. 이를 통해 얻은 결과는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드의 순서대로 나열된다.
이진 트리의 순회 방법은 트리 내 노드를 어떤 순서로 방문하느냐에 따라 달라지며, 이를 통해 트리 내 정보를 선형적인 순서로 얻을 수 있다. 따라서 전위, 중위, 후위 순회는 이진 트리에서 중요한 기본 연산이라고 할 수 있다."
2.3. 포화 이진 트리와 완전 이진 트리
포화 이진 트리와 완전 이진 트리는 이진 트리의 특수한 형태이다. 포화 이진 트리는 모든 노드가 두 개의 자식 노드를 가지는 이진 트리이다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨의 노드가 꽉 차 있고, 마지막 레벨의 노드들은 왼쪽부터 차례대로 배치되어 있는 이진 트리이다.
포화 이진 트리는 깊이가 h일 때 노드의 개수가 최대 2^h - 1개이다. 예를 들어 깊이가 3인 포화 이진 트리는 2^3 - 1 = 7개의 노드를 가진다. 이처럼 포화 이진 트리는 노드가 꽉 차 있어 트리의 구조가 안정적이고 정돈된 형태를 가진다.
반면, 완전 이진 트리는 마지막 레벨에서 일부 노드가 비어있을 수 있다. 다만 비어 있는 노드들은 항상 오른쪽에 위치한다. 따라서 완전 ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16