알고리즘

데이터로 답을 어떻게 낼지를 다루는 구역입니다. 같은 답에 이르는 절차가 여럿이고, 무엇을 고르느냐로 걸리는 시간과 메모리가 갈립니다. 그래서 이 구역에서는 절차를 짜는 방법과 그 절차의 비용을 재는 법을 함께 다룹니다. 이 구역 안에 무엇이 있느냐는 물음의 답은 한 문장이 아니라 목록으로 열립니다.

쉽고 빠른 이해

답을 내는 절차를 짜고 그 값을 재는 구역입니다. 회원 백만 명에서 아이디 하나를 찾을 때 처음부터 훑을지, 반씩 잘라 들어갈지가 여기서 갈립니다.

절차를 안 고르면 데이터가 늘어날 때 무엇이 먼저 무너지는지 모릅니다. 백 건에서 잘 돌던 코드가 백만 건에서 멈추는 일이 그래서 생깁니다.

무엇을 하나:

풀 문제를 입력과 답으로 또렷하게 적습니다
답에 이르는 단계를 정하고, 그 단계가 어떤 모양의 데이터 위에서 도는지 맞춥니다
입력이 커질 때 시간과 메모리가 어떻게 늘어나는지 잽니다

대가도 있습니다. 시간을 줄이려면 대개 메모리를 더 씁니다. 계산해 둔 답을 쌓아 두고 다시 쓰는 절차가 그렇습니다.

상세

이 구역의 물음은 하나입니다. 가진 데이터로 답을 어떻게 낼지입니다.

NIST(National Institute of Standards and Technology, 미국 국립표준기술연구소)가 유지하는 알고리즘·자료구조 사전은 알고리즘을 원하는 결과에 이르는 계산 가능한 단계의 집합이라고 정의합니다. 여기서 절차는 코드가 아닙니다. 어떤 언어로 적든 같은 단계를 밟으면 같은 절차입니다.

학부 컴퓨터과학 학위 과정 교육과정 지침인 Computer Science Curricula 2013 이 그 점을 못 박아 둡니다. 어떤 소프트웨어 시스템의 실세계 성능이든 고른 알고리즘과 구현의 여러 레이어가 가진 적합성·효율에 달려 있다고 적습니다. 그리고 알고리즘 연구가 문제의 본질과 가능한 해법 기법에 대한 통찰을 준다고 적습니다. 그 통찰이 프로그래밍 언어나 프로그래밍 패러다임, 컴퓨터 하드웨어, 그 밖의 어떤 구현 측면과도 무관하다고 적습니다.

절차는 허공에서 돌지 않습니다. 이웃 구역인 자료구조는 데이터를 어떤 모양으로 담을지를 다룹니다. 앞의 사전은 대부분의 자료구조가 탐색·삽입·균형 맞추기 같은 연산을 수행하는 절차를 딸려 가진다고 덧붙입니다. 그 절차가 자료구조의 성질을 유지한다고 적습니다. 반대 방향도 같습니다. 앞의 지침은 트리의 균형이 여러 이진 탐색 트리 연산의 효율에 어떻게 영향을 주는지 설명하는 것을 학습 성과로 적습니다. 담는 모양을 바꾸면 그 위에서 도는 절차의 비용이 달라집니다.

flowchart TD
    A[풀 문제를 입력과 답으로 적는다] --> B[데이터를 담을 모양을 고른다]
    B --> C[그 모양 위에서 도는 절차를 짠다]
    C --> D[최악과 평균의 비용이 갈린다]

같은 지침은 학부 교육과정의 지식 본체를 18개 지식영역으로 나눕니다. 그중 하나가 알고리즘과 복잡도입니다. 그 지식영역은 다시 네 단위로 갈립니다. 기본 분석, 알고리즘 전략, 기본 자료구조와 알고리즘, 그리고 기본 오토마타·계산가능성·복잡도입니다.

이 구역의 공통 언어는 비용을 재는 자입니다. 앞의 사전은 빅오 표기법을 알고리즘 실행에 대한 이론적 척도라고 정의합니다. 문제 크기 n 이 주어졌을 때 대개 필요한 시간이나 메모리를 잰다고 적습니다. n 은 대개 항목의 개수라고 덧붙입니다.

기본 분석 단위의 토픽 목록도 같은 자를 적습니다. 최선과 기대와 최악 동작의 차이, 상한과 기대 복잡도 경계의 점근 분석, 빅오 표기법의 형식 정의가 거기 있습니다. 상수·로그·선형· 이차·지수 같은 복잡도 클래스, 성능의 경험적 측정, 알고리즘에서의 시간과 공간 맞바꿈도 같은 목록에 있습니다.

경계

운영체제가 쓰는 교체 절차나 그래픽스의 그리기 절차도 이 구역인가. 아닙니다. 어느 구역에서 만나든 모양이 같은 일반적인 절차만 이 구역이 담고, 한 구역에서만 뜻이 서는 절차는 그 구역이 가져갑니다.

근거는 이 분야의 사전이 스스로 그어 둔 선입니다. 앞의 NIST 사전은 자기를 알고리즘과 알고리즘 기법, 자료구조, 전형적 문제와 관련 정의를 담은 사전이라고 적습니다. 그리고 담지 않는 것도 적습니다. 업무 데이터 처리·통신·운영체제·분산 알고리즘·프로그래밍 언어·인공지능·그래픽스· 수치해석에 고유한 알고리즘은 현재 담지 않는다고 적습니다. 일반적인 알고리즘과 자료구조를 다루는 것만으로도 벅차다는 이유를 답니다.

교육과정 지침 쪽도 같은 선을 긋습니다. Computer Science Curricula 2013 은 알고리즘과 복잡도를 18개 지식영역 가운데 한 칸으로 세우고, 운영체제와 그래픽스와 정보 관리를 각각 다른 칸으로 세웁니다. 같은 지침의 또 다른 지식영역은 자기 토픽이 정보 관리와 알고리즘과 복잡도 두 칸에서 자세히 다뤄진다고 적으며 두 칸을 나란히 가리킵니다.

가르는 선은 절차의 난이도가 아니라 절차가 기대는 것입니다. 다익스트라 알고리즘은 가중치가 붙은 그래프 하나만 있으면 성립합니다. 교체 절차는 페이지와 메모리 계층이 있어야 말이 됩니다.

이견

이 구역을 어떻게 나누고 그 안의 것을 무엇이라 부르는지가 문서마다 갈립니다.

구역을 나누는 축이 첫 갈림입니다. Computer Science Curricula 2013 은 알고리즘과 복잡도를 18개 지식영역 가운데 한 칸으로 세웁니다. 배열·연결 리스트·스택·큐 같은 기초 자료구조는 소프트웨어 개발 기초라는 다른 칸에 둡니다. 그런데 알고리즘과 복잡도 안에는 기본 자료구조와 알고리즘이라는 단위를 둡니다. 그 단위가 둘을 다시 한데 묶습니다. 앞의 NIST 사전은 그런 칸을 두지 않습니다. 알고리즘과 알고리즘 기법과 자료구조와 전형적 문제를 처음부터 한 사전 안에 함께 담는다고 적습니다. 두 문서 모두 어느 쪽이 맞다고는 적지 않습니다.

절차를 부르는 딱지도 갈립니다. NIST 사전은 동적 계획법·그리디 알고리즘·분할 정복에 알고리즘이 아니라 알고리즘 기법이라는 딱지를 답니다. 같은 이름들을 Computer Science Curricula 2013 은 알고리즘 전략이라는 단위로 묶습니다. 이름을 붙이는 쪽과 묶는 쪽이 갈린 셈입니다.

절차가 아닌 것이 이 구역에 드는지도 갈립니다. NIST 사전은 외판원 순회와 정지 문제에 전형적 문제라는 딱지를 답니다. 단계의 집합이 아니라 그 단계가 풀어야 할 문제인데도 같은 사전이 함께 담습니다. Computer Science Curricula 2013 은 그 둘을 기본 오토마타·계산가능성· 복잡도 단위 안에 두어 알고리즘과 복잡도 칸 안에 들입니다.

상세

경계

이견

관련 항목

답을 내는 절차

답을 짜는 전략

절차가 딛고 서는 담는 모양

해시테이블 위에서 도는 절차

절차의 값을 재는 지표

못 넘는 선과 어려운 문제

이 구역이 자기 밖으로 민 이웃 구역

이 구역을 정의하거나 나눈 문서