[B급 프로그래머] (Quora) 10분만에 알고리즘 사고를 기르는 방법

Quora에 재미있는 질문이 하나 올라와서 독자 여러분을 위해 정리해보았다.

What can I learn right now in just 10 minutes that could improve my algorithmic thinking?

한국어로 번역하자면 '10분만에 알고리즘 사고를 기를 수 있는 방법은 무엇인가요?'이며, 가장 멋진 대답을 정리하면 다음과 같다.

이미 알고 있는 지식이 어느 수준인지 모르는 상태에서 대답하기는 어렵습니다. 한 가지만 힌트를 드리자면, 루프 불변입니다. 루프를 작성할 때, 암시적이거나 명시적으로 루프 불변을 사용한다는 사실을 이해해야 합니다.

루브 불변은 술부(predicate, 참 또는 거짓인 서술)이며, 다음과 같은 속성이 있습니다.

1. 처음 루프에 진입할 때 참이다.
2. 루프 반복을 시작할 때 참이면, 다음 반복을 시작할 때도 참이다.
3. 루프가 종료되면, 루프 불변은 루프가 원하는 속성을 제공하는 근거를 제시한다.

간단한 예를 들어봅시다. 배열 a의 첫 n개(양수)를 더하기 위해 다음 루프를 만들어봅시다.

Read Quote of Thomas Cormen's answer to What can I learn right now in just 10 minutes that could improve my algorithmic thinking? on Quora

바로 루프 불변 예제입니다. 루프 반복에 들어갈 때, sum = a[0] + a[1] + a[2] + ... + a[i - 1]을 계산합니다. 위에서 설명한 세 가지 속성이 충족하는지 살펴봅시다.

1. 처음 반복할 때 i = 0입니다. i - 1 = -1이므로, a[0] + a[1] + a[2] + a[i - 1]은 비어 있습니다. 아무 항도 더하지 않았으므로 0이 됩니다.
2. i의 값에 대해 반복에 들어갈 때, 루브 불변이 참이라고 가정하면 sum = a[0] + a[1] + a[2] + ... + a[i - 1]이 됩니다. 반복 과정에서 a[i]을 sum에 더하고, i를 하나 증가시킵니다. 따라서 루프 불변은 다음 반복에 들어갈 때도 계속해서 유지됩니다.
3. i=n이 되면 루프가 종료됩니다. 루프 불변에 따르면 sum = a[0] + a[1] + a[2] + ... + a[i - 1]입니다. 따라서 sum은 배열의 첫 n개의 합입니다.

예제가 정말로 사소할지 모르겠습니다. 이런 루프를 작성했다면, 정형적인 방식으로 사유했다고 보기는 어려울지도 모릅니다. 하지만 인지하든 인지하지 못하든 마음 속에서는 정확하게 위에서 설명한 방식에 맞춰 사고가 일어납니다. 루프 불변은 훨씬 복잡한 루프를 이해하고 올바르게 증명하는 과정에 도움을 줍니다.

루프 불변이 수학적인 귀납법을 떠올리게 했다면, 당연합니다. 첫째 속성은 귀납의 기초를, 둘째 속성은 귀납적인 추측과 유사합니다. 셋째 속성이 조금 다른 이유는 대다수 귀납적인 증명에는 종결 조건이 없기 때문입니다.

어찌되었거나, 10분만에 배울 수 있는 뭔가를 질문했습니다. 루프 불변은 10분만에 배울 수 있는 최선의 개념입니다. 재귀를 말하고 싶었으나, 초급 과정에서 재귀를 가르친 23년 동안의 경험에 따르면, 설명에 10분 넘게 걸립니다.

EOB