AI의 사각지대: 언어 모델이 Elixir 리스트를 배열로 오해하는 이유

초록 (Abstract)

거대 언어 모델(LLMs)은 소프트웨어 개발을 위한 보편적인 도구가 되어 코드 생성과 알고리즘 설명에 활용되고 있습니다. 하지만 이들에는 체계적인 사각지대가 존재합니다. 바로 Elixir 코드를 분석할 때, []를 배열로 취급하며 연결 리스트(linked list)에 적용하기 부적절한 O(1) 복잡도 가정을 한다는 것입니다. 이러한 오해는 단순한 사소한 지적이 아닙니다. 이는 잘못된 복잡도 분석을 초래하고, 성능 기대치를 오도하며, 미묘하게 작동하지 않는 코드를 만들어냅니다. 본 글은 이 오류를 해부하고, Elixir의 근본적인 데이터 구조가 실제로 가진 메모리 레이아웃과 성능 특성을 설명하며, 해결책이 단순히 기술적인 문제가 아니라 개념적인 문제임을 주장합니다.

서론 (Introduction)

Elixir에서 동적 프로그래밍(dynamic programming) 솔루션을 최적화해달라고 AI에게 요청한다고 상상해 봅시다. AI는 자신감 있게 중첩 루프를 사용하고, 리스트에 Enum.at/2와 List.replace_at/3을 사용하여 O(n × k)의 시간 복잡도를 선언합니다. 코드는 컴파일되고, 작은 입력값에서는 테스트가 통과합니다. 하지만 표면 아래에는 알고리즘이 실제로는 O(n × k²)라는 이차적인 폭발(quadratic blowup)을 일으켜, 현실적인 입력값에서는 타임아웃될 수 있습니다.

이 시나리오는 가설이 아닙니다. 이는 반복적이고 재현 가능한 실패 모드입니다. AI는 연결 리스트를 배열로 혼동했으며, 이 혼동은 결함 있는 알고리즘과 잘못된 복잡도 분석으로 이어졌습니다.

근본적인 원인은 간단합니다: Elixir에서 []는 배열이 아닙니다. 그것은 단일 연결 리스트(singly linked list)입니다. Elixir에서 배열에 가장 가까운 것은 튜플 ({})입니다. 이 구별점은 성능 좋은 Elixir 코드를 작성하는 데 근본적이지만, 바로 이 구별점이 Python이나 Java 같은 명령형 언어(imperative languages)를 주로 학습한 언어 모델들이 지속적으로 놓치는 지점입니다.

오류의 시연 (The Error, Demonstrated)

실패 사례를 구체화해 봅시다. Elixir에서 바텀업 동적 프로그래밍 솔루션을 구현하라는 요청을 받은 AI가 다음과 같은 코드를 생성할 수 있습니다:

AI가 생성한 "O(n × k)" 솔루션 — 실제로는 O(n × k²)

def build_dp(n, k) do
initial_dp = List.duplicate(0, k + 1) |> List.replace_at(0, 1)
...

AI의 추론 과정은 투명합니다: AI는 Python이나 C++에서 한 차원 배열 dp[j]를 사용하는 동적 프로그래밍 솔루션을 본 적이 있으며, 이를 기계적으로 dp[j]를 Enum.at(dp, j)로, 그리고 dp[j] = value를 List.replace_at(dp, j, value)로 번역했습니다. AI는 이러한 연산들이 배열에서와 마찬가지로 O(1)이라고 가정합니다.

하지만 그렇지 않습니다.

현실: 리스트는 연결형이고, 튜플은 연속적이다

Elixir의 공식 문서는 모호하지 않습니다:

리스트는 연결 리스트(각 항목이 다음 항목을 가리키는 방식)로 구현되는 반면, 튜플은 메모리에 연속적으로 저장됩니다. 이는 튜플 요소에 접근하는 것이 매우 빠르다(상수 시간)는 것을 의미하며 elem 함수를 사용하여 달성할 수 있습니다.

튜플의 요소를 접근하는 것은 이미 크기가 알려져 있기 때문에 상수 $O(1)$ 복잡도를 가집니다. 리스트의 요소에 접근하는 것은 필요한 요소의 인덱스 n이 있을 때 $O(n)$ 복잡도입니다.

연결 리스트에서 각 요소는 값과 다음 요소를 가리키는 포인터를 포함하는 "cons cell"에 저장됩니다. 인덱스 j에 도달하려면 런타임은 j개의 포인터를 따라가야 하므로 **O(j)**의 접근 시간이 발생합니다. 요소를 업데이트하는 것은 훨씬 더 나쁩니다: List.replace_at/3는 해당 인덱스까지 순회해야 하며, 그 지점부터 리스트를 재구성해야 하므로 역시 **O(j)**입니다.

반면 튜플은 C 배열처럼 요소들을 메모리에 연속적으로 저장합니다. elem/2는 상수 시간 연산이며, put_elem/3은 전체 튜플의 얕은 복사본을 생성합니다—크기가 k인 튜플의 경우 **O(k)**이지만 작은 상수 인자를 가집니다.

성능에 미치는 영향은 명확합니다. Elixir 커리큘럼의 벤치마크는 튜플에서 요소를 접근하는 것이 리스트에서 접근하는 것보다 수 배 이상 빠르며, 인덱스가 증가함에 따라 그 격차는 더 벌어집니다.

올바른 구현: 배열처럼 사용되는 튜플

효율적인 Elixir 솔루션은 리스트가 아닌 튜플을 사용합니다:

# 튜플을 사용하는 올바른 O(n × k) 솔루션
def build_dp(n, k) do
  initial_dp =
...

핵심 통찰력은 **전체 튜플 재구성이 단일 Enum.map 패스에서 O(k)**라는 것이지, O(k²)가 아니라는 점입니다. AI의 실수는 개별적인 put_elem/3 연산을 k번 수행한 것입니다. 이 각 연산이 O(k)를 차지하여 행당 총 O(k²)의 복잡도를 초래했습니다.

AI가 잘못 이해하는 이유

이 오류는 무작위적이지 않습니다. 세 가지 복합적인 요인에서 비롯됩니다:

학습 데이터 편향성. 인터넷상의 알고리즘 코어버스트는 압도적으로 Python, Java, C++, 또는 JavaScript로 작성되어 있습니다. 이 언어들에서는 []가 O(1) 인덱스 접근이 가능한 배열입니다. 이러한 코퍼스로 훈련된 LLM은 "대괄호는 배열을 의미한다"라는 강력한 선험적 지식(prior)을 학습했습니다. 따라서 Elixir 구문을 만났을 때, 근본적인 의미론(semantics)을 확인하지 않고 이 선험적 지식을 적용합니다.

피상적인 구문 유사성. Elixir의 [] 구문은 Python의 리스트 구문과 시각적으로 동일해 보입니다. AI는 dp = [0, 0, 0]를 보고 이것이 Python 리스트(그 자체로 동적 배열임)처럼 작동한다고 가정합니다. 명시적으로 지시받지 않는 한, Elixir의 []가 cons-cell 연결 리스트라는 사실을 "알지" 못하는 것입니다.

런타임 피드백 부족. 코드를 생성하는 AI는 실제로 실행해 보지 않습니다. 따라서 이차적인 속도 저하(quadratic slowdown)를 관찰할 수 없습니다. 이 오류는 조용하며, AI가 이를 감지할 메커니즘이 없습니다.

이는 더 광범위한 문제의 특정 사례입니다: LLM은 의미론적 추론자(semantic reasoner)가 아니라 패턴 매처(pattern matcher)입니다. 그들은 겉보기에 올바른 코드를 생성하는 데 탁월하지만, 자신이 생성하는 언어의 실행 모델을 이해하지 못합니다. Elixir의 함수형, 불변성, BEAM 기반 런타임은 명령형 주류 개발 환경과 충분히 다르기 때문에 이러한 의미론적 격차는 빈번하고 중대한 결과를 초래하게 됩니다.

리스트와 튜플을 넘어: 더 광범위한 패턴

리스트 대 배열의 혼동은 이 실패 모드의 가장 흔한 사례이지만, 유일한 경우는 아닙니다. Elixir에서 유사한 AI 오류에는 다음과 같은 것들이 포함됩니다:

• String 연산을 O(1)로 간주: Elixir 문자열은 UTF-8 바이너리이며, String.at/2는 O(n)입니다. 문자열 알고리즘을 최적화하는 AI가 순환문 내에서 String.at을 순진하게 사용하면 2차 시간 복잡도(quadratic behavior)를 초래할 수 있습니다.
• Enum.length/1이 O(1)이라고 가정: 리스트의 경우 이는 O(n)입니다. AI는 탐색 비용(traversal cost)을 알지 못한 채 순환문 내에서 length/1을 호출할 수 있습니다.
• 맵(maps)과 해시 테이블 혼동: Elixir 맵은 O(log n)의 접근 속도를 가지며, O(1)이 아닙니다. Python dict에 익숙한 AI는 상수 시간 조회(constant-time lookups)를 가정할 수 있습니다.

공통적인 흐름은 AI가 명령형 언어(imperative languages)의 성능 모델을 함수형 런타임에 적용하고 있다는 것입니다. Elixir의 데이터 구조는 영속적(persistent), 불변적(immutable), 그리고 구조적으로 공유되는 특성을 가지며, 이러한 속성들이 복잡도 특성을 근본적으로 변화시킵니다.

오류가 초래하는 비용 (The Cost of the Error)

이것이 왜 중요할까요? 잘못된 복잡도 분석은 단순한 미관상의 문제가 아니기 때문입니다. 이는 다음과 같은 결과를 낳습니다:

1. 작은 테스트는 통과하지만 대규모에서는 실패하는 알고리즘. O(n × k²) DP 솔루션은 n=100일 때는 작동하겠지만, n=1000일 때는 시간 초과가 발생합니다.
2. 오해를 불러일으키는 인터뷰 준비. AI가 생성한 분석을 신뢰하는 지원자들은 잘못된 정신 모델(mental models)을 가지고 면접에 임하게 됩니다.
3. 신뢰도 하락. AI가 알고리즘이 O(n × k)라고 자신 있게 선언했지만 실제로는 O(n × k²)인 경우, 사용자들은 도구의 신뢰성을 잃게 됩니다.

가장 위험한 측면은 이 오류가 코드 검토 과정에서 눈에 보이지 않는다는 것입니다. 구문(syntax)은 정확하고 논리(logic)도 정확합니다. 오직 성능 모델만 잘못되었을 뿐이며, 성능 모델은 풀 리퀘스트(pull requests)에서 거의 검토되지 않습니다.

해결책: 단순한 문법이 아닌 의미론적 인식 (Semantic Awareness)

해결책은 AI 도구를 포기하는 것이 아니라, 그들이 단순히 구문뿐만 아니라 대상 언어의 **실행 모델(execution model)**에 대해 추론하도록 요구하는 것입니다. Elixir의 경우, 이는 다음을 의미합니다:

1. 데이터 구조의 의미론을 명확히 설명하는 것. AI는 []가 연결 리스트(linked list)이고 {}가 튜플(tuple)이라는 것을 알아야 하며, 이 구분이 복잡도에 중요하다는 점을 인식해야 합니다.
2. 언어의 실제 구현과 비교하여 복잡도 주장을 검증하는 것. AI가 O(1) 접근을 선언할 때, 이는 근본적인 메모리 모델을 지적함으로써 정당화할 수 있어야 합니다.
3. Elixir에서 튜플 기반 DP를 선호하는 것. 알고리즘이 인덱스 접근과 업데이트를 필요로 할 때, 튜플은 거의 항상 올바른 선택입니다.

인간 개발자에게도 교훈은 마찬가지로 중요합니다: []가 모든 언어에서 같은 의미를 갖는다고 절대 가정해서는 안 됩니다. Elixir에서는 연결 리스트를 의미합니다. Python에서는 동적 배열(dynamic array)을 의미합니다. JavaScript에서는 동적 배열을 의미합니다. 문법은 보편적이지만, 의미론은 그렇지 않습니다.

결론

Elixir 리스트와 배열 사이의 AI의 혼동은 AI 지원 프로그래밍에서 더 큰 과제의 축소판입니다: 구문적 능력(syntactic competence)이 의미론적 이해를 함축하지는 않는다. 언어 모델은 컴파일되고 테스트를 통과하는 Elixir 코드를 생성할 수 있지만, 그 기반은 해당 언어가 실행되는 방식에 대한 근본적으로 결함 있는 모델 위에 놓여 있습니다.

Elixir의 경우 특히, 해결책은 명확합니다: 리스트는 연결 리스트이며, 튜플이 배열에 가장 가깝습니다. Enum.at/2를 O(1)로 취급하거나 List.replace_at/3를 저렴하다고 간주하는 모든 AI 분석은 잘못되었으며, 그 결과로 나오는 복잡도 주장은 신뢰할 수 없습니다.

AI 도구가 개발 워크플로우에 더 통합됨에 따라, 개발자들은 성능 주장을 비판적으로 평가해야 하는 부담을 안게 됩니다. 특히 비주류 실행 모델(non-mainstream execution models)을 가진 언어에서 더욱 그렇습니다. 불변 데이터 구조와 BEAM 런타임을 가진 Elixir는 바로 그러한 언어입니다. 리스트 대 배열 오류는 예외적인 경우가 아니라, 경각심을 일깨우는 신호탄입니다.