반복문 한 줄에서 시작하여, 그 안에 담긴 수학적, 기하학적 원리들이 어떻게 서로 얽혀 있는지를 깊이 있게 서술한다. 여기서는 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}$로 표현된다. 파스칼 삼각형은 이러한 모든 조합 계산의 시각적, 구조적 기반을 제공하며, 하키스틱 규칙은 누적 합의 과정을 통해 새로운 조합 값을 만들어내는 원리를 설명한다. 더불어, 조합의 대칭성을 보여주는 항등식들은 코드와 수식, 그리고 기하학적 구조가 서로 유기적으로 연결되어 있음을 확인시켜 준다.

우리는 일상에서 "독립"이라는 말을 들으면 스스로 결정하며 타인이나 외부의 영향에 의존하지 않는 상태를 떠올린다. 예를 들어, "그 사람은 독립적이다"라는 말은 그 사람이 자신의 삶이나 결정을 스스로 해나가는 모습을 의미한다. 그러나 확률론에서 "독립"은 사뭇 다른 느낌을 준다. 확률론에서 두 사건 $A$와 $B$가 독립이라는 것은, 한 사건의 발생 여부가 다른 사건의 발생 확률에 전혀 영향을 주지 않는 상태이다. 이는 "정보가 추가되지 않는다"는 의미로 엄밀히 정의되며, 수식으로는

$$
P(A \cap B) = P(A) \cdot P(B)
$$

로 나타난다. 이 정의는 정보이론적 관점에서 상호정보 (Mutual Information)가 $0$임과 동치이다. 즉, $A$와 $B$ 사이에는 서로에 대해 공유하는 추가적인 정보가 전혀 없다는 것을 의미한다.


1. 교집합과 독립의 관계

1.1 교집합의 정의

교집합은 두 사건이 동시에 발생하는 경우를 의미한다. 예를 들어, 공정한 동전 두 개를 던졌을 때

  • 첫 번째 동전이 앞면이다.
  • 두 번째 동전도 앞면이다.

이 두 사건이 동시에 일어나는 경우는 $A \cap B$에 해당하며, 독립적인 동전 던지기에서는

$$
P(A \cap B)=0.5 \times 0.5=0.25
$$

이다. 여기서 "교집합"은 단순히 "동시에 발생하는 사건"을 나타내며, 독립 사건이라 하더라도 교집합의 확률은 양의 값을 가진다. 중요한 점은, 독립이라는 것은 한 사건이 발생한 사실이 다른 사건의 확률을 변화시키지 않는다는 것인데, 이때 두 사건이 동시에 일어날 확률이 그 각각의 확률의 곱으로 나타난다는 것이다. 정보이론에서는, 첫 번째 동전의 결과가 두 번째 동전의 결과에 대해 전혀 새로운 정보를 주지 않으므로, 두 사건 사이의 상호정보가 $0$이다.


2. 배반사건(서로 배타적 사건)과 독립의 차이

2.1 배반사건의 정의

배반사건은 두 사건이 동시에 발생할 수 없는 경우이다. 예를 들어, 한 주사위를 던졌을 때 "3이 나온다"와 "5가 나온다"는 사건은 배반적이다. 이 경우 두 사건의 교집합은 공집합이며,

$$
P(A \cap B)=0
$$

이다.

2.2 배반사건과 독립의 비교

독립 사건은 한 사건이 발생한 정보가 다른 사건의 발생 확률에 아무런 영향을 주지 않는다. 반면, 배반 사건은 두 사건이 동시에 발생할 수 없으므로, 한 사건이 발생하면 다른 사건은 반드시 발생하지 않는다. 만약 $P(A)>0$와 $P(B)>0$인 상황에서 $P(A \cap B)=0$이라면, 두 사건은 $P(A)P(B)>0$인 상황과 모순된다. 즉, 배반사건은 독립일 수 없다. 정보이론적 관점에서는, 배반사건은 한 사건의 발생이 다른 사건의 발생을 완전히 배제하는 강한 정보 의존성을 내포한다.


3. 조건부 독립과 그 정보이론적 해석

조건부 독립은 "추가 정보 $C$가 주어졌을 때, 두 사건 $A$와 $B$가 서로 독립이다"라는 개념이다. 수식으로는 다음과 같이 표현된다.

$$
P(A \cap B \mid C)=P(A \mid C) \cdot P(B \mid C)
$$

3.1 조건부 독립의 직관적 해석

조건 $C$가 주어지면, $A$와 $B$ 사이에 이미 존재하는 상호 연관 (즉, 서로 영향을 미치는 요인)이 조건 $C$에 의해 설명된다. 따라서, 조건 $C$가 있을 때 남은 $A$와 $B$의 불확실성은 서로 독립적으로 결정된다. 정보이론에서는 이것을 조건부 상호정보 $I(A; B \mid C)=0$로 해석한다. 즉, 조건 $C$가 모든 상호 의존성을 설명하므로, $A$와 $B$ 사이에는 추가로 공유되는 정보가 존재하지 않음을 나타낸다.

3.2 구체적 예시: 이진 변수 모형

$A$와 $B$를 이진 변수로 가정한다. 예를 들어,

  • $A=1$은 "고득점", $A=0$은 "저득점"
  • $B=1$은 "체육 우수", $B=0$은 "체육 부진"
    이고, 조건 $C=c$ (예: "학습 태도=우수")가 주어진다고 가정한다.

조건부 마진 확률을 다음과 같이 설정한다.

  • $P(A=1 \mid C=c)=\alpha$, 그러므로 $P(A=0 \mid C=c)=1-\alpha$이다.
  • $P(B=1 \mid C=c)=\beta$, 그러므로 $P(B=0 \mid C=c)=1-\beta$이다.

조건부 독립의 정의에 따라, 결합 확률은 두 마진 확률의 곱으로 결정된다.

  • $P(A=1, B=1 \mid C=c)=\alpha \cdot \beta$이다.
  • $P(A=1, B=0 \mid C=c)=\alpha \cdot (1-\beta)$이다.
  • $P(A=0, B=1 \mid C=c)=(1-\alpha) \cdot \beta$이다.
  • $P(A=0, B=0 \mid C=c)=(1-\alpha) \cdot (1-\beta)$이다.

이를 2×2 테이블로 나타내면 다음과 같다.

  $B=1$ ("체육 우수") $B=0$ ("체육 부진") $A$ 마진
$A=1$ ("고득점") $\alpha \cdot \beta$ $\alpha \cdot (1-\beta)$ $\alpha$
$A=0$ ("저득점") $(1-\alpha) \cdot \beta$ $(1-\alpha) \cdot (1-\beta)$ $1-\alpha$
$B$ 마진 $\beta$ $1-\beta$ $1$

이 표는, 조건부 독립이 만족되는 모든 분포가 두 벡터 $[\alpha,,1-\alpha]$와 $[\beta,,1-\beta]$의 외적으로 표현됨을 나타낸다. 정보이론적 관점에서는, 조건 $C$가 주어지면 $A$와 $B$ 사이에 추가적으로 공유되는 정보가 $0$임을 의미한다.

왜 양이 "줄어드는가" (합이 $1$이 되는가)

각 행과 열의 합은 다음과 같이 계산된다.

  • $A$의 마진:
    • $P(A=1 \mid C=c) = \alpha$
    • $P(A=0 \mid C=c) = 1-\alpha$
      따라서, 두 행의 합은 $\alpha + (1-\alpha)=1$이다.
  • $B$의 마진:
    • $P(B=1 \mid C=c) = \beta$
    • $P(B=0 \mid C=c) = 1-\beta$
      따라서, 두 열의 합은 $\beta + (1-\beta)=1$이다.
  • 전체 합:
    모든 결합 확률의 합은
    $$
    \alpha\beta+\alpha(1-\beta)+(1-\alpha)\beta+(1-\alpha)(1-\beta)
    $$
    이를 전개하면
    $$
    \alpha\beta+\alpha-\alpha\beta+(1-\alpha)\beta+1-\alpha-\beta+\alpha\beta = 1
    $$
    즉, 전체 확률이 $1$임을 확인할 수 있다.

이러한 정규화는 확률 분포의 필수 조건으로, 모든 가능한 경우의 수(즉, 표의 모든 셀의 합)가 $1$이 되어야 함을 의미한다.

3.3 다양한 값에 따른 예시

예를 들어,

  • 만약 $\alpha = 0.8$이고 $\beta = 0.7$이면,
    • $P(A=1, B=1 \mid C=c) = 0.8 \times 0.7 = 0.56$이다.
    • $P(A=1, B=0 \mid C=c) = 0.8 \times (1-0.7) = 0.8 \times 0.3 = 0.24$이다.
    • $P(A=0, B=1 \mid C=c) = (1-0.8) \times 0.7 = 0.2 \times 0.7 = 0.14$이다.
    • $P(A=0, B=0 \mid C=c) = (1-0.8) \times (1-0.7) = 0.2 \times 0.3 = 0.06$이다.
  • 만약 $\alpha = 0.9$이고 $\beta = 0.6$이면,
    • $P(A=1, B=1 \mid C=c) = 0.9 \times 0.6 = 0.54$이다.
    • $P(A=1, B=0 \mid C=c) = 0.9 \times (1-0.6) = 0.9 \times 0.4 = 0.36$이다.
    • $P(A=0, B=1 \mid C=c) = (1-0.9) \times 0.6 = 0.1 \times 0.6 = 0.06$이다.
    • $P(A=0, B=0 \mid C=c) = (1-0.9) \times (1-0.6) = 0.1 \times 0.4 = 0.04$이다.

이처럼, 조건부 독립 모형에서는 주어진 조건 $C$ 하에서 $A$와 $B$의 결합 확률이 오직 두 마진 확률 $\alpha$와 $\beta$의 곱으로 결정되며, 이 구조는 두 사건 사이에 추가 정보가 전혀 없음을 나타낸다. 정보이론적 관점에서는, 조건부 상호정보 $I(A;B \mid C)=0$임과 동치이다.


4. 정보이론적 관점에서 "영향"의 의미

확률론에서 "독립"이라 함은 한 사건의 발생이 다른 사건의 발생 확률에 영향을 주지 않는다는 것을 의미한다. 즉,

$$
P(A \mid B)=P(A)
$$

이다. 정보이론에서는 이를 "한 사건에 대한 정보가 다른 사건의 불확실성을 감소시키지 않는다"라고 해석한다. 상호정보 $I(A;B)$가 $0$이면, 한 사건에 대해 알더라도 다른 사건에 대해 얻는 새로운 정보가 전혀 없음을 나타낸다.

조건부 독립의 경우, 조건 $C$가 이미 모든 상호 연관성을 설명하므로, 조건 $C$가 주어졌을 때 $A$와 $B$ 사이에 추가적으로 공유되는 정보가 없으며, 즉, 조건부 상호정보

$$
I(A;B \mid C)=0
$$

이다. 이 수식은 "정보가 서로 영향을 주지 않는다"는 의미를 엄밀하게 나타낸다.

또한,

  • 독립 사건은 동시에 발생하는 경우(교집합)가 있을 수 있다. 단지, 그 교집합의 확률이 $P(A) \cdot P(B)$와 같아야 한다.
  • 배반 사건은 한 사건이 발생하면 다른 사건은 절대로 발생하지 않으므로, 교집합이 $0$이다. 만약 두 사건의 개별 확률이 양수인데 교집합이 $0$이면, 이는 한 사건의 발생이 다른 사건의 발생을 강제로 배제함을 의미한다.

정보이론적으로, 독립인 경우는 "정보가 추가되지 않는다"는 점, 배반인 경우는 "한 사건의 발생이 다른 사건의 불가능성을 확실히 알려준다"는 점에서 극명하게 구분된다.

중복조합

참고서, 개념서에는 중복조합의 정의를
'서로 다른 n개에서 중복을 허용하여 r개를 고르는 경우의 수'
라고 한다.

그러나,
'서로 다른 n개에서 중복을 허용하여 r개를 고르는 경우의 수'가 아니라
'(서로 다른) n개의 종류에서 r개를 고르는 경우의 수'라고 이해해야 더 명확하다.

왜 이렇게 정의해야 하는가?

이를 위해 중복조합의 정의를 살펴보자.
중복조합의 증명은 두 가지 방법으로 알려져있다.

  1. 칸막이를 도입하여 증명
  2. 순서쌍을 이용하여 증명

이 증명을 마친 후 이 개념을 조합에 적용할 수 없다는 것을 알 수 있다.
만약 중복조합이
'서로 다른 n개에서 중복을 허용하여 r개를 고르는 경우의 수'
라고 한다면 위의 두 증명(칸막이, 순서쌍)을 이용해서 조합도 설명되야 한다.
그러나, 비슷해 보이는 수식 ${}_{n}C_{r}$과 ${}_{n}H_r$을 잘 살펴보면
특히 예시를 들어 ${}_{6}C_2$ 와 ${}_{6}H_2$의 수식을 분수로 풀어놓고 생각해보면
조합은 도저히 위의 두 논리로 설명 안된다.
애시당초 정의가 다르기 때문이다.

=====
이어서

곧 작성

KMP 알고리즘

  • KMP(Knuth-Morris-Pratt) 알고리즘은 문자열에서 특정한 패턴을 빠르게 찾아주는 방법이다. 글자를 하나하나 비교하는 방식(브루트 포스)과 달리, 이전에 비교한 정보를 기억해서 불필요한 비교를 하지 않는다.이렇게 할 수 있는 이유는 LPS(Longest Prefix Suffix) 배열 덕분이다. LPS 배열은 패턴 안에서 반복되는 부분을 미리 계산해두는 배열이다. 이 정보를 사용하면, 패턴이 틀렸을 때 어디서부터 다시 시작하면 될지 빠르게 알 수 있다.
  • 즉, KMP 알고리즘은 패턴을 미리 분석해서 필요한 부분만 비교하도록 도와주는 방법이다. 덕분에 긴 문자열에서도 빠르게 패턴을 찾을 수 있다.
  • 예를 들어, "ABABABCA"라는 문자열에서 "ABABAC"이라는 패턴을 찾는다고 해보자. 보통은 첫 글자부터 하나씩 비교하지만, KMP 알고리즘은 이미 맞았던 부분을 활용해서 불필요한 검사를 줄인다.
  • 시간 복잡도 : O(M+N) 

KMP vs Brute Force 비교

알고리즘 시간 복잡도 비교 방식 최적화 방식

Brute Force O(MN) 불일치 시 패턴을 처음부터 다시 비교 없음
KMP O(M + N) LPS 테이블을 활용하여 불필요한 비교 건너뜀 접두사-접미사 정보 활용

M: 텍스트 길이, N: 패턴 길이

LPS(Longest Prefix Suffix) 테이블 개념

LPS 테이블은 패턴 내에서 **접두사(prefix)**와 **접미사(suffix)**가 같은 부분 문자열의 최대 길이를 기록하는 테이블이다. 이를 활용하면 패턴이 불일치할 경우, 이미 일치했던 부분을 다시 비교하지 않고 점프할 수 있다.

  • 가장 쉽게는 aaaaa 의 가장 큰 LPS값인 LPS[4]는 4이다.
    • 접두사는 aaaa, 접미사는 aaaa 이므로
  • abab의 가장 큰 LPS값인 LPS[3]는 2이다.
    • 접두사 aa, 접미사 aa
  • ababc는 LPS는 0이다.
    • 겹치는 부분이 없다.
  • A A B A A B의 LPS 배열은 아래와 같다.
  • [0, 1, 0, 1, 2, 3]

예제 패턴: A B C D A B C

패턴(P) 인덱스 0 1 2 3 4 5 6

문자(P[i]) A B C D A B C
LPS[i] 0 0 0 0 1 2 3

🔹 LPS 테이블 생성 과정 (단계별 분석)

패턴: A B C D A B C

초기 상태:

  • LPS = [0, 0, 0, 0, 0, 0, 0]
  • length = 0 (현재까지 접두사=접미사 길이)
  • i = 1 (두 번째 문자부터 비교 시작)

📌 1단계: i = 1

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
1 A B B A ❌ 불일치 0 0

불일치 발생 → LPS[1] = 0, length 그대로

i++ 후 다음 비교 진행


📌 2단계: i = 2

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
2 A B C C A ❌ 불일치 0 0

불일치 발생 → LPS[2] = 0, length 그대로

i++ 후 다음 비교 진행


📌 3단계: i = 3

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
3 A B C D D A ❌ 불일치 0 0

불일치 발생 → LPS[3] = 0, length 그대로

i++ 후 다음 비교 진행


📌 4단계: i = 4

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
4 A B C D A A A ✅ 일치 1 1

일치 발생 → LPS[4] = 1, length 증가

i++ 후 다음 비교 진행


📌 5단계: i = 5

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
5 A B C D A B B B ✅ 일치 2 2

일치 발생 → LPS[5] = 2, length 증가

i++ 후 다음 비교 진행


📌 6단계: i = 6

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
6 A B C D A B C C C ✅ 일치 3 3

일치 발생 → LPS[6] = 3, length 증가

i++, 반복 종료


📌 최종 LPS 테이블 결과

패턴(P) 인덱스 0 1 2 3 4 5 6
문자(P[i]) A B C D A B C
LPS[i] 0 0 0 0 1 2 3

🔹 KMP 검색 과정 (텍스트와 패턴 비교)

텍스트: A A A B C D A B C A B C D E

패턴: A B C D A B C

📌 초기 비교 상태

텍스트(T) i 현재까지 비교된 텍스트(T[0:i]) 문자(T[i]) 패턴(P) j 문자(P[j]) 비교 결과
0 A A 0 A ✅ 일치
1 A A A 1 B ❌ 불일치

불일치 발생 → j = LPS[0] = 0

패턴 인덱스를 0으로 이동 후, 텍스트 인덱스 증가 (i++)


📌 재비교 과정

텍스트(T) i 현재까지 비교된 텍스트(T[0:i]) 문자(T[i]) 패턴(P) j 문자(P[j]) 비교 결과
2 A A A A 0 A ✅ 일치
3 A A A B B 1 B ✅ 일치
4 A A A B C C 2 C ✅ 일치
5 A A A B C D D 3 D ✅ 일치
6 A A A B C D A A 4 A ✅ 일치
7 A A A B C D A B B 5 B ✅ 일치
8 A A A B C D A B C C 6 C ✅ 일치
9 - - 7 - 🎯 패턴 발견 (i - j = 2)

<aside> 💡

“i”와 “j”의 움직임 이해 KMP가 ‘점프’한다는 표현 때문에, 텍스트 인덱스 i까지도 확 뛰어넘는다고 오해하는 경우가 많다.

  • 하지만 실제로는 텍스트 인덱스 i는 대체로 1씩 증가하거나 ‘찾았다’ 직후에 동일한 위치에서 다시 비교하는 정도
  • **주요 점프 대상은 j(패턴 인덱스)**이고, 그 점프 폭을 미리 계산해 둔 테이블이 LPS </aside>

📌 패턴을 찾음: 패턴 발견 위치는 i - j = 2

  • 패턴이 완전히 일치했을 때: j == 패턴 길이 = 7
  • LPS를 활용해서 점프!
    • j = LPS[6] = 3 (패턴의 7번째 위치에서 LPS 테이블 값 사용)
    • 즉, j = 3에서부터 다시 비교 시작!
    • i는 그대로 (i = 9) → 텍스트 인덱스는 그대로 유지!

📌 LPS 적용 후, 다음 비교 과정

텍스트(T) i 현재까지 비교된 텍스트(T[0:i]) 문자(T[i]) 패턴(P) j 문자(P[j]) 비교 결과
9 A A A B C D A B C A A 3 D ❌ 불일치
9 A A A B C D A B C A A LPS[2] = 0 A LPS 점프
9 A A A B C D A B C A A 0 A ✅ 일치
10 A A A B C D A B C A B B 1 B ✅ 일치
11 A A A B C D A B C A B C C 2 C ✅ 일치
12 A A A B C D A B C A B C D D 3 D ✅ 일치
13 A A A B C D A B C A B C D E E 4 A ❌ 불일치
13 A A A B C D A B C A B C D E E LPS[3] = 0 A LPS 점프
13 A A A B C D A B C A B C D E E 0 A ❌ 불일치

<aside> 💡

불일치가 발생했으면 바로 이후 텍스트로 건너 뛰어도 될 것 같다 그렇지만 만약 찾고자 하는 패턴 안에(패턴 자체에) 반복되는 부분 문자열이 있다면 그렇게 했을 때, 예외상황이 생긴다. 예시를 통해서 이해해보자.

</aside>

패턴: A A A B A 텍스트: A A A A B A A A B A 일 때, 패턴의 의 LPS는 다음과 같다.

  • i = 0
    • 아무것도 비교할 수 없으므로 LPS[0] = 0
  • i = 1 (문자열: A A)
    • 앞선 접두사 "A"와 현재 문자 "A"가 일치
    • length = 1 → LPS[1] = 1
  • i = 2 (문자열: A A A)
    • 직전까지 일치 길이가 1(length = 1), 비교 문자: P[length] = P[1] = 'A'
    • 현재 P[i] = 'A'와 일치
    • length = 2 → LPS[2] = 2
  • i = 3 (문자열: A A A B)
    • 직전까지 일치 길이가 2(length = 2), 비교 문자: P[length] = P[2] = 'A'
    • 현재 P[i] = 'B'와 불일치
    • 불일치 시 처리
      • 우선 length = LPS[length - 1] = LPS[1] = 1로 줄여 다시 비교
      • P[length] = P[1] = 'A' vs 현재 P[i] = 'B' 여전히 불일치
      • 다시 length = LPS[1 - 1] = LPS[0] = 0
    • 결국 일치 길이를 0으로 만들고 더 이상 비교할 접두사가 없으므로 LPS[3] = 0
  • i = 4 (문자열: A A A B A)
    • length = 0, 비교 문자 P[length] = P[0] = 'A'
    • 현재 P[i] = 'A'와 일치
    • length = 1 → LPS[4] = 1

최종 LPS 테이블은 다음과 같다.

인덱스(i) 0 1 2 3 4
패턴(P[i]) A A A B A
LPS[i] 0 1 2 0 1

이제 텍스트를 인덱스로 나열하면 다음과 같다(인덱스는 0부터 시작):

T의 인덱스 0 1 2 3 4 5 6 7 8 9
텍스트(T) A A A A B A A A B A

(1) 초반 연속 일치 예시

  1. i=0, j=0
    • T[0] = 'A', P[0] = 'A' → 일치
    • → i=1, j=1
  2. i=1, j=1
    • T[1] = 'A', P[1] = 'A' → 일치
    • → i=2, j=2
  3. i=2, j=2
    • T[2] = 'A', P[2] = 'A' → 일치
    • → i=3, j=3
  4. i=3, j=3
    • T[3] = 'A', P[3] = 'B' → 불일치 발생!

(2) 불일치 시 LPS를 이용한 j 조정

  • 현재 j=3이므로, 불일치 발생 시 j를 LPS[j-1]로 이동한다.
  • LPS[3-1] = LPS[2] = 2
    • 즉, j를 2로 돌려놓고 T[3]과 P[2]를 다시 비교하자.(텍스트 i는 그대로).
  1. 재비교: i=3, j=2
    • T[3] = 'A', P[2] = 'A' → 일치
    • → i=4, j=3

<aside> 💡

여기서 보듯이, j가 0으로 떨어지지 않고(2로 세팅 후) 바로 이어서 비교를 진행 만약 LPS가 없었다면 보통 패턴 전체를 0으로 초기화한 뒤 텍스트 인덱스도 적잖이 뒤로 돌려 재비교를 할 것이다.

</aside>

  1. i=4, j=3
  • T[4] = 'B', P[3] = 'B' → 일치
  • → i=5, j=4
  1. i=5, j=4
  • T[5] = 'A', P[4] = 'A' → 일치
  • → i=6, j=5

이때 j == 패턴 길이(5)가 되었으므로, 패턴 발견!

  • “발견 위치”는 i - j = 6 - 5 = 1
    • 즉, 텍스트의 인덱스 1부터 5까지가 패턴과 일치한다.

(3) 패턴 발견 후 LPS로 또 j 이동

  • 일반적으로 KMP에서는 패턴을 찾은 뒤에도 바로 j = LPS[j-1]로 이동하여,텍스트 인덱스 i는 그대로 두고 연속 비교를 이어갈 수 있다.

➡️

위의 예시를 곰곰히 살펴보면 패턴에 반복 접두사 또는 접미사가 없을 경우에는 LPS 배열의 대부분이 0이라는 뜻이며 그러므로 LPS[j-1]로 조정해도 바로 0이 되므로 효율적으로 점프할 여지가 없는 것이다. 즉, 패턴 안에 패턴이 없다면 KMP는 통하지 않는다.

 

이제 다음 예시를 생각해보자.

패턴이 a b c d a b f 이고 텍스트가 a b c d a b c d a b f 일 때, 인간은 쉽게 찾을 수 있겠지만 컴퓨터가 이를 Brute force로 할 때, 매우 비효율적인 연산을 겪게 될 것이다. LPS[5] = 2를 이용해서 점프하면 쉽게 패턴을 찾을 수 있다.

👉

즉, 찾고자하는 패턴에 접두사 접미사 또는 패턴속의 패턴이 없다면 브루트 포스 보다 좋은건 만약 패턴 매칭이 실패했을 떄, 바로 다음 항으로 건너뛰는게 아니라 실패한 항에서 시작하는 점 뿐이다.

 

예제

🔹 예제 1: 패턴 내 중첩된 부분 문자열이 있는 경우

📌 패턴: A B C A B D A B C A B

📌 LPS 테이블 생성

이 패턴에서는 A B C가 여러 번 반복되므로, LPS 값이 점점 커지는 특징이 있다.

이러한 패턴이 포함된 경우, KMP 알고리즘이 불필요한 재비교를 얼마나 줄이는지 확인할 수 있다.

🔍 1단계: i = 1 (문자: B)

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
1 A B B A ❌ 불일치 0 0

불일치 발생 → LPS[1] = 0, length 그대로

i++ 후 다음 비교 진행


🔍 2단계: i = 2 (문자: C)

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
2 A B C C A ❌ 불일치 0 0

불일치 발생 → LPS[2] = 0, length 그대로

i++ 후 다음 비교 진행


🔍 3단계: i = 3 (문자: A)

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
3 A B C A A A ✅ 일치 1 1

일치 발생 → LPS[3] = 1, length 증가

i++ 후 다음 비교 진행


🔍 4단계: i = 4 (문자: B)

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
4 A B C A B B B ✅ 일치 2 2

일치 발생 → LPS[4] = 2, length 증가

i++ 후 다음 비교 진행


🔍 5단계: i = 5 (문자: D)

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
5 A B C A B D D C ❌ 불일치 0 0

불일치 발생 → LPS[5] = 0, length 초기화

i++ 후 다음 비교 진행


🔍 6단계: i = 6 (문자: A)

현재 인덱스(i) 현재 문자열 (P[0:i]) 현재 문자 (P[i]) 비교 대상 (P[length]) 비교 결과 LPS[i] 값 length 값
6 A B C A B D A A A ✅ 일치 1 1

일치 발생 → LPS[6] = 1, length 증가

i++ 후 다음 비교 진행


📌 최종 LPS 테이블 결과

패턴(P) 인덱스 0 1 2 3 4 5 6 7 8 9 10
문자(P[i]) A B C A B D A B C A B
LPS[i] 0 0 0 1 2 0 1 2 3 4 5

🔹 예제 2: 패턴이 완전히 반복되는 경우

📌 패턴: A B A B A B A B

📌 LPS 테이블이 점진적으로 증가하는 경우

📌 텍스트: A B A B A B A B A B A B A B

📌 이 경우, KMP는 처음 몇 번만 비교한 후 LPS 테이블을 활용하여 매우 빠르게 검색을 수행한다.

📌 LPS 테이블 결과

패턴(P) 인덱스 0 1 2 3 4 5 6 7
문자(P[i]) A B A B A B A B
LPS[i] 0 0 1 2 3 4 5 6
                 

패턴이 반복되는 경우, KMP는 처음 몇 번 비교한 후

LPS 테이블을 활용하여 불필요한 비교를 완전히 건너뛴다.

🔹 예제 3: 패턴이 거의 일치하지만 중간에 하나만 다른 경우

📌 텍스트: A B A C A B A B A C A B A B

📌 패턴: A B A B A C A B

📌 중간에 하나만 다르면, KMP는 LPS 테이블을 활용하여 빠르게 점프한다.

📌 KMP 검색 과정 중 불일치 발생 시 점프 과정

텍스트(T) i 현재까지 비교된 텍스트(T[0:i]) 문자(T[i]) 패턴(P) j 문자(P[j]) 비교 결과 LPS[j-1] 값 점프 후 j 값
6 A B A C A B A A 6 C ❌ 불일치 LPS[5]=2 2
6 A B A C A B A A 2 A ✅ 일치 - -

📌 중간에 하나만 다른 경우에도, KMP는 전체를 다시 비교하지 않고, 이미 맞았던 부분만큼 건너뛴다.

LPS 테이블 생성 함수 (Python)

def compute_lps(pattern):
    M = len(pattern)
    lps = [0] * M
    length = 0
    i = 1
    while i < M:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

KMP 검색 함수 (Python)

def kmp_search(pattern, text):
    M = len(pattern)
    N = len(text)
    lps = compute_lps(pattern)
    i = 0  # 텍스트 인덱스
    j = 0  # 패턴 인덱스
    while i < N:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        if j == M:
            return i - j  # 패턴 발견 위치
        elif i < N and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1  # 패턴을 찾지 못한 경우

문제출처 : 백준 2869번 - 달팽이는 올라가고 싶다

이 문제를 푸는 것은 어렵지 않다.
그렇지만 이를 함수를 쓰지 않고(예: math.ceil() 없이) 나타낼 수 있을까?

이에 대한 실마리를 찾기 위해 다음과 같은 상황을 생각해보자.


1. 가우스 함수로 올림 함수 표현하기

우리는 올림 함수를 가우스 함수 $[ ~~ ]$를 이용해 표현하는 방법을 두 가지로 나눌 수 있다.

정수일 때 적용할 수 있는 변형

$$
\lceil x \rceil = [ x - 1 ] + 1, \quad \text{(단, $x$가 정수일 때)}
$$

  • 이 식은 $x$가 정수일 때만 성립한다.
  • 예를 들어, $x = 3$이면 $\lceil 3 \rceil = [3 - 1] + 1 = [2] + 1 = 3$ (정확)
  • 하지만 $x = 3.4$이면 $\lceil 3.4 \rceil = 4$인데, $\left[ 3.4 - 1 \right] + 1 = [2.4] + 1 = 2 + 1 = 3$ (틀림)
  • 따라서 이 방식은 정수에 대해서만 유효하며, 소수에는 적용 불가하다.

** 분수일 때 적용할 수 있는 변형**

$$
\lceil \frac{p}{q} \rceil = \Big[ \frac{p - 1}{q} \Big] + 1, \quad \text{(단, $p, q$는 양의 정수)}
$$

  • 이 방식은 $p, q$가 양의 정수일 때 항상 성립한다.
  • 예를 들어,
    • $p = 10, q = 3$일 때:
      $$
      \lceil \frac{10}{3} \rceil = 4
      $$
      $$
      \Big[ \frac{10-1}{3} \Big] + 1 = \Big[ \frac{9}{3} \Big] + 1 = [3] + 1 = 4
      $$ (정확)
    • $p = 7, q = 2$일 때:
      $$
      \lceil \frac{7}{2} \rceil = 4
      $$
      $$
      \Big[ \frac{7-1}{2} \Big] + 1 = \Big[ \frac{6}{2} \Big] + 1 = [3] + 1 = 4
      $$ (정확)
  • 이 방식은 항상 성립하며, 특히 "분수" 형태의 값에 적용할 때 유용하다.

특수하게 정수를 논하는 문제에서만 첫번째 공식을 쓸 수 있고
사실은 두번째 공식은 정수이든 분수이든 성립한다 따라서, 두번째 공식을 쓰면 된다.
이 내용을 가지고 달팽이 문제를 풀며 된다.


2. 달팽이 문제 요약 및 식 유도

  • 낮에 $A$미터 올라가고, 밤에 $B$미터 미끄러진다.
  • 막대기의 높이가 $V$미터일 때, 달팽이가 며칠 만에 정상에 도달하는지 구해야 한다.
  • 마지막 날에는 밤에 미끄러지지 않는다.

이를 올림 함수를 직접 쓰지 않고 정수 연산만으로 풀어내려면, 다음 공식을 떠올릴 수 있다.

$$
\left\lceil \frac{V - B}{A - B} \right\rceil = \Big[ \frac{(V - B) - 1}{A - B} \Big] + 1
$$

여기서 우리는 분수 형태의 올림 연산이 필요하므로, 앞서 소개한 두 번째 방식을 적용할 수 있다.

따라서 파이썬 코드는 이렇게 작성된다.

A, B, V = map(int, input().split())
cnt = (V - B - 1) // (A - B) + 1
print(cnt)

또한, 다른 유도 방식으로는 다음과 같이 시작한다.
낮에 $A$미터, 밤에 $B$미터 이동하고 마지막 날 밤에는 미끄러지지 않으므로,

$$
A + (n-1)(A-B) \ge V
$$

에서 출발하면

$$
n \ge \frac{V-A}{A-B} + 1,
$$

즉,

$$
n = \left\lceil \frac{V-A}{A-B} \right\rceil + 1.
$$

여기서
$$
\frac{V-A}{A-B} + 1 = \frac{V-A+(A-B)}{A-B} = \frac{V-B}{A-B}
$$
이므로,
$$
n = \left\lceil \frac{V-B}{A-B} \right\rceil
$$
와 같이 표현할 수 있고, 위의 정수 연산 식과 대수적으로 동치이다.

이제 우리는 분수의 올림을 정수 연산으로 변환하는 두 번째 공식을 활용하여 문제를 해결할 수 있다.

이와 같이, 정수 연산만으로 올림 기능을 구현하는 방법을 통해
math.ceil() 없이도 달팽이 문제를 정확하게 풀 수 있음을 보였다.
두 가지 방식

  • 분자에서 바로 V - B를 사용하는 방식과
  • V - A를 사용하여 마지막에 1을 더하는 방식
    은 대수적으로 동일하므로, 상황에 맞게 편리한 쪽을 선택하면 된다.

문제 출처 : https://www.acmicpc.net/problem/2563

보통 이 문제는 도화지를 쪼개서 작은 영역으로 나누고 그 영역이 색종이이의 영역인지 아닌지를 판별하여 구하면 된다.
어떻게 보면 유한요소법이다.

이에 대한 코드는 간단히 다음과 같다.

N = int(input())
paper = [[0]*100 for _ in range(100)]

for _ in range(N) :
    x, y = map(int, input().split())
    for i in range(x, x+10) :
        for j in range(y, y+10) :
            paper[i][j] = 1

covered_area = sum(row.count(1) for row in paper)
print(covered_area)

그런데 원래 우리가 초등학교 때 배운 수학에서
도형은 원래 선을 통해 이루어진다.
다각형은 여러 선분으로
타원, 원의 경우에는 곡선으로 이루어질 것이다.
그러니까, 이 문제는 선의 경계를 찾으면 된다.
어떻게 찾을 것인가?

입력받은 x와 그로부터 생기는 x+10
y와 그로부터 생기는 y+10 에 대한 직선을 생각한다.
이것들은 도화지를 분할할테고 곰곰히 생각하면 겹치는 영역은 무조건 이 선들을 따라서 생길 수 밖에 없다.
이 영역이 색종이의 영역인지 아닌지를 판별하면 된다.
코드는 다음과 같다.

import sys
input = sys.stdin.readline

N = int(input().strip())
squares = []
for _ in range(N):
    a, b = map(int, input().split())
    squares.append((a, b))

x_boundaries = set()
y_boundaries = set()
for a, b in squares:
    x_boundaries.add(a)
    x_boundaries.add(a + 10)
    y_boundaries.add(b)
    y_boundaries.add(b + 10)

x_boundaries = sorted(x_boundaries)
y_boundaries = sorted(y_boundaries)

def is_covered(x, y):
    for a, b in squares:
        if a <= x < a + 10 and b <= y < b + 10:
            return True
    return False

total_area = 0
for i in range(len(x_boundaries) - 1):
    for j in range(len(y_boundaries) - 1):
        mid_x = (x_boundaries[i] + x_boundaries[i+1]) / 2.0
        mid_y = (y_boundaries[j] + y_boundaries[j+1]) / 2.0
        if is_covered(mid_x, mid_y):
            total_area += (x_boundaries[i+1] - x_boundaries[i]) * (y_boundaries[j+1] - y_boundaries[j])
print(total_area)

도형을 경계를 구성하는 점과 선의 집합으로 바라본다면, 풀이 과정에서 점과 선을 모두 활용하는 것이
자연스럽다. 그러니까 점으로 생각한 풀이와 선으로 생각한 풀이 두 가지가 나올 수 있는 것이다.

아래의 문제는 어떤 문제에서 영감을 받아 직접 변형한 문제입니다.


🚦 출근길을 지켜라! - 교통신호 최적화 문제 🚦

배경 이야기

교통국에서 일하는 ‘교통이’는 출근길 정체를 줄이기 위해 일직선 도로에 있는 신호등 $N$개를 조정해야 한다.

하지만 문제는 이 신호등이 특수한 방식으로 작동한다는 것이다.

  • 교통이는 신호등 번호 $j$를 조작할 수 있다.
  • 하지만 $j$번 신호등을 조작하면, $j$의 배수인 모든 신호등이 동시에 상태를 반전(빨간 ↔ 초록)시킨다.

현재 모든 신호등은 빨간불(0) 상태이다.
교통이는 최소한의 조작만으로 도로의 신호등을 원하는 패턴(초록불=1, 빨간불=0)으로 맞춰야 한다!


입출력 설명

  1. 입력

    • 첫 줄에 테스트 케이스 수 $T$.
    • 각 테스트 케이스에서:
      1. 첫 줄에 신호등 개수 $N(1 \leq N \leq 100)$.
      2. 둘째 줄에 $N$개의 정수(0 또는 1)로 목표 신호 상태가 주어진다.
  2. 출력

    • 각 테스트 케이스마다,
      “#(테스트케이스번호) (최소 조작 횟수)” 형태로 결과 출력.

예제 (교통이의 신호 조정 시뮬레이션)

  • 예제1:
    $N=3$, 목표 상태: [1, 0, 1]

    1. 🛑 처음: [0, 0, 0] (모든 신호등이 빨간불)
    2. 🚦 1번 신호 조작 → [1, 1, 1] (1,2,3번 신호등이 토글됨)
    3. 🚦 2번 신호 조작 → [1, 0, 1] (2번 신호등만 토글됨)
    • ✅ 총 2번 만에 목표 달성!
  • 예제2:
    $N=5$, 목표 상태: [1,1,0,0,1]

    1. 🛑 처음: [0,0,0,0,0] (모든 신호등이 빨간불)
    2. 🚦 1번 신호 조작 → [1,1,1,1,1] (1~5번 신호등이 토글됨)
    3. 🚦 3번 신호 조작 → [1,1,0,1,1] (3번 신호등만 토글됨)
    4. 🚦 4번 신호 조작 → [1,1,0,0,1] (4번 신호등만 토글됨)
    • ✅ 총 3번 만에 해결!

...

아래에는 문제풀이 스포가 있습니다.

...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


이 문제를 푸는 것은 어렵지 않다.
전형적인 그리디 알고리즘이다. 그런데 왜 그리디 알고리즘이 통하냐고 하면 대답하기 쉽지 않다.
대충 이정도로 얼버무릴 수 있을 것 같다.
만약 8번째가 켜져있어서 8번을 클릭해서 켰는데 다시 4번이나 2번을 누르면 말짱도루묵이니까
순차적으로 하지 않으면 엉망이 되고 문제가 어려워진다. 그래서, 그리디이다.
이런 논증은 비약이 엄청 심한 논증이다.
나는 처음 풀 때 이를 다음과 같이 풀었다.

신호등 문제: 그리디와 XOR로 풀어보자

위에서 이미 예시를 보면 감이 오겠지만,
문제의 핵심“버튼 $j$를 누르면 $j$의 배수 신호등들이 전부 토글(켜짐 ↔ 꺼짐)된다”는 것입니다.

  • 초기 상태: 모든 신호등이 꺼져 있음(0).
  • 목표: $N$개의 신호등을 각각 원하는 패턴(0 또는 1)대로 켜거나 끄기.
  • 클릭(버튼 누르기) 최소 횟수를 구하기.

예컨대, $N=3$이고 목표가 “1 0 1”이었을 때,
1번 → 2번 신호등을 차례대로 누르면 2번 만에 원하는 결과를 얻을 수 있었죠.


1. 단순 시뮬레이션(그리디) 아이디어

가장 직관적인 풀이는 아래와 같은 그리디 알고리즘입니다.

  1. $j = 1$부터 $N$까지 차례대로 확인한다.
  2. “현재 상태”에서 $j$번째 신호등이 목표 패턴과 다르면 → $j$번 버튼을 누른다.
  3. “현재 상태”에서 $j$번째 신호등이 목표 패턴과 같으면안 누른다.
  4. 이렇게 $N$까지 진행하면 최종적으로 목표 패턴이 완성된다.
# b[j] = j번 신호등의 목표 상태(0 또는 1) (1-based)
# state[j] = 현재 j번 신호등의 상태
# N = 신호등의 총 개수

state = [0] * (N+1)  # 초기: 모두 꺼짐
click_count = 0

for j in range(1, N+1):
    if state[j] != b[j]:  # 목표와 다르면 클릭
        click_count += 1
        # j의 배수들을 전부 토글
        for k in range(j, N+1, j):
            state[k] = 1 - state[k]

print("최소 클릭 횟수:", click_count)

이 방법이 항상 목표를 만족하는 이유

  • 앞에서부터 순서대로 맞춰놓고, 이미 처리한 앞쪽 신호등을 다시 뒤집지 않는다.
  • 예를 들어, 2번 신호등을 맞추기 위해 1번 버튼을 다시 누르면 1의 배수(모든 신호등)가 또 바뀌면서 엉망이 된다.
  • 따라서 한 번 결정한 건 건드리지 않고, 해당 시점에서 필요한 신호등만 토글하는 방식이 최소 클릭을 보장한다.

2. "그리디가 왜 최적(최소 클릭)인지?" - 직관적인 설명

  • 이미 한 버튼을 두 번 클릭하는 것은 의미가 없다(두 번이면 원상 복구).
  • 한 번 결정한 걸 또 뒤집으면 앞에서 맞춰둔 다른 신호등들까지 바뀌면서 서로 충돌 가능성이 높아지고, 클릭 횟수도 증가할 뿐이다.
  • 필요할 때 한 번만 누르는 것이 결국 최소로 누르는 방법이다.

이 정도로도 어느 정도 이해할 수 있지만,
조금 더 엄밀하게 증명하려면 XOR(모듈로 2) 관점에서 보는 것이 더 깔끔하다.


3. XOR(모듈로 2)로 풀이하기

3.1 문제를 “모듈로 2 선형방정식”으로 만들기

  1. “$j$번 버튼을 누르는지 말지는 0/1로 표현”

    • $x[j] = 1$이면 $j$번 버튼을 ‘홀수 번’ 누른 것,
    • $x[j] = 0$이면 ‘아예 안 누르거나 짝수 번’ 누른 것(결국 효과 없음).
  2. $j$번째 신호등의 최종 상태 = “$j$의 배수 버튼”들을 XOR한 값

    • 예: 6번 신호등은 (1번 버튼, 2번 버튼, 3번 버튼, 6번 버튼)이 각각 1로 눌렸다면 그 개수만큼 토글됨.
    • 결국 짝수 번이면 0, 홀수 번이면 1. → XOR 연산과 동일.
  3. 목표 패턴 $b[j]$에 맞추려면,
    $$ b[j] = \bigoplus_{d \mid j} x[d]. $$

    • $d\mid j$는 $j$의 약수를 의미.
    • 혹은 $j$의 배수인지 약수인지 관점이 다를 뿐, 같은 원리이다.

3.2 전진 대입(Forward Substitution)으로 해 구하기

$$
x[j]
=
b[j] \oplus
\Bigl(\oplus_{\substack{d < j \ d \mid j}} x[d]\Bigr).
$$

  • , $j=1$부터 $N$까지 순서대로, 이미 결정된 $x[1], x[2], \dots, x[j-1]$와 목표 $b[j]$를 보고 $x[j]$를 0 또는 1로 결정할 수 있다는 뜻이다.
  • 이것이 실제 코딩에서는 “현재 상태와 목표가 다르면 클릭”으로 구현되는 것이다.

T = int(input().strip())
for test_case in range(1, T+1):
    N = int(input().strip())
    b = list(map(int, input().split()))
    # b[i]는 i번째 신호등의 목표 상태 (0 or 1), 여기서 i는 0-based

    # state: 현재 신호등 상태(모두 0부터 시작), 0-based 맞춰서 사용
    state = [0]*N  
    click_count = 0

    # 그리디 시뮬레이션
    for i in range(N):
        if state[i] != b[i]:
            click_count += 1
            # i의 배수(0-based에서는 i, i+(i+1), ...)를 토글
            # 단, 인덱스는 0-based, 버튼번호는 (i+1)
            step = i+1
            for k in range(i, N, step):
                state[k] = 1 - state[k]

    print(f"#{test_case} {click_count}")

4. 마무리

  • 단순히 시뮬레이션하면 그리디처럼 보이지만, 본질적으로 XOR(모듈로 2) 성질이 핵심이다.
  • 전진 대입(Forward Substitution) 방식으로 푸는 것이 최적임을 증명할 수 있다.
  • 실제 코드로 구현할 때는 단순히 “목표와 다르면 클릭”을 수행하면 된다.

이제 신호등 토글 문제를 가장 효율적으로 푸는 방법을 확실히 이해했을 것이다.

5. 추가 예시와 함께 살펴보기

이번에는 실제로 XOR 관점에서 버튼을 어떻게 결정하는지, 구체적인 예시를 통해 확인해 보겠습니다.

예제 1: $N=3$, 목표 상태: $[1, 0, 1]$

1) 초기 상태 및 방정식

  • 초기 신호등 상태: $[0, 0, 0]$
  • 목표 상태: $[1, 0, 1]$

신호등 $j$에 대응하는 버튼을 $x[j]$라고 하면,

  • $ b[1] = x[1] $
  • $ b[2] = x[1] \oplus x[2] $
  • $ b[3] = x[1] \oplus x[3] $

목표 $ b = [1, 0, 1] $을 만족하려면,

2) 전진 대입 순서

  1. $j=1$:

    • $ x[1] = b[1] = 1 $
    • (버튼 1번을 누른다 → 모든 신호등이 한 번씩 토글되어 $[1,1,1]$이 됨)
  2. $j=2$:

    • $ b[2] = 0 $, 이미 $x[1] = 1$이라고 할 때,
    • $ x[2] = b[2] \oplus x[1] = 0 \oplus 1 = 1 $
    • (버튼 2번을 누르면 2의 배수인 신호등 2번, 4번(없음)은 토글 → 실제로는 $[1,(1→0),1]$이 되어 $[1,0,1]$)
  3. $j=3$:

    • $ b[3] = 1 $, 이미 $x[1] = 1$.
    • $ x[3] = b[3] \oplus x[1] = 1 \oplus 1 = 0 $
    • (즉, 버튼 3번은 안 누른다)

결국 $\mathbf{x} = (1,1,0)$ 로,
버튼 1번, 2번만 누르면 2번의 클릭으로 끝납니다.


예제 2: $N=5$, 목표 상태: $[1, 1, 0, 0, 1]$

  1. 초기 상태: $[0, 0, 0, 0, 0]$
  2. 목표 상태: $[1, 1, 0, 0, 1]$

버튼을 $x[1] \dots x[5]$라 할 때, 신호등별로:

  • $ b[1] = x[1] $
  • $ b[2] = x[1] \oplus x[2] $
  • $ b[3] = x[1] \oplus x[3] $
  • $ b[4] = x[1] \oplus x[2] \oplus x[4] $
  • $ b[5] = x[1] \oplus x[5] $

목표 $[1,1,0,0,1]$을 만족하려면,

  • $ j=1:, x[1] = 1 $
  • $ j=2:, x[2] = b[2] \oplus x[1] = 1 \oplus 1 = 0 $
  • $ j=3:, x[3] = b[3] \oplus x[1] = 0 \oplus 1 = 1 $
  • $ j=4:, x[4] = b[4] \oplus x[1] \oplus x[2] = 0 \oplus 1 \oplus 0 = 1 $
  • $ j=5:, x[5] = b[5] \oplus x[1] = 1 \oplus 1 = 0 $

즉, $\mathbf{x} = (1,0,1,1,0)$.
이를 시뮬레이션하면 실제로 3번(3,4,1 - 순서는 다를 수 있음) 정도 누르면 $[1,1,0,0,1]$을 만들 수 있습니다.

(주의): 예시 해석에서는 약수/배수 구분 등으로 인해 실제 “누르는 순서”가 달라 보일 수 있지만,
결론적으로 XOR 전진 대입이 “필요한 버튼만 1번씩” 골라내어 최소 횟수로 신호등을 맞춘다는 사실은 동일합니다.


6. 교환(Exchange) 증명 간단 스케치

혹시 “더 적게 누르는 해”가 있을 수 있다고 생각한다면, 아래 교환 논리를 대입해 볼 수 있습니다.

  1. 가정: 어떤 해 $\mathbf{x}^{\text{opt}}$가 $\mathbf{x}^{\text{greedy}}$보다 적은 클릭으로 목표를 만족시킨다고 치자.
  2. 중복 클릭 제거: 버튼을 짝수 번 누르면 ‘안 누른 것’과 동일하므로, $\mathbf{x}^{\text{opt}}$ 역시 최대 1번씩 누른 형태로 정규화할 수 있음.
  3. 앞에서 뒤로 교환: 1번 버튼부터 비교해가며, $\mathbf{x}^{\text{greedy}}$와 다르게 눌렀다면 그 차이를 교환(토글)하는 과정에서,
    뒤 신호등 상태가 뒤섞이지만, 결과적으로 클릭 수를 더 줄일 수 없음을 보일 수 있다.
  4. 결론: $\mathbf{x}^{\text{greedy}}$로 바꾸더라도 클릭 수가 증가하지 않는다면, 그리디 해 역시 최적해와 동일한 비용을 가진다.

7. 더 큰 N에서의 시간 복잡도?

  • 그리디 시뮬레이션 방식은 최대 $O(N^2)$ 정도로 동작하며, $N \le 100$ 이면 충분히 빠릅니다.
  • XOR 전진 대입 방식도 비슷한 복잡도를 가집니다.
  • 어떤 방법이든, N=100 수준에선 거의 순간에 해결이 가능하므로 최적화 고민은 크게 필요 없습니다.

8. 결론 & 한 줄 요약

  1. 버튼 토글 문제는 “한 버튼을 여러 번 누르느냐(짝수·홀수)”가 중요하므로, XOR(=모듈로 2) 문제로 볼 수 있다.
  2. 그리디 시붬레이션(앞에서부터 필요 시 클릭)이나 전진 대입(XOR 방정식 풀이) 모두 최소 클릭을 보장한다.
  3. “한 번 결정한 걸 다시 뒤집는 건 낭비”라는 점이 이 문제를 단순화시킨다.

9. 마무리

이상으로 신호등 토글 문제를 그리디 & XOR 관점에서 푸는 전반적인 과정을 살펴봤습니다.

  • 시뮬레이션 코드도 간단하고,
  • 수학적 증명(모듈로2, XOR)도 깔끔하기 때문에,
  • 자신 있게 “최소 클릭”임을 주장할 수 있습니다.

+ Recent posts