Chocolate

Invariants in Algorithms

불변량을 공부하기 위한 문제는 다음과 같습니다.
격자무늬로 금이 간 초콜릿을 여러 개의 작은 초콜릿으로 쪼개려고 합니다.
쪼갠다는 것은 금을 따라서 초콜릿을 둘로 나눈다는 것을 의미합니다.
하나의 초콜릿을 금이 그어진 대로 모두 쪼개어 작은 조각들로 만드려면 몇 번을 쪼개야 할까요?

Identify Potential Invariants

문제를 풀기 위해 잠재적인 불변량 식별이 필요합니다.
이 문제에서 변하지 않는 것은 쪼갠 수와 쪼개진 조각의 차이입니다.
이것이 불변량이자 상수이며 0번 쪼개었을 때 1개의 초콜릿이므로 그 초기값은 1입니다.

Abstraction

이제 문제에서 불필요한 세부사항을 걷어내고 필수적인 요소만 남기기 위한 작업이 필요합니다.
조각의 수를 p, 쪼갠 수를 c로 표기하겠습니다.
문제가 초콜릿 문제였는지 색종이 자르기였는지, 조각을 자르는 순서나 크기 등은 이 문제를 푸는데 필요하지 않습니다.
p와 c는 이런 것들을 포함하지 않으면서도 문제를 풀기에 충분합니다.
세부사항을 걷어내고 추상화 하는 작업은 어렵습니다.
또 무엇이 필수적인지 정하는 과정도 동일합니다.

Assignment Statement

이제 대입문을 사용하여 한 번 쪼개는 것에 대한 행위를 모델링하겠습니다.
대입문 기호는 :=를 사용할 것입니다.
p,c := p+1, c+1라고 작성할 경우 좌변은 어떤 중복도 허용되지 않고 우변은 좌변의 개수에 맞춰 표현식을 작성합니다.
이 대입문을 수행 시 표현식을 계산한 후 좌변 값을 표현식의 값으로 바꿉니다.
즉 , p,c를 p+1, c+1로 치환하는 것입니다.
대입문의 불변량은 대입 이전과 이후의 값이 항상 일정하게 유지되는 상태의 함수입니다.
예를 들어 p-c는 p,c := p+1, c+1의 불변량입니다.
이를 확인하는 법은 표현식의 모든 변수를 대입문에 적힌 변수로 치환하였을 때 표현식의 값이 변하는지 확인하는 것입니다.
p-c에 p+1, c+1을 대입해도 같은지 보기 위해 p-c = (p+1) - (c+1)이라는 식을 만들고 식이 성립하는지 보면 됩니다.
또 다른 예로는 m,n := m+3, n-1이라는 대입문에서 m+3*n이 불변임을 알아볼 수 있습니다.
m+3*n = (m+3)+3*(n-1)를 풀어보면 표현식이 성립하는 것을 알 수 있죠.

Induction

이제 p-c라는 불변성을 활용하여 풀이를 끝낼 수 있습니다.
초기 상태에서 p=1이고 c=0입니다. 즉 처음에는 p-c=1입니다.
그리고 앞서 알아보았듯 p-c는 불변량이므로 초콜릿을 몇 번을 쪼개든 p와 c의 차이는 언제나 1입니다.
이제 모든 초콜릿 조각을 쪼갰을 때의 수 s를 p로 두었을 때 c=s-1을 알아낼 수 있습니다.
이는 수학적 귀납법이라는 원리가 사용되었는데 어떤 대입에 의해 표현식의 값이 바뀌지 않는다면 대입을 몇 번을 하든 값이 변하지 않는다는 것입니다.
대입을 0회 적용하더라도 값은 바뀌지 않습니다.

Conclusion

이제 그림의 초콜릿처럼 20조각을 만들어야 한다면 c = p -1을 통해 19번의 쪼개기가 필요하다는 걸 알게 되었습니다.
초콜릿 문제는 간단하지만 직관으로 풀기보다 불변량을 찾고 추상화 하는 과정을 연습해나가는 것이 추후 더 어려운 문제를 풀어나가는 데 직관보다 더 나은 바탕이 되어줄 것이라 생각합니다.