Computational Thinking

컴퓨터의 입장에서 생각하기

Computational Thinking을 한마디로 정의하자면 컴퓨터 입장에서 생각하기다. 컴퓨터의 도움이 필요한 문제들이 있다. 수작업으로 다루기 힘든 어마어마한 규모의 자료가 필요한 문제이거나, 어떤 소프트웨어에 존재하는 버그를 해결해야 하는 상황일 수도 있다. 어떤 상황이 됐든 간에 컴퓨터를 이용해 문제를 해결해야 하는 상황에서는 컴퓨터, 그리고 그 컴퓨터에서 돌아가는 프로그램을 생각해야 한다. 그리고 주어진 문제를 해결할 답을 구현할 최적의 하드웨어와 소프트웨어에 대해 고민해야 한다.

무엇을 다루는가

Computational Thinking을 구성하는 인지 활동은 보통 네 개의 기둥으로 정리된다. 네 기둥은 순차 단계가 아니라, 문제를 다룰 때 번갈아 동원되는 분석 도구다.

분해Decomposition

복잡한 문제를 더 작은 하위 문제들로 쪼갠다. 각 하위 문제는 독립적으로 이해하고 해결할 수 있을 만큼 작아야 한다. 학생 명단을 성적 순으로 보고서로 출력하는 문제는 입력 읽기, 정렬, 포맷팅, 출력의 네가지 하위 문제로 분해된다.

패턴 인식Pattern Recognition

분해된 하위 문제들 사이에서 반복되는 구조를 찾는다. 같은 연산이 여러 데이터에 적용되거나, 과거에 본 문제와 같은 꼴로 환원된다면 기존 해법을 재사용할 수 있다. 성적 정렬은 "키로 비교 가능한 레코드를 순서화"라는 패턴이고, 이는 일반적인 정렬 알고리즘으로 해결된다.

추상화Abstraction¹

문제를 푸는 데 필요 없는 세부를 제거하고, 본질적인 속성만 남긴다. 학생의 키나 주소는 성적 정렬과 무관하므로 생략하고, (이름, 점수) 쌍으로 추상화한다. 추상화는 어떤 자료구조를 고를 것인가와 동전의 양면이다.

알고리즘 설계Algorithm Design²

추상화된 입력을 추상화된 출력으로 변환하는 유한한 단계들의 나열을 작성한다. 각 단계는 모호하지 않고, 종료되며, 기계적으로 실행 가능해야 한다.

어떻게 실행하는가

어떤 문제가 주어졌을 때, Computational Thinking을 통해 문제를 해결하는 과정은 크게 세 단계로 나뉜다.

추상화

이전 섹션의 추상화와 이름은 같지만 층위가 다르다. 여기서 문제는 "컴퓨터가 다룰 수 있는 형태로 모델링하는 행위 전체"를 가리킨다. 자료구조를 고르고, 입출력 명세를 정의하고, 불필요한 맥락을 떼어내는 작업이 모두 이 단계에 속한다.

자동화Automation

추상화된 모델 위에서 알고리즘을 설계하고 구현한다. 컴퓨터가 반복적으로 실행하면 자동으로 답이 나오도록 만드는 단계다.

분석Analysis

구현을 실행해 보고, 정확성·시간 복잡도·공간 복잡도를 평가한다. 이 단계에서 얻은 통찰은 추상화와 자동화로 되돌아가 개선의 근거가 된다. 세 단계는 일방향이 아니라, 분석이 다시 추상화를 흔드는 반복되는 과정이다.

두 프레임의 관계

점수 분류하기

학생 100명의 점수를 받아, 평균 이상인 그룹과 미만인 그룹으로 나누어라.

이 문제를 4기둥으로 분석한 뒤, 같은 풀이를 3단계로 재조명해 두 프레임이 어떻게 맞물리는지 확인한다.

4기둥으로 분석하기

분해

문제를 세 하위 문제로 나눈다.

• 평균을 구한다.
• 각 점수를 평균과 비교한다.
• 비교 결과에 따라 두 그룹에 배분한다.

패턴 인식

평균을 구하는 문제는 "리스트의 모든 원소를 더한다"는 반복 패턴이고, 나머지는 "리스트의 모든 원소에 같은 조건을 적용한다"는 반복 패턴이다. 두 패턴 모두 단일 순회로 해결된다.

추상화

학생의 이름·학번·반 같은 속성은 이 문제와 무관하다. 입력을 점수만 담은 리스트 $X = [x_1, x_2, \dots, x_n]$으로 추상화하고, 출력을 두 리스트 $(A, B)$로 정의한다.

알고리즘 설계

평균 $\bar{x}$와 분류 규칙을 수식으로 먼저 쓴다.

$\bar{x} = \frac{1}{n} \sum_{i=1}^{n} x_i$

$A = \{\, x_i \mid x_i \geq \bar{x} \,\}, \quad B = \{\, x_i \mid x_i < \bar{x} \,\}$

이를 의사 코드로 옮기면 다음과 같다.

function classify(scores):
    total ← 0
    for s in scores:
        total ← total + s
    avg ← total / length(scores)

    above ← []
    below ← []
    for s in scores:
        if s ≥ avg:
            append(above, s)
        else:
            append(below, s)
    return (above, below)

검토하기

추상화

입력을 List<int>, 출력을 (List<int>, List<int>)로 정했다. 학생의 다른 속성은 모두 버렸다. 이 선택 덕분에 classify는 "점수 리스트를 두 리스트로 분할하는 함수"라는 단순한 계약만 갖게 된다.

자동화

두 번의 선형 순회로 자동화했다. 첫 순회로 평균을 구하고, 두 번째 순회로 분류한다. 평균은 모든 원소를 본 뒤에만 확정되기 때문에 한 번의 순회로는 분류할 수 없다는 제약이 여기서 명확해진다.

분석

시간 복잡도는 두 번의 선형 순회로 $O(n)$이다³. 공간 복잡도는 출력 두 리스트를 포함해 최악의 경우 $O(n)$. $n = 100$처럼 작은 입력에서는 어떤 비효율적 알고리즘을 써도 체감되지 않지만, $n$이 $10^9$ 규모라면 "리스트를 두 번 순회"하는 비용과 메모리 접근 패턴이 본격적으로 문제가 된다. 스트리밍 환경이라면 평균을 온라인으로 추정하거나, 중앙값 같은 분위수를 대체 기준으로 삼을 수 있다.

관련 포스트

• 알고리즘
• 자료구조
• 시간 복잡도

---

출처

• Aho, Alfred V. "Computation and Computational Thinking." The Computer Journal 55.7 (2012): 832–835.
• https://en.wikipedia.org/wiki/Computational_thinking
• https://www.bbc.co.uk/bitesize/guides/zp92mp3/revision/1

Footnotes

1. Abstraction(추상화)은 문제 해결에 불필요한 세부를 제거하고 본질적인 구조만 남기는 행위다. 자료구조 수준에서는 데이터의 표현을, 알고리즘 수준에서는 연산의 인터페이스를 단순화한다. ↩

2. 알고리즘은 유한 시간 안에 종료되고, 각 단계가 모호하지 않으며 기계적으로 실행 가능하고, 명확한 입력과 출력을 갖는 단계들의 나열이다(Knuth, The Art of Computer Programming, Vol. 1, §1.1의 Finiteness·Definiteness·Input·Output·Effectiveness 다섯 성질). ↩

3. Big-O 표기법은 입력 크기 $n$에 대한 연산 횟수의 상한 증가율을 나타낸다. $O(n)$은 연산 횟수가 $n$에 선형으로 비례함을, $O(\log n)$은 로그 스케일로 증가함을 의미한다. ↩