백준 24267번 : 알고리즘 수업을 통해 보는 삼중 시그마의 이해

반복문 한 줄에서 시작하여, 그 안에 담긴 수학적, 기하학적 원리들이 어떻게 서로 얽혀 있는지를 깊이 있게 서술한다. 여기서는 1부터 $n$까지의 정수 중 서로 다른 세 개의 수 $i$, $j$, $k$를 선택하는 삼중 반복문의 예제를 들어 설명한다.

for i in range(1, n-1):
    for j in range(i+1, n):
        for k in range(j+1, n+1):
            print(i, j, k)

이 코드의 구조는 단순해 보이지만, 사실 이는 $i < j < k$인 모든 경우의 수를 열거하는 과정이며, 이는 $n$개의 원소 중에서 순서를 고려하지 않고 3개를 선택하는 조합, 즉 이항 계수 $\binom{n}{3}$의 결과와 정확히 일치한다. 이항 계수는 다음과 같이 정의된다.

$$
\binom{n}{3} = \frac{n(n-1)(n-2)}{6}.
$$

여기서 단순한 산술 계산 이상의 의미가 드러난다. 반복문이 구현하는 모든 선택의 경우의 수는, 우리가 수학에서 다루는 조합의 본질을 그대로 반영한다. 반복문 속에 내재한 이러한 구조는 우리가 코드 한 줄을 볼 때, 단순한 순회 이상의 깊은 원리를 느낄 수 있게 한다.

이와 같은 조합의 원리는 파스칼 삼각형에서 더욱 명확하게 나타난다. 파스칼 삼각형은 각 항이 바로 위의 두 항의 합으로 구성되는 배열로, 각 숫자는 $\binom{n}{r}$의 값을 나타낸다. 예를 들어, 다음과 같은 배열을 생각해 보자.

           1
         1   1
       1   2   1
     1   3   3   1
  1   4    6   4   1
1   5   10  10   5   1

이 배열은 단순한 덧셈의 반복으로 만들어지며, 이는 코드에서 반복문이 수행하는 누적 합의 원리와 동일하다. 삼중 반복문에서 한 값 $i$가 정해지면, 그 다음에 등장하는 $j$와 $k$의 조합은 이중 반복문으로 $\binom{n-i}{2}$를 산출하는 과정과 같다. 이처럼 파스칼 삼각형은 단순한 수학적 도구가 아니라, 코드의 반복적 구조와 자연스럽게 연결되어 모든 선택의 경우를 한눈에 보여 주는 창과 같다.

 

 

또한, 파스칼 삼각형 속에는 “하키스틱 규칙”이라 불리는 특별한 성질이 있다. 이 규칙은 파스칼 삼각형에서 한쪽 대각선을 따라 이어진 항들을 모두 더하면, 그 누적 합이 바로 그 아래쪽에 위치한 항과 같아지는 원리를 나타낸다. 수식으로 표현하면 다음과 같다.

 

$$
\sum_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1}.
$$

이 항등식은 우리가 반복문에서 각 단계마다 누적되는 값을 생각할 때, 그 결과가 새로운 조합 값으로 자연스럽게 연결되는 과정을 설명해준다. 코드에서 각 반복의 결과들이 서로 더해져 하나의 최종 값을 도출하는 모습은, 이 하키스틱 규칙이 보여주는 누적 합의 원리와 닮아 있다.

 

 

더 나아가, 조합은 본질적으로 대칭성을 지닌다. 예를 들어, 아래와 같은 항등식은 조합의 대칭적 성질을 여실히 드러낸다.

$$
\binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \cdots + \binom{n}{n}\binom{n}{0}.
$$

이 식은 파스칼 삼각형의 좌우 대칭을 그대로 반영하며, 반복문을 통한 조합 계산 속 구조를 보여준다.

반복문과 조합의 관계를 단순한 산술 계산 이상의 것으로 이해하기 위해서는, 이 모든 개념들을 기하학적으로도 해석할 필요가 있다. 이중 반복문을 통해 선택된 $(i, j)$의 조합은, 2차원 평면상의 격자에서 한쪽 삼각형 모양을 형성하는 데, 그 전체 경우의 수는 $\binom{n}{2}$와 같다. 이 삼각형은 평면상의 영역과 같이, 모든 가능한 쌍을 시각적으로 보여준다.

 

 

반면, 삼중 반복문을 통해 선택된 $(i, j, k)$의 조합은 3차원 공간에서 정사면체(테트라헤드론)의 꼭짓점을 이루며, 이 때의 경우의 수는 $\binom{n}{3}$로 표현된다. 정사면체는 3차원에서 가장 단순한 다면체로서, 그 꼭짓점들이 서로 유기적으로 연결되어 있는 방식은 단순한 조합 수식이 아니라, 기하학적 구조로서의 아름다움을 드러낸다.

 

 

직접 코드를 작성하여 실행해 보고, 작은 $n$의 값으로 $(i, j, k)$ 조합이 어떻게 출력되는지 눈으로 확인하면, 그 총 경우의 수가 $\binom{n}{3}$임을 자연스럽게 깨달을 수 있다. 또한, 종이나 디지털 도구를 사용해 파스칼 삼각형을 직접 그려보고, 그 속에 담긴 누적과 대칭의 원리를 이해하는 과정은, 코드 한 줄에 담긴 수학적 선택의 깊이를 체험하게 해준다. 3차원 공간에서 $(i, j, k)$ 조합을 시각화하는 작업은, 단순한 산술 계산을 넘어 기하학적 정사면체의 아름다움을 직접 눈으로 확인하게 해 주며, 이 모든 개념들이 하나의 통일된 세계를 이루고 있음을 분명히 보여준다.

 

 

결과적으로, 반복문은 단순히 코드를 반복하는 도구가 아니라, 그 자체로 수학적 조합의 원리와 기하학적 구조를 구현하는 매개체이다. 이중 반복문은 2차원에서 삼각형을 이루며 $\binom{n}{2}$로 나타나고, 삼중 반복문은 3차원에서 정사면체를 이루며 $\binom{n}{3}$로 표현된다. 파스칼 삼각형은 이러한 모든 조합 계산의 시각적, 구조적 기반을 제공하며, 하키스틱 규칙은 누적 합의 과정을 통해 새로운 조합 값을 만들어내는 원리를 설명한다. 더불어, 조합의 대칭성을 보여주는 항등식들은 코드와 수식, 그리고 기하학적 구조가 서로 유기적으로 연결되어 있음을 확인시켜 준다.