11장 성능을 위한 알고리즘

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

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

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

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

• 정확성(Accuracy): 결과가 정답에 얼마나 가까운가?

• 정밀성(Precision): 같은 계산을 반복했을 때 결과들이 얼마나 일관적인가?

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

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

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

1) 지름길 (Shortcut)

• 미리 계산된 값을 테이블로 만들어서 사용

• 대표 예시: 삼각함수, 로그, 온도 변환, 텍스처 매핑 등

2) 근삿값 (Approximation)

• 정밀도가 약간 떨어지더라도 계산량을 줄이기 위해 간단한 계산이나 추정 사용

• 대표 예시: 게임 렌더링, 필터링, 피라미드 이미지(MIP 맵)

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

직접 계산하는 것보다 표에서 무언가를 찾는 게 훨씬 더 빠른 경우가 종종 있습니다.

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

예시: 온도 센서 보정

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

이걸 매번 계산한다면?

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

👉 해결 방법

• 10비트 A/D 변환기 → 최대 1024 값

• 8비트 온도 테이블을 만들어, 각 A/D 값에 대응하는 온도를 미리 저장

• 필요할 때 temp = lookup[vin] 으로 끝!

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

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

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

🎮 게임 속 벽돌을 보면?

• 가까이 있으면 선명하게

• 멀어지면 흐릿하게

이런 효과를 어떻게 줄까요?

전통적 방법

1. 벽 텍스처에서 해당 좌표의 색을 가져오기

2. 멀리 있으면 평균을 내거나 다운스케일

3. 너무 느림!

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

• 아이디어: 텍스처의 여러 해상도 버전을 미리 계산해 저장

• 더 멀리 떨어진 물체에는 저해상도 버전을 사용

• 그림처럼 피라미드 구조로 저장

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

🧠 이점

• 계산 없음 → 빠르다!

• 시점에 따라 적절한 해상도 선택

• 부드러운 전환 → 시각적으로도 깔끔

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

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

전통적 접근

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

문제점?

• 매번 조건 판단

• 코드가 반복됨

✨ 해결책: 표를 만들자!

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

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

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

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

매크로로 한 줄 처리 가능

#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 문자 속성 정보를 비트로 저장	언어 처리, 컴파일러, 문법 분석기
매크로 최적화	함수를 매크로로 치환하여 호출 오버헤드 제거	단순한 수식, 논리 조건 등

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

---

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

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

1. 왜 정수 계산인가?

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

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

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

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

캔버스는 웹에서 그래픽을 그릴 수 있는 HTML 요소입니다. 모눈종이처럼 생각하면 돼요

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

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

• (0, 0): 왼쪽 위

• x축: → 오른쪽으로 증가

• y축: ↓ 아래로 증가 (우리가 아는 좌표계와 반대)

🛠 좌표계 변환 코드

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

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

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

격자 그리기 코드

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

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

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

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)

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. 응용: 브레슨햄으로 그레이디언트 만들기

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

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

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

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

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

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

• 코흐 눈송이(Koch Snowflake)는 정삼각형에서 시작해, 각 변을 3등분하고 그 가운데에 작은 삼각형을 추가하는 방식으로 반복됩니다.

• 힐베르트 곡선은 선이 'U', 'L', 'R', 'D'처럼 네 방향을 순회하며 공간을 채웁니다.

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

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

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

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

• 예: 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) 알고리즘은 현재 픽셀의 오차를 주변에 나누어 전파합니다.

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

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

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

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

• 그는 힐베르트 곡선(Hilbert Curve)의 순서를 따라 픽셀을 방문하며,

• 가장 최근의 16픽셀의 오류를 가중 평균(weighted average)으로 반영합니다.

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

📌 요약 정리

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

---

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

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