{"type":"doc","content":[{"type":"image","attrs":{"textAlign":null,"src":"/assets-api/uploads/c21839f193b8012b.jpg","alt":null,"title":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"기본 알고리즘인 정렬이나 해싱은 어느 하루를 기준으로 해도 수조 번 사용된다. 계산 수요가 증가함에 따라, 이러한 알고리즘이 가능한 한 높은 성능을 갖추는 것은 점점 더 중요해졌다. 과거에 괄목할 만한 진전이 있었음에도 불구하고, 이러한 루틴의 효율을 더 개선하는 일은 인간 연구자에게도, 계산적 접근법에게도 어려운 과제로 남아 있었다. 본 연구에서는 인공지능이 지금까지의 최첨단 수준을 넘어, 기존에 알려지지 않았던 새로운 루틴을 발견할 수 있음을 보인다. 이를 위해 더 나은 정렬 루틴을 찾는 문제를 단일 플레이어 게임으로 정식화하였다. 그리고 이 게임을 수행하도록 새로운 심층 강화학습 에이전트인 AlphaDev를 학습시켰다. AlphaDev는 처음부터 작은 정렬 알고리즘들을 발견했으며, 이들은 기존에 인간이 만든 기준 구현보다 더 우수한 성능을 보였다. 이 알고리즘들은 LLVM 표준 C++ 정렬 라이브러리에 통합되었다. 정렬 라이브러리의 이 부분이 변경되었다는 것은, 강화학습을 통해 자동으로 발견된 알고리즘으로 기존 구성 요소 하나가 대체되었음을 의미한다. 또한 본 연구는 추가적인 영역들에서의 결과도 제시하며, 이 접근법이 일반적으로 적용 가능함을 보여준다. -"},{"type":"text","marks":[{"type":"italic"}],"text":"Faster sorting algorithms discovered using deep reinforcement learning"},{"type":"text","text":". "},{"type":"text","marks":[{"type":"italic"}],"text":"Nature(2023)"}]}]},{"type":"paragraph","attrs":{"textAlign":null}},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"시작하기에 앞서"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"알고리즘 교과서에서 정렬은 보통 \"해결된 문제\"로 취급된다. Timsort, pdqsort, introsort 같은 하이브리드 알고리즘들이 이미 수십 년간 최적화되어 있고, 표준 라이브러리에 들어간 코드는 전문가들이 반복 검토한 결과물이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"2023년 구글 딥마인드의 AlphaDev는 그 전제를 틀렸다고 증명했다. 발견한 것은 새로운 알고리즘이 아니다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"기존 sort3 커널에서 명령 하나를 제거하는 instruction sequence다. 그리고 그 한 줄이 LLVM libc++에 반영되었다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 글은 그 발견이 왜 의미 있는지를 설명한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그러려면 퀵소트(퀵정렬)부터 시작해야 한다."}]},{"type":"image","attrs":{"textAlign":"center","src":"/assets-api/uploads/81608e81a4ece7a2.gif","alt":null,"title":null}},{"type":"paragraph","attrs":{"textAlign":"center"},"content":[{"type":"text","text":"(퀵 정렬 애니메이션)"}]},{"type":"interactiveCodeBlock","attrs":{"code":{"html":"

comparisons

swaps

step

— / —

Reset을 눌러 시작하세요.

\n \n \n Speed\n \n 2x\n

\n pivot\n 비교 중\n swap\n 정렬 완료\n 미정렬\n

","css":"* {\n box-sizing: border-box;\n margin: 0;\n padding: 0;\n}\n\nbody {\n background: #0f0f0f;\n color: #e0e0e0;\n font-family: 'JetBrains Mono', 'Fira Code', monospace;\n padding: 2rem;\n}\n\n#qs {\n max-width: 720px;\n margin: 0 auto;\n}\n\n.stats {\n display: grid;\n grid-template-columns: repeat(3, minmax(0, 1fr));\n gap: 8px;\n margin-bottom: 1rem;\n}\n\n.sv {\n background: #1a1a1a;\n border: 0.5px solid #2a2a2a;\n border-radius: 8px;\n padding: 10px 14px;\n}\n\n.sl {\n font-size: 11px;\n color: #666;\n margin-bottom: 4px;\n}\n\n.sn {\n font-size: 22px;\n font-weight: 500;\n color: #e0e0e0;\n}\n\n.bars {\n display: flex;\n align-items: flex-end;\n gap: 3px;\n height: 200px;\n margin: 1rem 0;\n border-bottom: 0.5px solid #2a2a2a;\n}\n\n.b {\n flex: 1;\n min-width: 4px;\n border-radius: 2px 2px 0 0;\n}\n\n.info {\n font-size: 12px;\n color: #666;\n min-height: 34px;\n padding: 6px 0;\n word-break: break-all;\n margin-bottom: 0.5rem;\n}\n\n.ctrl {\n display: flex;\n align-items: center;\n gap: 10px;\n flex-wrap: wrap;\n margin-bottom: 12px;\n}\n\nbutton {\n background: transparent;\n border: 0.5px solid #444;\n color: #e0e0e0;\n padding: 6px 16px;\n border-radius: 6px;\n font-family: inherit;\n font-size: 13px;\n cursor: pointer;\n}\n\nbutton:hover {\n background: #1a1a1a;\n}\n\nbutton:active {\n transform: scale(0.97);\n}\n\ninput[type=\"range\"] {\n width: 80px;\n accent-color: #EF9F27;\n}\n\n.lbl {\n font-size: 13px;\n color: #666;\n}\n\n.leg {\n display: flex;\n gap: 14px;\n flex-wrap: wrap;\n font-size: 11px;\n color: #666;\n}\n\n.dot {\n display: inline-block;\n width: 8px;\n height: 8px;\n border-radius: 1px;\n margin-right: 3px;\n vertical-align: middle;\n}","javascript":"(function () {\n const N = 26;\n let steps = [], idx = 0, playing = false, tid = null;\n\n const COLORS = {\n n: '#888',\n pv: '#EF9F27',\n cp: '#378ADD',\n sw: '#D85A30',\n ok: '#1D9E75'\n };\n\n function gen() {\n return Array.from({ length: N }, () => Math.floor(Math.random() * 85) + 8);\n }\n\n function record(input) {\n const a = [...input];\n const n = a.length;\n const out = [];\n let cmps = 0, swps = 0;\n const done = new Array(n).fill(false);\n\n function snap(hi, msg) {\n const cls = new Array(n).fill('n');\n done.forEach((v, k) => { if (v) cls[k] = 'ok'; });\n hi.forEach(h => { cls[h.i] = h.c; });\n out.push({ a: [...a], cls, msg, cmps, swps });\n }\n\n function qs(lo, hi, d) {\n if (lo > hi) return;\n if (lo === hi) {\n if (!done[lo]) {\n done[lo] = true;\n snap([], '[depth ' + d + '] index ' + lo + ' 단독 확정');\n }\n return;\n }\n\n const mid = (lo + hi) >> 1;\n cmps += 3;\n snap(\n [{ i: lo, c: 'cp' }, { i: mid, c: 'cp' }, { i: hi, c: 'cp' }],\n '[depth ' + d + '] median-of-3 후보: lo=' + lo + ', mid=' + mid + ', hi=' + hi\n );\n\n if (a[lo] > a[mid]) { [a[lo], a[mid]] = [a[mid], a[lo]]; swps++; }\n if (a[lo] > a[hi]) { [a[lo], a[hi]] = [a[hi], a[lo]]; swps++; }\n if (a[mid] > a[hi]) { [a[mid], a[hi]] = [a[hi], a[mid]]; swps++; }\n\n [a[mid], a[hi]] = [a[hi], a[mid]];\n swps++;\n const pv = a[hi];\n snap([{ i: hi, c: 'pv' }], '[depth ' + d + '] pivot=' + pv + ' → index ' + hi + '로 이동');\n\n let store = lo;\n for (let j = lo; j < hi; j++) {\n cmps++;\n snap(\n [{ i: hi, c: 'pv' }, { i: j, c: 'cp' }, { i: store, c: 'cp' }],\n '[depth ' + d + '] arr[' + j + ']=' + a[j] + ' vs pivot=' + pv\n );\n if (a[j] <= pv) {\n if (j !== store) {\n [a[j], a[store]] = [a[store], a[j]];\n swps++;\n snap(\n [{ i: hi, c: 'pv' }, { i: j, c: 'sw' }, { i: store, c: 'sw' }],\n '[depth ' + d + '] swap arr[' + j + ']↔arr[' + store + ']'\n );\n }\n store++;\n }\n }\n\n [a[store], a[hi]] = [a[hi], a[store]];\n swps++;\n done[store] = true;\n snap([{ i: store, c: 'ok' }], '[depth ' + d + '] pivot ' + pv + ' → index ' + store + ' 확정');\n\n qs(lo, store - 1, d + 1);\n qs(store + 1, hi, d + 1);\n }\n\n qs(0, n - 1, 0);\n out.push({\n a: [...a],\n cls: new Array(n).fill('ok'),\n msg: '정렬 완료! comparisons=' + cmps + ' swaps=' + swps,\n cmps,\n swps\n });\n return out;\n }\n\n function render() {\n const s = steps[idx];\n if (!s) return;\n const max = Math.max(...s.a);\n const bars = document.getElementById('bars');\n if (bars.children.length !== s.a.length) {\n bars.innerHTML = s.a.map(() => '

').join('');\n }\n s.a.forEach((v, i) => {\n const el = bars.children[i];\n el.style.height = Math.round(v / max * 190) + 'px';\n el.style.background = COLORS[s.cls[i]] || COLORS.n;\n });\n document.getElementById('info').textContent = s.msg;\n document.getElementById('sc').textContent = s.cmps;\n document.getElementById('ss').textContent = s.swps;\n document.getElementById('st').textContent = (idx + 1) + ' / ' + steps.length;\n }\n\n function msPerStep() {\n return [350, 180, 90, 45, 15][parseInt(document.getElementById('spd').value) - 1];\n }\n\n function advance() {\n if (idx >= steps.length - 1) {\n playing = false;\n document.getElementById('pbtn').textContent = 'Play';\n return;\n }\n idx++;\n render();\n if (playing) tid = setTimeout(advance, msPerStep());\n }\n\n window.qsToggle = function () {\n if (!steps.length) return;\n playing = !playing;\n document.getElementById('pbtn').textContent = playing ? 'Pause' : 'Play';\n if (playing) { clearTimeout(tid); advance(); }\n else clearTimeout(tid);\n };\n\n window.qsReset = function () {\n playing = false;\n clearTimeout(tid);\n document.getElementById('pbtn').textContent = 'Play';\n steps = record(gen());\n idx = 0;\n render();\n };\n\n qsReset();\n})();"},"height":780}},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"퀵소트(퀵 정렬)의 기본 구조"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"퀵소트는 분할 정복(divide and conquer) 알고리즘이다. 동작 원리는 단순하다."}]},{"type":"orderedList","attrs":{"start":1,"type":null},"content":[{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"1.배열에서 pivot을 하나 고른다."}]}]},{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"2.pivot보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분리한다. 이 단계를 partition이라 한다."}]}]},{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"3.왼쪽 부분 배열과 오른쪽 부분 배열에 대해 재귀적으로 같은 과정을 반복한다."}]}]}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"코드로 보면 다음과 같다."}]},{"type":"codeBlock","attrs":{"language":"cpp"},"content":[{"type":"text","text":"void quicksort(int* arr, int lo, int hi) {\n if (lo >= hi) return;\n int pivot_idx = partition(arr, lo, hi);\n quicksort(arr, lo, pivot_idx - 1);\n quicksort(arr, pivot_idx + 1, hi);\n}"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"퀵소트에 필요한(partition)의 구현은 여러 가지가 있지만 여러가지 있지만, Lomuto Scheme 기준으로는 pivot을 맨 오른쪽에 두고 왼쪽에서부터 순회하며 pivot보다 작은 원소를 앞으로 밀어낸다."}]},{"type":"codeBlock","attrs":{"language":"cpp"},"content":[{"type":"text","text":"int partition(int* arr, int lo, int hi) {\n int pivot = arr[hi];\n int i = lo - 1;\n for (int j = lo; j < hi; j++) {\n if (arr[j] <= pivot) {\n i++;\n std::swap(arr[i], arr[j]);\n }\n }\n std::swap(arr[i + 1], arr[hi]);\n return i + 1;\n}"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"평균 시간복잡도는 O(n log n)이다. 분할(partition)이 매번 배열을 절반 근처로 나눈다고 가정하면, 재귀 깊이는 log n이고 각 단계에서 O(n) 작업이 발생하기 때문이다."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"최악 케이스와 pivot 선택 문제"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"퀵소트의 약점은 pivot 선택에 있다. partition 이후 두 부분 배열의 크기가 균등할수록 성능이 좋고, 한쪽으로 치우칠수록 나빠진다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"최악의 경우는 매번 pivot이 최솟값이나 최댓값으로 선택될 때다. 이러면 한쪽 부분 배열의 크기가 항상 0이 되고, 재귀 깊이가 n이 된다. 시간복잡도는 O(n²)로 떨어진다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 상황이 발생하는 대표적인 입력이 있다."}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"1.이미 정렬된 배열에 첫 번째 원소를 pivot으로 선택하는 경우"}]}]},{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"2.역순으로 정렬된 배열에 마지막 원소를 pivot으로 선택하는 경우"}]}]},{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"모든 원소가 동일한 경우"}]}]}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"단순한 퀵소트 구현에서 정렬된 입력이 가장 느리다는 것은 직관에 반한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"라이브러리 수준에서 이 문제를 방치할 수 없는 이유다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"초기 해결책 중 하나는 pivot을 무작위로 선택하는 것이었다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"랜덤 pivot은 특정 입력에 대한 최악 케이스를 확률적으로 희석시킨다. 하지만 난수 생성 비용이 있고, 최악 케이스 자체를 제거하지는 못한다."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"median-of-3 전략"}]},{"type":"codeBlock","attrs":{"language":"cpp"},"content":[{"type":"text","text":"int median_of_3(int* arr, int lo, int hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[lo] > arr[mid]) std::swap(arr[lo], arr[mid]);\n if (arr[lo] > arr[hi]) std::swap(arr[lo], arr[hi]);\n if (arr[mid] > arr[hi]) std::swap(arr[mid], arr[hi]);\n return mid;\n}"}]},{"type":"paragraph","attrs":{"textAlign":"center"},"content":[{"type":"text","text":"(median-of-3)"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"("},{"type":"text","marks":[{"type":"code"}],"text":"(lo + hi) / 2"},{"type":"text","text":" 대신 "},{"type":"text","marks":[{"type":"code"}],"text":"lo + (hi - lo) / 2"},{"type":"text","text":"를 쓴 이유는 "},{"type":"text","marks":[{"type":"code"}],"text":"lo + hi"},{"type":"text","text":"가 "},{"type":"text","marks":[{"type":"code"}],"text":"INT_MAX"},{"type":"text","text":"를 넘을 때 오버플로가 발생하기때문이고, C++에서 이 차이가 실제로 버그로 이어진다)"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"실용적인 대안으로 등장한 것이 median-of-3 pivot 선택이다. 배열의 첫 번째, 중간, 마지막 원소 중 중앙값을 pivot으로 선택하는 방식이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 방식은 이미 정렬된 배열이나 역순 배열에서 항상 최악의 pivot이 선택되는 문제를 완화한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"세 후보 중 중앙값은 전체 배열의 실제 중앙값에 가까울 가능성이 높기 때문이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"더 중요한 점은 부수효과(Side effect)다. median-of-3 과정에서 세 원소를 비교하고 위치를 조정하면, 그 세 원소는 이미 정렬된 상태가 된다. 이 부분 배열이 partition 이후 경계에 위치하게 되므로, 이후 재귀 호출에서 이 세 원소를 다시 처리할 필요가 없다. 실질적으로 partition 비용도 줄어든다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"Sedgewick이 1970년대에 이 방식을 체계화한 이후, median-of-3는 실용적인 퀵소트 구현의 표준 전략이 되었다."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"최악 케이스를 완전히 제거하려면 - introsort"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"median-of-3로도 최악 케이스를 완전히 없앨 수는 없다. 극단적인 입력이 반복되거나, 의도적으로 구성된 입력에 대해서는 여전히 O(n²)가 발생할 수 있다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 문제를 해결한 것이 introsort다. 1997년 David Musser가 제안했으며, 퀵소트와 힙소트를 결합한 하이브리드 알고리즘이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"동작 방식은 다음과 같다."}]},{"type":"orderedList","attrs":{"start":1,"type":null},"content":[{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"1.재귀 깊이를 추적한다. 임계값은 보통 "},{"type":"text","marks":[{"type":"code"}],"text":"2 * log2(n)"},{"type":"text","text":"이다."}]}]},{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"2.재귀 깊이가 임계값 이하이면 퀵소트(median-of-3 pivot)를 사용한다."}]}]},{"type":"listItem","content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"3.재귀 깊이가 임계값을 초과하면 힙소트로 전환한다."}]}]}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"힙소트는 O(n log n)이 항상 보장되므로, 퀵소트가 최악 케이스로 빠지기 시작하는 시점을 감지해 힙소트로 전환하면 전체 시간복잡도 보장이 가능하다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"여기에 한 가지 최적화가 더 붙는다. 부분 배열의 크기가 일정 임계값(보통 16 이하) 이하가 되면 삽입 정렬로 전환한다. 소규모 배열에서는 삽입 정렬의 상수 인자가 퀵소트보다 작기 때문이다. 캐시 친화성도 삽입 정렬이 유리하다."}]},{"type":"codeBlock","attrs":{"language":"cpp"},"content":[{"type":"text","text":"static constexpr int THRESHOLD = 16;\n\nvoid introsort(int* arr, int lo, int hi, int depth_limit) {\n if (hi - lo < THRESHOLD) {\n insertion_sort(arr, lo, hi);\n return;\n }\n if (depth_limit == 0) {\n heap_sort(arr, lo, hi);\n return;\n }\n int pivot_idx = median_of_3(arr, lo, hi);\n pivot_idx = partition(arr, lo, hi);\n introsort(arr, lo, pivot_idx - 1, depth_limit - 1);\n introsort(arr, pivot_idx + 1, hi, depth_limit - 1);\n}\n\nvoid sort(int* arr, int n) {\n int depth_limit = 2 * static_cast(std::log2(n));\n introsort(arr, 0, n - 1, depth_limit);\n}"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C++ STL의 "},{"type":"text","marks":[{"type":"code"}],"text":"std::sort"},{"type":"text","text":"는 introsort 기반이다. GCC libstdc++, LLVM libc++ 모두 이 구조를 따른다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"자, 근데 이걸 왜 글쓴이는 쓴걸까? "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"20여년간 이어진 이 문제에 대해서 AI가 새로운 해법을 23년도에 발견해냈기 때문이다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"우선 그전에 AI가 대체 무엇을 발견했는가에 대해서 알기 위해 필요한 기초지식을 쌓아보자."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"커널이란 무엇인가?"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"Kernel (핵심)"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"보통 핵심이라고하는데, 컴퓨터 좀 한다하는 사람들은 다 커널하면 OS를 말한다 생각하지만,"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"참고로 여기서 커널이란 일반적 운영체제를 뜻하는 Kernel이라기보다는 더 큰 알고리즘 내부에서 호출되는 "},{"type":"text","marks":[{"type":"bold"}],"text":"아주 작은 연산 단위"},{"type":"text","text":"를 뜻한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"23년도에 AI, AlphaDev가 개선한 것은 이 고정 크기 커널들이다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"sort라는 이름의 커널들은 정렬에 주로 쓰이는 작은 연산 단위였는데,"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"구체적으로는 sort3, sort4, sort5가 대상이었고, 각각에서 기존 인간이 작성한 최적 구현보다 더 적은 명령어로 동작하는 명령 시퀀스를 찾아냈다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"즉 군더더기를 뺀 더 효율적인 효율을 발견한 것이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이제 sort들의 연산을 정리하면"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"sort1은 원소 1개, sort2는 원소 2개, sort3는 원소 3개를 처리하는 코드 블록이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"sort1은 아무 작업이 없는 연산이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"sort2는 비교 한 번과 조건부 교환 한 번으로 끝난다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"sort3는 정확히 3개 원소를 정렬하는 고정 크기 커널이다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 커널들은 독립적으로 호출되기도 하지만, 주로 더 큰 정렬 알고리즘의 내부 구성 요소로 사용된다."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"왜 sort3?"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"sort3는 정확히 3개 원소를 정렬하는 고정 크기 커널이며, "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"bold"}],"text":"입력 크기가 정확히 3개로 고정된 정렬 루틴"},{"type":"text","text":"이다."},{"type":"hardBreak"},{"type":"text","text":"일반 정렬처럼 임의 길이 배열을 처리하지 않으며, 길이가 컴파일 시점에 확정되어 있으므로 루프나 재귀 없이 "},{"type":"text","marks":[{"type":"bold"}],"text":"비교(compare)"},{"type":"text","text":" 와 "},{"type":"text","marks":[{"type":"bold"}],"text":"조건부 교환(conditional swap)"},{"type":"text","text":" 만으로 구성된다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이런 커널은 단독으로도 사용할 수 있지만, 실제로는 "},{"type":"text","marks":[{"type":"code"}],"text":"std::sort"},{"type":"text","text":" 같은 더 큰 정렬 알고리즘 안에서 "},{"type":"text","marks":[{"type":"bold"}],"text":"알고리즘을 구성하는 코드 블록"},{"type":"text","text":"으로 더 자주 쓰인다."},{"type":"hardBreak"},{"type":"text","text":"예를 들어 introsort는 pivot 선택을 위한 "},{"type":"text","marks":[{"type":"code"}],"text":"median-of-3"},{"type":"text","text":" 단계에서 "},{"type":"text","marks":[{"type":"code"}],"text":"sort3"},{"type":"text","text":"를 호출하고, 작은 구간으로 내려가면 삽입 정렬 전환 구간에서도 2~4개 원소 수준의 소규모 정렬 루틴을 반복적으로 사용한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"즉 "},{"type":"text","marks":[{"type":"code"}],"text":"sort3"},{"type":"text","text":"는 “3개짜리 장난감 정렬”이 아니라,"},{"type":"hardBreak"},{"type":"text","marks":[{"type":"bold"}],"text":"대형 정렬 알고리즘이 반복적으로 의존하는 작은 핵심 연산"},{"type":"text","text":"이다."},{"type":"hardBreak"},{"type":"text","text":"크기는 작지만 호출 빈도가 매우 높기 때문에, 여기서 명령어 한두 개를 줄이는 최적화도 전체 시스템 수준에서는 큰 누적 효과를 낼 수 있다."}]},{"type":"image","attrs":{"textAlign":null,"src":"/assets-api/uploads/3487e286b100aead.webp","alt":null,"title":null}},{"type":"paragraph","attrs":{"textAlign":null}},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"("},{"type":"text","marks":[{"type":"bold"}],"text":"a"},{"type":"text","text":" . 최대 두 개의 요소로 이루어진 입력 시퀀스를 정렬하는 변수 정렬 함수의 C++ 구현. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"bold"}],"text":"b . a"},{"type":"text","text":" 의 C++ 구현은 다음과 같은 저수준 어셈블리 표현으로 컴파일된다.)"},{"type":"hardBreak"}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"이것이 왜 퀵정렬과 관련이 있는가?"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"우선 퀵정렬의 구현방식을 생각해보자."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"introsort의 두 지점에서 소규모 배열 정렬이 필요하다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"첫째, median-of-3 pivot 선택 단계에서 세 원소를 정렬한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이것이 sort3다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"둘째, 재귀 하단에서 삽입 정렬로 전환할 때, 삽입 정렬 자체가 내부적으로 2~4개 원소를 비교하고 정렬하는 작업을 반복한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"말로 설명하면 어렵지만 간단히 생각하면 학급에서 줄 세우기와 같다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"둘을 비교해서 키가 작으면 앞으로, 키가 크면 뒤로, 이런식으로 반복해서 나누는 것이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"자, 그럼 이걸 우리 인간은 어떻게 표기했을까?"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그리고 그걸 알기 위해서 우리는 어셈블리어에 대해서 조금 알아야한다."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"어셈블리 기초 - 코드를 읽기 전에"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"어셈블리는 CPU가 직접 이해하는 명령어 수준의 언어다. C나 Python처럼 변수나 함수 호출이 없다. 대신 레지스터와 명령어로 동작한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"bold"}],"text":"레지스터"},{"type":"text","text":"는 CPU 안에 있는 작은 임시 저장공간이다. 변수와 비슷하지만 개수가 정해져 있고, 연산은 반드시 레지스터를 거쳐야 한다. x86-64 기준으로 범용 레지스터는 "},{"type":"text","marks":[{"type":"code"}],"text":"rax"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"rbx"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"rcx"},{"type":"text","text":" 등이 있고, 이 글에서는 설명을 단순화하기 위해 "},{"type":"text","marks":[{"type":"code"}],"text":"P"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"Q"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"R"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"S"},{"type":"text","text":"로 표기한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"아래에서 사용하는 명령어는 네 가지다."}]},{"type":"table","content":[{"type":"tableRow","content":[{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"명령어"}]}]},{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"의미"}]}]},{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"예시"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"mov A, B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"B의 값을 A에 복사한다"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"mov R, S"},{"type":"text","text":" → S = R"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmp A, B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"A와 B를 비교해 결과를 플래그에 기록한다. 값 자체는 바뀌지 않는다"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmp P, R"},{"type":"text","text":" → P와 R을 비교"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmovg A, B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"직전 "},{"type":"text","marks":[{"type":"code"}],"text":"cmp"},{"type":"text","text":"에서 A > B였으면 A에 B를 복사한다. 아니면 아무것도 안 한다"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmovg P, R"},{"type":"text","text":" → P > R이면 P = R"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmovl A, B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"직전 "},{"type":"text","marks":[{"type":"code"}],"text":"cmp"},{"type":"text","text":"에서 A < B였으면 A에 B를 복사한다. 아니면 아무것도 안 한다"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmovl R, S"},{"type":"text","text":" → R < S이면 R = S"}]}]}]}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmovg"},{"type":"text","text":"와 "},{"type":"text","marks":[{"type":"code"}],"text":"cmovl"},{"type":"text","text":"은 조건부 이동(conditional move)이다. if문 없이 분기 없는 비교와 선택을 한 줄로 처리한다. 분기 예측 실패(branch misprediction) 비용이 없어서 정렬처럼 비교가 반복되는 코드에서 성능상 유리하다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"cmp"},{"type":"text","text":" 이후 플래그가 어떻게 작동하는지 예를 들면 다음과 같다."}]},{"type":"codeBlock","attrs":{"language":"asm"},"content":[{"type":"text","text":"cmp P, R ; P와 R을 비교, 결과를 플래그에 기록\ncmovg P, R ; P > R이었으면 P = R, 즉 P는 min(P, R)이 된다\ncmovl R, S ; P < R이었으면 R = S, 즉 R은 max(P, R)이 된다"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 두 줄이 하는 일은 결국 "},{"type":"text","marks":[{"type":"code"}],"text":"P = min(A, C)"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"R = max(A, C)"},{"type":"text","text":"를 만드는 것이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 정도면 아래 sort3 코드를 한 줄씩 따라갈 수 있다."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"인간이 짜는 sort3"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"x86 기준으로 3개 원소 "},{"type":"text","marks":[{"type":"code"}],"text":"A"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"B"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"C"},{"type":"text","text":"를 정렬하는 assembly 흐름은 다음과 같다. 레지스터 "},{"type":"text","marks":[{"type":"code"}],"text":"P"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"Q"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"R"},{"type":"text","text":", "},{"type":"text","marks":[{"type":"code"}],"text":"S"},{"type":"text","text":"를 사용한다."}]},{"type":"codeBlock","attrs":{"language":"asm"},"content":[{"type":"text","text":"; 초기 상태: P=A, Q=B, R=C\n\nmov R, S ; S = C (C 보존)\ncmp P, R ; A vs C\ncmovg P, R ; P = min(A, C)\ncmovl R, S ; R = max(A, C)\nmov S, P ; S = min(A, C) <- 핵심 지점\ncmp S, Q ; min(A,C) vs B\ncmovg Q, P ; P = min(A, B, C)\ncmovg S, Q ; S = 중간값"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"mov S P"},{"type":"text","text":"의 역할은 명확하다. 이전 비교에서 "},{"type":"text","marks":[{"type":"code"}],"text":"P"},{"type":"text","text":"에 "},{"type":"text","marks":[{"type":"code"}],"text":"min(A, C)"},{"type":"text","text":"를 담았는데, 다음 비교에서 이 값을 안전하게 쓰기 위해 "},{"type":"text","marks":[{"type":"code"}],"text":"S"},{"type":"text","text":"에 복사해 두는 것이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"인간은 중간 상태를 명시적으로 정리하고 다음 단계로 넘어간다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 습관은 가독성과 검증 용이성을 높이고, 코드를 지역적으로 이해하기 쉽게 만든다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이렇게 보면 이해가 어려우니 예시를 들겠다."}]},{"type":"image","attrs":{"textAlign":null,"src":"/assets-api/uploads/4f1479e09ffc102b.png","alt":null,"title":null}},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","marks":[{"type":"bold"}],"text":"예시: 반 전체를 키 순서로 줄 세운다고 하자. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"선생님이 한 명을 기준(pivot)으로 지목한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"나머지 학생들은 그 기준보다 키가 작으면 왼쪽, 크면 오른쪽으로 이동한다. 한 번의 정렬이 끝나면 기준으로 지목된 학생은 자기 자리가 확정된다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그리고 이제 왼쪽 무리와 오른쪽 무리에서 같은 과정을 반복한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"무리가 한 명이 될 때까지."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"bold"}],"text":"이것이 퀵소트다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"bold"}],"text":"매 단계마다 한 명씩 자리가 확정되고, 나머지는 점점 작은 무리로 쪼개진다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그리고 퀵소트 안에서 "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"선생님이 기준(pivot)을 지목할 때, 후보가 세 명이다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"맨 앞, 가운데, 맨 뒤. 이 세 명 중 중간 키를 가진 학생을 기준으로 삼는다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그러려면 세 명을 먼저 키 순서대로 세워야 한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 세 명을 정렬하는 작업이 sort3다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"선생님은 세 명을 줄 세우고 나서, 그 결과를 칠판에 기록한다. \"가운데 학생이 pivot이다. 그리고 세 명의 순서는 이미 확정되었다.\" 이 기록이 이후 전체 정렬의 전제가 된다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"무리가 줄어들어 세 명 이하가 남으면 다시 sort3가 호출된다. 반 전체를 정렬하는 동안 sort3는 재귀 트리의 거의 모든 단계에서 실행된다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그럼 AI는 어떤가?"}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"AlphaDev가 찾은 코드"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"AlphaDev의 결과는 다음과 같다."}]},{"type":"codeBlock","attrs":{"language":"asm"},"content":[{"type":"text","text":"; 초기 상태: P=A, Q=B, R=C\n\nmov R, S ; S = C\ncmp P, R ; A vs C\ncmovg P, R ; P = min(A, C)\ncmovl R, S ; R = max(A, C)\n; mov S P <- 제거됨\ncmp S, Q ; S = C, B와 비교\ncmovg Q, P ; 조건부 이동\ncmovg S, Q ; 조건부 이동"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"mov S P"},{"type":"text","text":"가 사라졌다. 이 시점에서 "},{"type":"text","marks":[{"type":"code"}],"text":"S"},{"type":"text","text":"는 원래의 "},{"type":"text","marks":[{"type":"code"}],"text":"C"},{"type":"text","text":" 값을 그대로 들고 있다. "},{"type":"text","marks":[{"type":"code"}],"text":"min(A, C)"},{"type":"text","text":"가 아니다. 직관적으로 잘 못되보이고 이해가 어려워보인다."}]},{"type":"image","attrs":{"textAlign":null,"src":"/assets-api/uploads/84a9745ff66c780b.webp","alt":null,"title":null}},{"type":"paragraph","attrs":{"textAlign":"center"},"content":[{"type":"text","text":"(원본 논문에 나온 코드와 이미지)"}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"왜 제거해도 되는가?"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 코드는 독립 실행 코드가 아니다. sorting network 안의 부분 코드다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"sorting network는 비교기(comparator)를 고정된 순서로 연결해 정렬을 수행하는 구조다. 각 비교기는 두 입력을 받아 "},{"type":"text","marks":[{"type":"code"}],"text":"min"},{"type":"text","text":"과 "},{"type":"text","marks":[{"type":"code"}],"text":"max"},{"type":"text","text":"를 출력한다. 중요한 점은 앞선 비교기의 출력이 뒤 비교기의 입력 조건을 제약한다는 것이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"AlphaDev의 코드 조각이 실행되는 시점에는 앞선 비교기가 이미 "},{"type":"text","marks":[{"type":"code"}],"text":"B ≤ C"},{"type":"text","text":"를 보장해 놓은 상태다. 이 전제가 있으면 분석이 달라진다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"code"}],"text":"mov S P"},{"type":"text","text":"를 제거한 상태에서 "},{"type":"text","marks":[{"type":"code"}],"text":"S = C"},{"type":"text","text":"다. "},{"type":"text","marks":[{"type":"code"}],"text":"B ≤ C"},{"type":"text","text":"가 성립하므로 "},{"type":"text","marks":[{"type":"code"}],"text":"cmp S Q"},{"type":"text","text":", 즉 "},{"type":"text","marks":[{"type":"code"}],"text":"C"},{"type":"text","text":"와 "},{"type":"text","marks":[{"type":"code"}],"text":"B"},{"type":"text","text":"의 비교 결과는 이미 방향이 정해져 있다. 이 조건 아래에서 이후 "},{"type":"text","marks":[{"type":"code"}],"text":"cmovg"},{"type":"text","text":" 두 개가 만드는 최종 출력 3개는 "},{"type":"text","marks":[{"type":"code"}],"text":"mov S P"},{"type":"text","text":"가 있을 때와 동일한 정렬 결과를 형성한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"단계별 레지스터 상태를 추적하면 다음과 같다."}]},{"type":"table","content":[{"type":"tableRow","content":[{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"단계"}]}]},{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"P"}]}]},{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"Q"}]}]},{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"R"}]}]},{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"S"}]}]},{"type":"tableHeader","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"전제"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"초기"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"A"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"-"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"B ≤ C"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"mov R, S"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"A"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"cmovg P, R"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"min(A,C)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"cmovl R, S"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"min(A,C)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"max(A,C)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"cmp S, Q (S=C, Q=B)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C ≥ B 이미 성립"}]}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"cmovg Q, P"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"min(A,C,B)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"B"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"max(A,C)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"C"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]}]},{"type":"tableRow","content":[{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"cmovg S, Q"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"min(A,C,B)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"중간값"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"max(A,C)"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"중간값"}]}]},{"type":"tableCell","attrs":{"colspan":1,"rowspan":1,"colwidth":null},"content":[{"type":"paragraph","attrs":{"textAlign":null}}]}]}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"로컬 코드만 보면 틀린 것처럼 보이지만, 전체 네트워크의 불변식을 포함하면 맞다. Nature 논문은 이 구조를 AlphaDev swap move라고 명명한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이걸 앞 선 학급 비유로하면 어떻게 이해해야할까?"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","marks":[{"type":"bold"}],"text":"이번엔 세 명만 줄을 세운다. A, B, C."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"인간은 이렇게 한다. A와 C를 먼저 비교해 순서를 잡고, 그 결과를 칠판에 메모한다. \"지금 앞에 선 애가 min(A,C)다.\" "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그 메모를 보고 B와 비교해 최종 순서를 완성한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"중간 결과를 반드시 적어두고 넘어간다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그런데 이 반에서는 수업 시작 전에 이미 B와 C의 키를 재서 \"B가 C보다 작다\"는 사실이 칠판에 적혀 있다. 이 사실을 알고 있는 교사라면 굳이 칠판에 메모할 필요가 없다. A와 C를 비교한 직후, 칠판의 그 사실을 전제로 삼아 바로 다음 비교로 넘어갈 수 있다. 최종 줄 세우기 결과는 동일하다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"AlphaDev가 제거한 한 줄은 그 칠판 메모다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"인간은 다음 단계가 무엇을 전제하는지 따지지 않고 습관적으로 중간 상태를 적어두지만, AlphaDev는 칠판에 이미 적힌 사실, 즉 앞 단계가 확보한 불변식을 전제로 삼아 그 메모 자체를 없앴다."}]},{"type":"image","attrs":{"textAlign":null,"src":"/assets-api/uploads/821fa6582516c036.jpg","alt":null,"title":null}},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"Nature 논문은 이 루틴들이 매일 수조 번(trillions of times) 실행된다고 적고 있다. 과장이 아니다. 전 세계 서버에서 실행되는 C++ 프로그램, 데이터베이스 엔진, 네트워크 스택, 파일 시스템이 모두 "},{"type":"text","marks":[{"type":"code"}],"text":"std::sort"},{"type":"text","text":"를 호출한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"즉, "},{"type":"text","marks":[{"type":"code"}],"text":"std::sort"},{"type":"text","text":"를 호출할 때마다 sort3는 재귀 트리의 거의 모든 내부 노드에서 실행된다. n개 원소를 정렬하면 재귀 트리의 내부 노드 수는 O(n)이고, 각 노드에서 sort3가 호출되므로 전체 정렬 과정에서 sort3의 실행 횟수도 O(n)에 비례한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그렇다면 정말 몇 조번이 실행되고 있다는 것이 과장이 아니었을 것이다."}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"왜 인간은 이걸 못 찾았나"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"인간은 코드를 지역적으로 검증한다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"\"하지 않은 비교를 하고 넘어가야, 다음 비교가 안전하다\" "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"“중간 상태를 한 번 명확히 정리하고 넘어가야 한다”는 식으로 사고한다."},{"type":"hardBreak"}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 습관은 가독성과 검증 용이성을 높이고, 코드를 지역적으로 이해하기 쉽게 만든다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"AlphaDev는 그 제약이 없다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"레지스터 상태 전이 전체를 탐색 공간으로 보고, 최종 출력 3개가 정렬 상태를 만족하는지만 판단한다. 각 어셈블리 명령을 하나의 행동(action)으로 보고, 정렬 정확성과 명령 수를 보상(reward)으로 설계한 강화학습 구조가 이 탐색을 가능하게 했다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"전체 알고리즘이 보장하는 불변식을 이용해 로컬 정리용 복사를 제거하는 것은, 그 탐색 과정에서 자연스럽게 발견될 수 있는 수순이었다. 인간이 수십 년간 당연하게 두었던 한 줄이 사라진 이유는 결국 탐색 단위의 차이에 있다."}]},{"type":"image","attrs":{"textAlign":null,"src":"/assets-api/uploads/96e971297a920045.webp","alt":null,"title":null}},{"type":"paragraph","attrs":{"textAlign":"center"},"content":[{"type":"text","text":"(콜럼버스의 달걀)"}]},{"type":"heading","attrs":{"textAlign":null,"level":2},"content":[{"type":"text","text":"마치며..."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이 발견의 핵심은 AI가 인간보다 더 우월하다는 데 있지 않다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"중요한 것은 탐색 단위의 차이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"인간은 코드를 지역적으로 이해하고, 중간 상태를 정리하며, 각 단계를 안전하게 검증하는 방식으로 사고한다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"반면 AlphaDev는 전체 상태 공간을 대상으로, 최종 출력이 조건을 만족하는지와 명령 수가 최소화되는지만 본다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그 차이 때문에 인간이 수십 년간 당연하게 유지해온 한 줄이 사라졌다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"즉 우리가 ‘당연하다’고 믿는 코드 패턴 중 일부는 문제의 본질이라기보다, 인간이 이해하고 검증하기 쉬운 형태에 맞추어 굳어진 습관일 수 있다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"AlphaDev는 그 사실을 작은 예제로 증명했다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이것은 콜럼버스의 달걀과 비슷하다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"정답을 본 뒤에는 누구나 단순하다고 말할 수 있다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"하지만 진짜 어려운 것은, 아무도 의심하지 않던 전제를 처음으로 깨는 일이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"AlphaDev가 보여준 것은 더 나은 손기술이 아니라, 인간이 당연하게 여긴 구조를 다른 탐색 방식으로 다시 볼 수 있다는 가능성이다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"이제 인간의 인지적 습관만이 아니라, AI라는 새로운 탐색 도구도 갖게 되었다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"그것을 인간과 같은 의미의 지능이라고 부를지는 내 개인적으로는 망설여진다. "}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"하지만 우리가 너무도 당연하게 여겨 온 것들이 이런 방식으로 하나씩 깨져 나간다는 사실은, 분명 지적인 흥분을 준다."}]},{"type":"paragraph","attrs":{"textAlign":null},"content":[{"type":"text","text":"참고문헌:Mankowitz, D. J., Michi, A., Zhernov, A., Gelmi, M., Selvi, M., Paduraru, C., Leurent, E., Iqbal, S., Lespiau, J.-B., Ahern, A., Köppe, T., Millikin, K., Gaffney, S., Elster, S., Broshear, J., Tsing, A., Polosukhin, I., Pikhtin, A., Sifre, L., Singh, S., … Silver, D. (2023). "},{"type":"text","marks":[{"type":"italic"}],"text":"Faster sorting algorithms discovered using deep reinforcement learning"},{"type":"text","text":". "},{"type":"text","marks":[{"type":"italic"}],"text":"Nature, 618"},{"type":"text","text":"(7964), 257–263. "},{"type":"text","marks":[{"type":"link","attrs":{"href":"https://doi.org/10.1038/s41586-023-06004-9","target":"_blank","rel":"noopener noreferrer nofollow","class":"text-emerald-600 underline underline-offset-2"}}],"text":"https://doi.org/10.1038/s41586-023-06004-9"}]}]}