알고리즘 (Algorithm)

알고리즘(Algorithm)은 원하는 결과를 얻기 위해 계산으로 수행할 수 있도록 정한 단계들의 절차입니다. 무엇을 입력받아 어떤 순서와 조건으로 처리할지 설명하며, 같은 문제에도 여러 알고리즘을 사용할 수 있습니다. 실제 프로그램에서는 그 절차를 특정 언어의 코드로 구현하므로, 알고리즘의 원리와 구현 코드가 올바르게 동작하는지는 나누어 살펴봅니다.

입력을 결과로 바꾸는 처리 절차

미국 국립표준기술연구소의 알고리즘 사전은 알고리즘을 원하는 결과를 달성하는 계산 가능한 단계들의 집합으로 정의합니다. 숫자들을 크기순으로 정렬하거나 목록에서 특정 값을 찾는 일에는 입력 자료, 처리 규칙, 결과가 있습니다. 단순히 원하는 결과를 말하는 것보다 구체적이어야 하며, 다음에 무엇을 할지 결정할 수 있는 단계가 필요합니다. 중간 결과에 따라 다른 단계로 갈 조건도 절차에 포함됩니다.

오름차순으로 정렬된 번호 목록에서 특정 번호를 찾는다면 가운데 번호부터 비교하는 방법을 쓸 수 있습니다. 찾는 번호가 가운데 값보다 작으면 앞쪽만, 크면 뒤쪽만 남겨 다시 비교합니다. 같은 연구소의 이진 검색 설명은 이처럼 검색 구간을 반복해서 절반으로 줄이다가 값을 찾거나 구간이 비면 끝내는 절차를 제시합니다. 목록 전체를 처음부터 하나씩 확인하는 방법과는 비교 순서가 다릅니다.

이 절차에는 목록이 미리 정렬되어 있어야 한다는 전제가 붙습니다. 번호가 뒤섞인 목록에서 가운데 값보다 크다는 이유로 앞쪽을 버리면 찾는 값을 놓칠 수 있습니다. 입력의 조건은 알고리즘을 설명할 때 생략할 수 없는 부분입니다. 결과가 틀렸을 때도 절차 자체에 문제가 있는지, 정렬이라는 전제를 어겼는지 구분해야 원인을 찾을 수 있습니다. 알고리즘 이름만 같다고 어떤 입력에서나 같은 결과가 보장되지는 않습니다.

처리 원리와 구현 코드의 차이

이진 검색의 원리는 특정 프로그래밍 언어에 묶이지 않습니다. 같은 절차를 반복문으로 작성하거나 함수를 다시 호출하는 방식으로 작성할 수 있으며, 변수 이름과 문법도 구현에 따라 달라집니다. 알고리즘은 처리 단계의 관계를 설명하고 코드는 그 단계를 실제 실행 환경에 맞게 표현합니다. 코드를 다른 언어로 옮겼다는 사실만으로 알고리즘까지 달라졌다고 판단하지는 않습니다.

구현에는 추상적인 절차에 보이지 않는 제약도 나타납니다. 이진 검색에서 가운데 위치를 계산할 때 양끝 위치를 더하면, 사용하는 정수 표현의 범위를 넘을 가능성이 있습니다. 미국 국립표준기술연구소의 이진 검색 문서는 이 문제와 이를 피하는 계산식을 함께 설명합니다. 검색 구간을 절반씩 줄인다는 원리가 맞더라도 자료형과 경계값을 다루는 코드가 잘못되면 프로그램은 잘못된 결과를 낼 수 있습니다.

AI 문맥에서도 알고리즘이라는 말이 가리키는 절차를 먼저 분명히 하면 설명을 이해하기 쉽습니다. 모델을 만드는 과정의 처리 규칙을 말하는지, 만들어진 모델을 실행하는 절차를 말하는지에 따라 논의 대상이 달라집니다. 모델 이름은 특정 대상을 식별하고, 알고리즘 설명은 어떤 단계로 계산하는지 밝힙니다. 모델 하나의 이름이나 평가 점수만으로 그 안에서 사용하는 모든 처리 절차를 설명할 수는 없습니다.

입력 조건과 전체 작업 비용

빠른 알고리즘이라는 설명을 읽을 때는 무엇을 세었는지 확인합니다. 이진 검색은 정렬된 배열에서 검색 범위를 절반씩 줄여 비교 횟수를 줄입니다. 그러나 아직 정렬되지 않은 자료를 준비하는 작업이나 검색 뒤의 수정 작업까지 자동으로 빨라지는 것은 아닙니다. 실제로 수행하려는 일이 찾기만 하는 작업인지, 찾은 자리에 새 값을 넣는 작업인지에 따라 계산해야 할 비용의 범위가 달라집니다.

Python의 bisect 공식 문서는 정렬된 목록에서 값을 넣을 위치를 찾는 작업과 실제 삽입을 구분합니다. 검색 단계는 O(log n)이지만 목록에 삽입하는 단계는 O(n)이므로, 두 단계를 수행하는 insort의 비용은 삽입 단계가 좌우합니다. 여기서 n은 목록의 항목 수이며 표기는 항목 수가 커질 때 작업량이 늘어나는 방식을 나타냅니다. 초 단위 실행 시간이나 고정된 속도 배수를 뜻하지 않습니다.

같은 문서는 bisect가 특정 값의 존재를 확정하는 대신 삽입 위치를 돌려준다는 점도 명시합니다. 위치를 얻었다는 사실과 원하는 값을 찾았다는 사실은 다르므로, 존재 여부가 필요하면 해당 위치의 값까지 확인하는 절차가 필요합니다. 프로그램을 검토할 때는 입력의 정렬 조건, 함수가 돌려주는 결과의 의미, 검색 뒤에 이어지는 작업을 함께 확인합니다. 확인 범위를 정하면 알고리즘 이름만 보고 기능이나 성능을 추정하는 오류를 줄일 수 있습니다.