진법 관련 알고리즘

호너의 메소드(Honor’s method)

먼저 다짜고짜 코드부터 살펴보자. 호너의 메소드를 사용해서 2진법을 10진법으로 바꾸는 예제이다.

#include <stdio.h>  
  
int main(void) {  
    int sum = 0;  
    char vect[5] = "1101";  
  
    for (int i = 0; vect[i] != ‘\0’; i++) {  
        sum = sum * 2 + (vect[i] - ‘0’);  
    }  
    printf("%d", sum);  
    return 0;  
}  

1101이란 이진법 숫자는 풀어서 생각해보면 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0이고 아래와 같이 또 정리할 수 있다.

(((1 * 2) + 1) * 2 + 0) * 2 + 1

그리고 위와 같은 수식이 컴퓨터가 사고하기가 편한 방법이다. 같은 방식을 반복해서 사용하면 답을 찾을 수 있다.

위와 같은 호너의 메소드는 문자열 처리나 해시 함수 구현등에서 매우 유용한데, 문자열을 26진법 숫자로 생각할 수 있는 것이다. 이를 다시 10진법 숫자로 바꾸면 문자열을 하나의 숫자로 표현할 수 있다.

또한 문자열들에 대한 해시 자료구조를 사용할 때, 해시함수로 위처럼 숫자를 사용하면 훨씬 간단하고 빠르게 처리를 할 수 있다.

int hashFunc(char* key) {  
	int sum = 0;  
	for (int i = 0; key[i] != 0; i++) {  
		sum = sum * 26 + (key[i] - ‘A’);  
	}  
	return sum;  
}  

호너의 메소드를 통해 특정 진법을 10진법으로 쉽게 변경하는 법을 알아봤으니, 이번에는 다시 10진법을 특정 진법으로 바꾸는 방법을 생각해보자. 우리가 어릴적 종이에 그려가며 변환했던 나머지를 이용한 방법과 동일하다.

// target은 변경하려는 진법을 의미  
void run(int x) {  
    if (x == 0) return;    // 재귀함수는 항상 종료조건부터 챙긴다  
  
    run(x / target);  
  
    int value = x % target;  
    if (value >= 10) {  
        printf("%c", value - 10 + ‘A’);  
    } else {  
        printf("%d", value);  
    }  
}  

반복해서 나머지를 구하던 과정을 재귀함수로 표현한 것이다. key가 되는 아이디어는 나누기를 반복해서 몫이 0이 되는 것이 종료조건이라는 것이니 잘 기억이 안날때는 이것을 생각하자.