# 11장 성능을 위한 알고리즘



🧠 주제: **계산을 피하라! – 표와 근사로 속도를 얻는 기술들**

> “정확히 계산하는 것보다, 아예 계산하지 않는 게 빠르다!”

### 1. **왜 계산을 피하려고 할까?**

컴퓨터는 빠르고 정밀하다고 생각하기 쉽지만, 현실은 그렇게 단순하지 않습니다.

* **정확성(Accuracy)**: 결과가 정답에 얼마나 가까운가?
* **정밀성(Precision)**: 같은 계산을 반복했을 때 결과들이 얼마나 일관적인가?

컴퓨터는 **정밀성은 강하지만 정확성은 상황에 따라 한계가 있습니다.** 특히 실수(float, double)는 근사값입니다.

> 예: `π = 3.1415926535...` 을 매번 계산할까요? 절대 아닙니다. 필요한 자리수까지만 기억하면 됩니다.

그래서 등장한 아이디어가 두 가지입니다:

#### 1) **지름길 (Shortcut)**

* 미리 계산된 값을 테이블로 만들어서 사용
* 대표 예시: 삼각함수, 로그, 온도 변환, 텍스처 매핑 등

#### 2) **근삿값 (Approximation)**

* 정밀도가 약간 떨어지더라도 계산량을 줄이기 위해 간단한 계산이나 추정 사용
* 대표 예시: 게임 렌더링, 필터링, 피라미드 이미지(MIP 맵)

### 📐 2. **표로 계산을 대신한다 – Lookup Table**

{% hint style="success" %}
직접 계산하는 것보다 표에서 무언가를 찾는 게 훨씬 더 빠른 경우가 종종 있습니다.&#x20;
{% endhint %}

표 찾기는 어떤 계산을 많이 하는 경우 **그 결과를 미리 계산해서 반복 사용하는 편이 합리적**이라는 측면에서 8장에서 설명한 `루프 불변값 최적화`와 비슷합니다.

#### 예시: **온도 센서 보정**

```plaintext
A/D 변환기 → 전압(v) → 로그함수 포함된 복잡한 계산식 → 온도(t)
```

> 이걸 매번 계산한다면?

너무 느리죠! 그래서 다음과 같이 처리합니다:

#### 👉 해결 방법

* 10비트 A/D 변환기 → 최대 1024 값
* 8비트 온도 테이블을 만들어, 각 A/D 값에 대응하는 온도를 미리 저장
* 필요할 때 `temp = lookup[vin]` 으로 끝!

```c
unsigned char lookup[1024];  // A/D값 → 온도
```

> 계산을 단 한 번도 하지 않고, 빠르게 온도값을 얻을 수 있습니다.

<figure><img src="https://498337729-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FqKPDlntOwGZBfzPFGkYi%2Fuploads%2FObx4WP7mVlYCcCJ88ITF%2Fimage.png?alt=media&#x26;token=1bb0b68b-160b-44f1-8549-422ee5387dda" alt=""><figcaption></figcaption></figure>

### 3. **3D 그래픽의 핵심 – 텍스처 매핑과 MIP Mapping**

{% hint style="warning" %}
#### 🎮 게임 속 벽돌을 보면?

* 가까이 있으면 선명하게
* 멀어지면 흐릿하게

이런 효과를 어떻게 줄까요?
{% endhint %}

#### 전통적 방법

1. 벽 텍스처에서 해당 좌표의 색을 가져오기
2. 멀리 있으면 평균을 내거나 다운스케일
3. 너무 느림!

#### ✅ 해결책: **MIP 맵(Multum in Parvo)**

<figure><img src="https://498337729-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FqKPDlntOwGZBfzPFGkYi%2Fuploads%2FeuxVR7IzG3hEnzevTI6e%2Fimage.png?alt=media&#x26;token=861a1501-0999-416f-b955-d4a741140599" alt=""><figcaption></figcaption></figure>

<figure><img src="https://498337729-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FqKPDlntOwGZBfzPFGkYi%2Fuploads%2FvmgouOjeJsW7KCJT9iet%2Fimage.png?alt=media&#x26;token=8b0802b8-0a5f-46dd-977e-b92ad2360280" alt=""><figcaption></figcaption></figure>

* **아이디어**: 텍스처의 여러 해상도 버전을 미리 계산해 저장
* 더 멀리 떨어진 물체에는 **저해상도 버전**을 사용
* 그림처럼 **피라미드 구조**로 저장

```plaintext
원본 64x64 → 32x32 → 16x16 → 8x8 ... → 1x1까지 저장
```

#### 🧠 이점

* 계산 없음 → 빠르다!
* 시점에 따라 적절한 해상도 선택
* 부드러운 전환 → 시각적으로도 깔끔

MIP 맵은 지금도 **게임 엔진 / 그래픽 카드 / 영상 합성기**에 기본 적용됩니다.

### 4. **문자 종류 판별 – if문보다 빠른 방법은?**

#### 전통적 접근

```c
int isdigit(int c) {
  return c >= '0' && c <= '9';
}
```

#### 문제점?

* 매번 조건 판단
* 코드가 반복됨

#### ✨ 해결책: **표를 만들자!**

<figure><img src="https://498337729-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FqKPDlntOwGZBfzPFGkYi%2Fuploads%2FKuDqeE3DYPTxleIULXcc%2Fimage.png?alt=media&#x26;token=66d06cca-e0b6-4596-943b-cc1fd429ffdd" alt=""><figcaption></figcaption></figure>

* 아스키 코드(0\~127)에 대해 속성을 비트로 저장

| 문자 | 비트 표현    |
| -- | -------- |
| A  | 00000010 |
| a  | 00000101 |
| 0  | 00001100 |

* 각 문자에 대해 아래처럼 비트를 부여

```c
#define UPPER      0x01
#define LOWER      0x02
#define DIGIT      0x04
#define HEXADECIMAL 0x08
```

#### 매크로로 한 줄 처리 가능

```c
#define isdigit(c) (table[(c)&0x7f] & DIGIT)
#define isalpha(c) (table[(c)&0x7f] & (UPPER | LOWER))
```

> **조건문 없이 비트 연산 한 번!**

이 방법은 무려 **20배나 빠르다**고 합니다. 벨 연구소에서 리치가 결국 채택했을 정도니까요.

### 🧠 5. 매크로 vs 함수

| 구분    | 매크로                          | 함수             |
| ----- | ---------------------------- | -------------- |
| 실행 속도 | 빠름 (치환)                      | 비교적 느림 (함수 호출) |
| 부작용   | 높음 (재평가 위험)                  | 낮음             |
| 사용 예  | isdigit(\*p++)와 같이 사용할 경우 위험 | 함수는 안전         |

**결론**: 매우 단순한 연산에는 매크로, 그렇지 않으면 함수!

### 🧠 정리: “계산하지 않을 수 있다면, 계산하지 마라!”

| 기술           | 설명                       | 사용 사례               |
| ------------ | ------------------------ | ------------------- |
| Lookup Table | 결과값을 미리 저장해 사용           | 온도 변환, 로그값, 삼각함수    |
| MIP Mapping  | 낮은 해상도 이미지를 계층으로 미리 저장   | 게임 텍스처, 거리 기반 렌더링   |
| 문자 판별 표      | ASCII 문자 속성 정보를 비트로 저장   | 언어 처리, 컴파일러, 문법 분석기 |
| 매크로 최적화      | 함수를 매크로로 치환하여 호출 오버헤드 제거 | 단순한 수식, 논리 조건 등     |

> **"계산은 컴퓨터가 빠르니까 시킨다?"**\
> 아니다. **계산을 안 할 수 있으면 안 하는 게 최고다!**

***

## 🎯 **정수만으로 그림을 그리자 – 계산 없이 속도로 승부하는 그래픽 알고리즘 이야기**

{% hint style="warning" %}
**“정수 + 덧셈만으로도 컴퓨터 그래픽을 완성할 수 있다고?”**\
지금부터 컴퓨터 역사상 가장 중요한 발명 중 하나인 ‘브레슨햄 알고리즘’을 시작으로,\
계산 없이 성능을 높이는 기술들을 살펴보겠습니다.
{% endhint %}

### 1. 왜 정수 계산인가?

컴퓨터 하드웨어는 연산의 종류에 따라 속도가 다릅니다.

| 연산 종류    | 속도    | 메모리/전력 사용량 |
| -------- | ----- | ---------- |
| 정수 덧셈/뺄셈 | 빠름    | 적음         |
| 정수 곱셈    | 중간    | 보통         |
| 부동소수점 연산 | 느림    | 많음         |
| 삼각함수, 로그 | 매우 느림 | 매우 많음      |

> 📌 결론: **가능하면 정수 덧셈/뺄셈만으로 표현하는 것이 가장 효율적이다.**

### 2. 캔버스에서 좌표계 변환 – 위아래가 바뀐 세상?

{% hint style="success" %}
캔버스는 웹에서 그래픽을 그릴 수 있는 HTML 요소입니다. 모눈종이처럼 생각하면 돼요
{% endhint %}

캔버스 모눈 종이는 기본적으로 표준적인 직교 좌표계를 사용하지 않기 때문에 우리가 그릴 때 쓰던 방식과 다릅니다. 이렇게 된 이유는 텔레비전에 래스터로 화면을 그리던 방향의 영향을 받았기 때문

기본적으로 사용되는 좌표계는 다음과 같습니다:

* (0, 0): **왼쪽 위**
* x축: → 오른쪽으로 증가
* y축: ↓ 아래로 증가 (**우리가 아는 좌표계와 반대**)

#### 🛠 좌표계 변환 코드

```js
canvas.translate(0, height);  // y축 기준 하단으로 평행이동
canvas.scale(1, -1);          // y축 방향 반전
```

### 3. 그리드와 직선 – 수학이 필요한 이유

격자선을 그리고 선을 그리는 기능을 자바스크립트로 구현해 보겠습니다.

#### 격자 그리기 코드

```js
var grid = 25;
canvas.scale(grid, grid);
canvas.setLineDash([0.1, 0.1]);  // 점선
```

### 4. 직선 그리기 – 부동소수점의 한계

아래 코드는 \*\*기울기 `m = y / x`\*\*를 사용해 점을 찍습니다.

```js
for (var x = 0; x <= width; x++) {
  var y = Math.round(m * x);
  canvas.arc(x, y, 0.15, 0, 2 * Math.PI);
}
```

📌 **문제점**

* `곱셈` + `소수점` + `반올림` → **느리다**
* **대각선 픽셀은 흩어져 보여 밝기가 낮게 보임**
* 부동소수점 연산은 정수보다 **성능이 2\~10배 느림**

### 5. 잭 브레슨햄의 혁신 – 덧셈으로 직선을 그린다!

1962년, **Jack Bresenham**은 IBM에서 근무하며 **CPU에 부동소수점이 없던 시절**\
순수 정수 덧셈만으로 직선을 그리는 방법을 고안했습니다.

#### 💡 아이디어

* 결정 변수 `d`를 설정하고 덧셈으로 x/y 방향을 판단
* 기울기 대신 변화량 `Δx`, `Δy`만 사용
* `d >= 0`이면 y를 증가시키고, 그렇지 않으면 x만 이동

#### ✅ 브레슨햄 알고리즘 코드 (JavaScript)

```js
var dx = width;
var dy = yValue;
var d = 2 * dy - dx;
var y = 0;

dx *= 2;
dy *= 2;

for (var x = 0; x <= width; x++) {
  canvas.arc(x, y, 0.4, 0, 2 * Math.PI); // 점 그리기

  if (d >= 0) {
    y++;
    d -= dx;
  }
  d += dy;
}
```

#### 🎯 결과

* **곱셈 없음**
* **정수 덧셈/뺄셈만 사용**
* **빠르고 정확**

### 6. 응용: 브레슨햄으로 그레이디언트 만들기

```js
var dc = 255;
var d = 2 * dc - dx;
var color = 0;

for (var x = 0; x <= width; x++) {
  var rgb = `rgb(${color}, ${color}, ${color})`;
  canvas.strokeStyle = rgb;
  canvas.moveTo(x, 0);
  canvas.lineTo(x, height);
  canvas.stroke();

  if (d >= 0) {
    color++;
    d -= 2 * dx;
  }
  d += 2 * dc;
}
```

#### 🟣 효과

* 정수만 사용해서 **수직 그라데이션**
* 부드럽고 빠르게 색상 변화 구현

### 7. 정수만으로 타원까지?

브레슨햄 알고리즘은 타원에도 확장됩니다.

#### 핵심 수식

```
Ax² + By² = AB
```

* `A = b²`, `B = a²`
* d (결정 변수)를 초기화하고, 세 방향 중 **가장 이상적인 방향 선택**

#### 타원 그리기 전략

* 수평, 수직, 대각선 세 점 비교 → `|d|`가 가장 작은 점 선택
* **좌표계의 1사분면만 계산**, 나머지는 대칭성으로 해결
* `(x, y)` → `(-x, y)`, `(-x, -y)`, `(x, -y)` 동시에 찍기

### 8. 정리

| 개념         | 설명                  | 예시                  |
| ---------- | ------------------- | ------------------- |
| 부동소수점 회피   | 계산 비용 높은 실수 연산 회피   | `y = mx + b` → 브레슨햄 |
| 브레슨햄 알고리즘  | 결정 변수로 선/타원 그리기     | 픽셀당 연산 최소화          |
| 대칭성 활용     | 1/4 계산 후 대칭으로 전체 구현 | 원, 타원 그리기           |
| 정수 기반 색 변화 | 점진적 덧셈으로 색상 변화      | 그레이디언트 구현           |

### 🧠 한 줄 요약

> **정수 계산은 낡았다고요?**\
> **오늘날 GPU와 게임엔진도 여전히 이 고전적인 알고리즘에 감사하고 있습니다.**

## 🎲 정교하게 '흔들기' – 난수, 프랙탈, 그리고 디더링을 넘나드는 컴퓨터 그래픽의 세계

### 1. 난수는 정말 '무작위'일까?

컴퓨터는 원칙적으로 결정적(deterministic)인 기계입니다. 즉, 같은 입력이 들어오면 반드시 같은 출력을 내는 구조이죠. 그렇다면 '난수(random number)'는 어떻게 만들 수 있을까요?

우리가 보통 쓰는 난수는 `의사 난수(pseudorandom number)`입니다. 이것은 특정 수학 공식(예: 선형 합동법)을 기반으로 만들어지며, 일정 주기를 두고 **반복되는 패턴**을 갖습니다. 그러나 암호학적 보안이 중요한 분야가 아니라면, 이 정도 난수면 충분히 "무작위처럼 보이는 수열"을 제공해줍니다.

이런 난수는 다양한 근삿값 계산에 유용하게 활용됩니다.&#x20;

{% hint style="warning" %}
예를 들어, 복잡한 곡선을 그릴 때 미세한 '우연성'을 추가하여 더 자연스럽게 보이도록 할 수 있습니다.
{% endhint %}

### 2. 공간을 가득 채우는 곡선 – 페아노, 힐베르트, 그리고 프랙탈

1890년, 이탈리아 수학자 주세페 페아노는 충격적인 아이디어를 내놓습니다. **선 하나가 평면 전체를 채울 수 있다**는 것이죠. 이렇게 나온 것이 바로 _페아노 곡선(Peano Curve)_, 그리고 그 연장선상에서 \*힐베르트 곡선(Hilbert Curve)\*과 같은 `공간 채움 곡선(space-filling curve)`입니다.

이들은 **자기 유사성(self-similarity)**&#xC774;라는 특성을 지니는데요, 가까이서 보나 멀리서 보나 구조가 반복되는 특징입니다. 이런 구조는 바로 `프랙탈(fractal)`의 본질입니다.

* 코흐 눈송이(Koch Snowflake)는 정삼각형에서 시작해, 각 변을 3등분하고 그 가운데에 작은 삼각형을 추가하는 방식으로 반복됩니다.
* 힐베르트 곡선은 선이 'U', 'L', 'R', 'D'처럼 네 방향을 순회하며 공간을 채웁니다.

> ⛏️ 실제 응용: 이렇게 생성된 프랙탈 곡선은 **디지털 아트, 렌더링 최적화, 공간 탐색 알고리즘** 등 다양한 분야에서 활용됩니다.

### 3. 식물도 규칙으로 자란다 – L-System으로 나무를 코딩하다

헝가리 생물학자 **아리스티드 린덴마이어**는 식물의 성장 과정을 모사하기 위해 **L-System(Lindenmayer System)**&#xC774;라는 규칙 기반 문법을 고안합니다.

간단한 기호만으로도 놀라운 나무를 생성할 수 있습니다.

* 예: `E → B L E R E`, `B → B B` 와 같은 규칙으로 시작하여
* 기호 `L`과 `R`로 방향 회전을 제어하고, `B`, `E`로 선분과 잎을 생성

이는 마치 **DNA가 생물의 형태를 규정짓듯**, 컴퓨터에서도 **기호 규칙만으로 복잡한 자연을 생성할 수 있음을 보여줍니다**.

🎬 이 개념은 훗날 **픽사 애니메이션**, **게임 배경**, **디지털 나무 생성기** 등 수많은 그래픽 분야의 기반이 되었습니다.

### 4. 눈속임으로 더 나은 품질을 – 디더링(Dithering) 이야기

#### (1) 문제: 회색은 두 가지 색으로 표현할 수 있을까?

흑백 프린터에서 회색을 출력하려면 어떻게 할까요? 바로 "눈을 속이면" 됩니다.

* 예: 회색 127은 흰색(255)과 검정(0)을 _섞어서 보이게_ 하면 됩니다.

이런 트릭이 바로 **디더링**입니다.

#### (2) 방법 1: 바이어 행렬 (Ordered Dithering)

픽셀마다 다른 `임계값(threshold)`을 가지게 하여 일정 패턴으로 디더링합니다.

* 바이어(Bayer) 행렬: 2x2, 3x3, 4x4 행렬 패턴을 타일링으로 반복
* 특징: 일정한 무늬로 결과가 예측 가능

하지만! 이 방법은 무아레(Moiré) 같은 **거슬리는 반복 패턴**이 생길 수 있다는 단점이 있습니다.

#### (3) 방법 2: 난수 기반 디더링

각 픽셀마다 난수를 적용하여 무작위로 밝기 여부를 판단합니다. 무늬는 없어지지만 **이미지가 흐릿해 보이는 단점**이 있습니다.

#### (4) 방법 3: 오류 전파 (Error Diffusion)

플로이드-스타인버그(Floyd–Steinberg) 알고리즘은 현재 픽셀의 **오차를 주변에 나누어 전파**합니다.

```plaintext
  현재 → 7/16
  아래 왼쪽 → 3/16
  아래     → 5/16
  아래 오른쪽 → 1/16
```

이렇게 분산된 오류 덕분에 **전체적인 밝기 보존**이 가능하며, 시각적으로도 훨씬 자연스러운 디더링을 만들어냅니다.

### 5. 곡선 따라 흐르는 디더링 – 리머스마 알고리즘

마지막으로, 네덜란드 개발자 **티아메 리머스마**는 디더링에도 **공간 채움 곡선**을 접목시킵니다.

* 그는 힐베르트 곡선(Hilbert Curve)의 순서를 따라 픽셀을 방문하며,
* 가장 최근의 16픽셀의 오류를 가중 평균(weighted average)으로 반영합니다.

그 결과, 픽셀 간의 오류가 부드럽게 흐르며, **시각적으로도 매우 정교한 디더링 효과**를 얻게 됩니다.

### 📌 요약 정리

| 주제       | 기법         | 특징                    |
| -------- | ---------- | --------------------- |
| 난수 생성    | 의사 난수      | 정해진 규칙으로 생성, 주기 존재    |
| 프랙탈      | 자기 유사성, 재귀 | 간단한 규칙으로 복잡한 구조 생성    |
| L-System | 생성 문법      | 식물, 나무 등 구조적 자연 모델링   |
| 디더링 1    | 바이어 행렬     | 예측 가능한 무늬, 빠르지만 반복 티남 |
| 디더링 2    | 난수 비교      | 무늬 없음, 흐릿한 이미지        |
| 디더링 3    | 오류 전파 (FS) | 정교한 표현, 고양이도 좋아함      |
| 디더링 4    | 리머스마       | 프랙탈 기반 디더링, 품질 최고 수준  |

***

> “진짜를 만들기보다, 진짜처럼 보이게 만드는 것”\
> – 컴퓨터 그래픽이 품은 철학은 근삿값과 디더링에 있다.

이 장은 컴퓨터가 ‘있는 그대로 그리는 법’을 배운 것이 아니라, **‘그럴 듯하게 그리는 법’을 익힌 과정**이었습니다. 난수와 패턴, 규칙과 예외, 반복과 확장. 이 모든 것이 **시각화 알고리즘의 아름다움**을 만들어냅니다.

