알고리즘

알고리즘, 어렵지 않아요 컴퓨터와 블록체인의 뼈대인 '순서 있는 절차' 이야기

1. 알고리즘이 대체 뭐예요?

알고리즘(Algorithm)은 어떤 입력을 원하는 출력으로 바꾸기 위해, 명확하게 정해 둔 단계들을 순서대로 늘어놓은 절차예요. 이때 각 단계는 헷갈릴 여지가 없어야 하고, 무한정 반복되지 않고 정해진 횟수 안에 끝나서 결과를 내놓아야 해요.

컴퓨터 과학에서 알고리즘은 프로그램의 논리적 뼈대예요. 재미있는 건, 같은 문제라도 알고리즘은 여러 개일 수 있고, 어떤 걸 쓰느냐에 따라 효율(얼마나 빠른지, 메모리를 얼마나 쓰는지)이 크게 달라진다는 점이에요. 알고리즘은 단순 계산뿐 아니라 데이터 처리, 기계 학습, 자동 추론 같은 곳에도 두루 쓰여요.

암호화폐와 분산원장 분야에서도 알고리즘은 아주 중요한 역할을 해요. 데이터가 변조되지 않았는지 확인하는 해싱, 여러 노드(네트워크에 참여하는 각각의 컴퓨터)가 같은 장부 상태에 합의하게 만드는 합의 알고리즘, 신원을 증명하는 전자서명이 모두 알고리즘으로 만들어져요.

이렇게 보면 쉬워요 · 요리 조리법이 재료를 음식으로 바꾸는 순서를 정하듯, 알고리즘은 데이터를 처리하는 순서를 정해 줘요.

2. '알고리즘'이라는 말은 어디서 왔어요?

'알고리즘'은 9세기 페르시아의 수학자 무함마드 알콰리즈미의 이름을 라틴어식으로 바꾼 '알고리스무스(Algorismus)'에서 나온 말이에요. 사람 이름이 말의 뿌리인 셈이죠. 한국어로는 산법(算法), 셈법, 계산절차라고도 불러요.

영어 algorithm의 발음을 두고 '알고리듬'이라고 적는 게 더 정확하다는 지적도 있어요. 하지만 실제로는 '알고리즘'이라는 표기가 훨씬 널리 쓰이고 있어요.

3. 좋은 알고리즘은 어떤 조건을 갖춰야 해요?

좀 더 딱딱하게 말하면, 알고리즘은 정해진 규칙에 따라 구별할 수 있는 기호를 다뤄서 입력에서 출력을 만들어 내는 '유한한 계산'이에요. 여기서 유한하다는 건 언젠가 반드시 끝난다는 뜻이에요.

좋은 알고리즘이 갖춰야 할 성질은 이렇게 정리돼요.

• 정밀성: 각 작업 단계가 명확하고 흔들리지 않아야 해요.
• 유일성: 한 단계 다음에 올 단계가 분명해야 해요.
• 타당성: 실제로 만들 수 있고 실용적이어야 해요.
• 입력: 정해진 입력을 받아들일 수 있어야 해요.
• 출력: 답에 해당하는 출력을 내놓아야 해요.
• 유한성: 정해진 수만큼 작업한 뒤에는 반드시 멈춰야 해요.
• 일반성: 정해진 입력 전반에 두루 적용할 수 있어야 해요.

이 중에서도 유한성이 특히 중요해요. '알고리즘이 언제 멈추는가'라는 물음은, 어떤 프로그램이 끝나긴 하는지 미리 알 수 있느냐를 따지는 '정지 문제'와 맞닿아 있거든요.

4. 알고리즘은 어떻게 표현하고, 어떤 과정을 거쳐 만들어요?

알고리즘은 한 가지 모양만 있는 게 아니에요. 우리가 쓰는 자연어(그냥 말과 글), 의사코드(프로그램처럼 보이지만 사람이 읽기 쉽게 쓴 가짜 코드), 순서도(흐름을 도형으로 그린 그림), 실제 프로그래밍 언어, 인터프리터가 다루는 제어 테이블, 유한상태기계(상태가 정해진 몇 개뿐인 기계)의 상태도 등 여러 형태로 표현할 수 있어요. 대부분은 컴퓨터 프로그램으로 구현되지만, 전기 회로나 생물의 신경 회로로 구현되기도 해요.

하나의 알고리즘이 실제 소프트웨어로 자리 잡기까지는 대체로 이런 단계를 거쳐요.

1. 문제 정의 2. 모델 고안 3. 명세 작성 4. 설계 5. 검증 6. 분석(복잡도 등) 7. 구현 8. 테스트 9. 문서화

5. 알고리즘에는 어떤 종류가 있어요?

알고리즘은 보는 기준에 따라 여러 갈래로 나눌 수 있어요.

• 구현 방식: 재귀적 알고리즘(자기 자신을 다시 불러 쓰는 방식), 연역적 알고리즘, 결정론적 알고리즘(같은 입력이면 늘 같은 결과), 근사 알고리즘(정답에 가까운 답을 빠르게), 양자 알고리즘 등이 있어요.
• 설계 기법: 무차별 대입(brute force, 될 때까지 다 넣어 보기), 분할 정복(큰 문제를 작게 쪼개 풀기), 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹(막히면 되돌아가 다른 길 시도) 등이 있어요.
• 최적화 문제: 선형 계획법, 동적 계획법, 탐욕 알고리즘(매 순간 가장 좋아 보이는 선택), 휴리스틱 함수(대충 좋은 답을 빨리 찾는 어림셈) 등이 있어요.
• 이론적 분야: 검색, 정렬, 수치, 그래프, 문자열, 암호학적 알고리즘, 기계 학습, 데이터 압축 등이 있어요.

앞서 말했듯 같은 문제라도 어떤 기법으로 접근하느냐에 따라 코드의 구조와 성능이 크게 달라져요.

6. '복잡도'가 왜 중요해요?

알고리즘이 얼마나 효율적인지는, 입력의 크기(n)가 커질 때 걸리는 시간이 어떻게 늘어나는지로 가늠해요. 이걸 나타내는 방법이 점근 표기법, 흔히 말하는 '대문자 O 표기법'이에요. O 뒤에 붙는 식이 커질수록 입력이 늘 때 더 가파르게 느려진다고 보면 돼요.

• O(1): 입력 크기와 상관없이 늘 일정한 시간에 끝나요. 예) 파일의 첫 바이트가 널인지 검사.
• O(log n): 예) 이진 탐색.
• O(n): 입력에 비례하는 시간이 들어요. 예) 기수 정렬.
• O(n log n): 예) 대표적인 정렬 알고리즘.
• O(n²): 예) 최장 공통 부분 수열 문제.
• O(n³): 예) 행렬 곱셈.
• O(2ⁿ): 예) 충족 가능성 문제.
• O(n!): 예) 배열의 모든 순열을 검사.

같은 결과를 내더라도 복잡도가 낮은 알고리즘일수록 큰 입력에서 압도적으로 빨라요. 그래서 어떤 알고리즘을 고르느냐가 실제 시스템의 성능을 좌우하는 핵심 요소가 돼요.

이렇게 보면 쉬워요 · O(1)은 몇 명이 오든 문 하나만 확인하는 것, O(n!)은 손님을 자리에 앉히는 모든 경우의 수를 다 따져 보는 것과 같아요.

7. 블록체인과 암호화폐는 알고리즘을 어떻게 써요?

암호화폐와 블록체인은 사실상 여러 알고리즘을 엮어서 작동해요. 그중 해싱 알고리즘은 아무 데이터나 넣어도 정해진 길이의 값으로 바꿔 주는데, 데이터가 변조되지 않았는지 확인하는 데 써요. 같은 입력은 언제나 같은 해시가 나오지만, 입력이 조금만 달라져도 결과가 완전히 바뀌기 때문에 위·변조를 잡아내는 데 유용해요.

블록체인마다 쓰는 해시 알고리즘이 달라요. 비트코인 계열은 SHA 계열을, 일부 코인은 스크립트(scrypt)를, 이더리움 계열은 케차크를 써요. 반대로 MD5처럼 충돌(서로 다른 입력인데 같은 해시가 나오는 현상)이 발견돼서 보안 용도로는 더 이상 쓰지 않는 해시도 있어요. 해싱은 머클 트리, 채굴, 전자서명 등 블록체인 곳곳의 밑바탕이 돼요.

넓게 보면 암호학에서 다루는 암호화(내용을 알아볼 수 없게 바꾸기)와 복호화(다시 원래대로 되돌리기)도 정해진 절차, 즉 알고리즘으로 이뤄져요.

8. 합의 알고리즘은 무슨 문제를 풀어요?

합의 알고리즘은 중앙에서 관리하는 사람 없이도 여러 노드가 하나의 장부 상태에 동의하게 만드는 규칙이에요. 탈중앙화 네트워크가 돌아가는 근간이죠. 대표적인 방식은 이래요.

• 작업증명: 채굴자에게 특정 조건을 만족하는 해시값을 찾도록 어마어마한 계산을 반복시켜요. 네트워크의 계산 능력은 해시레이트로 재고, 블록을 만든 채굴자는 블록 보상을 받아요.
• 지분증명: 가진 코인의 지분에 따라 블록을 만들 권한을 줘요. 계산으로 경쟁하는 대신 지분을 근거로 하니 에너지 소모가 상대적으로 적어요.
• 위임 지분증명: 코인 보유자가 대표 노드를 뽑아서 합의를 맡기는 변형이에요.

이런 합의 규칙은 비잔틴 장애 허용 문제, 즉 일부 노드가 고장 나거나 나쁜 마음을 먹고 엉뚱하게 행동해도 전체가 올바른 결론에 이르게 하는 문제를 푸는 알고리즘으로 볼 수 있어요. 또 합의는 같은 돈을 두 번 쓰는 이중지불을 막는 핵심 장치이기도 해요.

9. 전자서명과 머클 트리는 어떻게 안전을 지켜요?

블록체인의 안전성은 여러 암호 알고리즘에 기대고 있어요. 전자서명에는 타원곡선 암호 알고리즘을 써요. 덕분에 개인키를 가진 사람만 거래를 승인할 수 있고, 나머지 사람은 누구나 공개키로 그게 진짜인지 검증할 수 있어요.

머클 트리는 여러 거래를 해시로 묶어서 하나의 대표값으로 요약하는 자료 구조예요. 이렇게 하면 방대한 데이터가 변조되지 않았는지를 효율적으로 확인할 수 있어요. 이런 구성 절차 역시 알고리즘의 한 예이고, 앞에서 살펴본 해싱을 여러 번 반복 적용해서 만들어져요.

10. 스마트 컨트랙트와 알고리즘 트레이딩도 알고리즘이에요?

네, 맞아요. 스마트 컨트랙트는 미리 정해 둔 조건이 충족되면 자동으로 실행되는 논리예요. 그 자체가 하나의 알고리즘인 셈이죠. 조건과 결과가 코드로 고정돼 있어서 사람이 끼어들지 않아도 계약이 이행돼요.

금융 시장에서는 미리 짜 둔 규칙에 따라 자동으로 사고파는 '알고리즘 트레이딩'이 널리 쓰여요. 어느 쪽이든 '정해진 입력에 정해진 절차로 결과를 낸다'는 알고리즘의 본질은 그대로 유지돼요.

11. 앞으로 풀어야 할 숙제는 뭐예요?

알고리즘이 사회 곳곳의 결정을 대신하게 되면서, 그 작동 방식이 겉으로 잘 드러나지 않는 데서 오는 문제도 함께 커지고 있어요. 예를 들어 학습에 쓴 데이터에 담긴 편향(한쪽으로 치우친 성향)이 결과에 그대로 반영되거나, 왜 그런 판단을 내렸는지 근거를 설명하기 어려운 점 등이 대표적이에요.

블록체인 분야에서는 합의·암호 알고리즘에 허점이 생기면 곧바로 자산을 빼앗기는 일로 이어질 수 있어요. 그래서 코드가 명세대로 정말 동작하는지 수학적으로 따져 보는 정형 검증의 중요성이 강조돼요. 결국 알고리즘의 성능만이 아니라 투명성과 안전성을 어떻게 확보하느냐가 앞으로의 과제로 남아 있어요.