불변량이란?
변환을 적용해도 변하지 않는 일정한 값 == 상수, 패턴
여기서 공부한 건
- 불변량이 문제 해결에 어떻게 도움되는지
- 좋은 접근 방법, 나쁜 접근 방법
- 새로운 문제 풀이에 대한 개념
문제를 간략하게 적고, 내가 생각한 풀이를 기술한 뒤 마지막에 저자의 풀이 이런식으로 글을 적어나갈 생각이다.
2-1) 초콜릿 쪼개기
4X3의 초콜릿을 쪼개는 문제 였다.
직사각형의 초콜릿을 정사각형 조각으로 쪼개려 할때 어떻게 쪼갰는지를 알아보는 문제 였다.
나는 2X1을 쪼개는데 한번이 든다.에서 시작했다.
즉 어떻게든 MX1의 형식으로 만들면 MX1을 하나의 정사각형 조각으로 만들려면 M-1번 이 필요하다고 생각했고, 4X3 조각이면 각각을 4X1개 조각으로 만든 뒤 3번이 필요하다. 즉 MXN 조각을 쪼개려면
(M-1) X N + N-1(M-1)X N = MX1의 조각을 N 번 쪼개는 횟수
N-1 = N으로 쪼개는 횟수
즉 4X3 의 조각을 쪼개기 위해선
(4-1)X3 + 3-1 = 11이렇게 생각 했다.
문제를 푸는 방식
2-1) 초콜릿
이 문제는 비슷한듯 다른 방식 이었고 제목처럼 불변량을 이용해야 했다. 초콜릿을 한번 쪼갤 때 초콜릿을 쪼갠 횟수는 1 증가 하고, 초콜릿 조각의 수도 1 증가한다. 즉 쪼갠 횟수와 조각의 수 둘다 변한다. 하지만, 변하지 않는 값이 있고, 쪼갠 횟수와 조각의 수의 차이였다.
처음에 1조각 일때 쪼갠 횟수는 0 이다.
이 값은 2조각 일땐 1회 쪼갰을 것이고 수가 늘어도 변하지 않는 불변량 인것이다.
수학적 풀이
글로 써나가는 풀이보다 수학적 표기는 간결하고 정확하다.
1) 추상화
문제에서 핵심적인 요소를 완전하게 기술하는 변수로 만드는 것
이 단계에서 불필요한 세부 사항이 사라진다.
초콜릿으로 무엇인가를 한다는건 불필요한 세부 사항이다. 문제 풀이와 전혀 관련이 없다.
문제의 핵심은 수의 성질이다.
초콜릿을 쪼개거나 조각들의 모양 및 크기 또한 불필요하다.
변수 p를 조각의 수, c를 쪼갠 횟수 라고 하면 이는 쪼갠 순서나 상태를 기술하지 않아도 상관 없다. 예를 들어 4번을 쪼개서 5조각이 나왔건 조각들의 크기가 어떻건 해결해야 하는 문제와는 상관 없다는 얘기다.
추상화 단계는 수행하기 가장 어렵기도 하다. 불필요한 세부 사항을 포함하는 함정에 빠져 나와야 하고, 어떤 요소의 필요,불필요를 판단하는게 쉬운 작업이 아니기 때문이다. 심지어 이런 결정을 내려주는 알고리즘은 존재하지 않는다.
2) 대입
문제 풀이의 과정을 모델링 하는것
다음 과정은 초콜릿을 쪼개는 과정을 모델링 하는것이다.
p,c:= p+1, c+1
대입문의 불변량은 대입 이전과 이후 값이 일정하게 유지되는 상태의 함수이다. p-c는 다음 대입문의 불변량이된다.
p-c == (p+1) - (c+1) == p-c
이렇게 대입문에 불변량을 대입해 봄으로써 불변량인지 알 수 있다.
3) 귀납
불변성을 활용하는 것, 어떤 대입에 의해 표현식의 값이 바뀌지 않는다면, 그 대입을 몇번 적용하더라도 값이 변하지 않는다.
초기 상태에서 p=1 이고 c=0이다.즉 p-c=1이다.
p-c가 불변량 이므로, 초콜릿을 얼마나 쪼갰는지에 관계없이 p-c=1 이다.
초콜릿을 완전하게 쪼갠 횟수 s에 대해서도 성립 하므로 s-c=1 이 된다.
그럼 쪼갠 횟수 c = s-1 임을 알 수 있다.
공부 한 것들 정리
불변량이란?
변환을 적용해도 변하지 않는 값
문제를 푸는 방법?
문제를 추상화 한다.
- 필요, 불필요를 판단해서 문제를 단순화 한다.
- 필요한 세부 사항들에 대해 변수를 대입한다.
풀이의 과정을 모델링 한다.
- 문제의 과정을 식으로 표현 한다.
- 불변량을 찾아 대입문에 검증한다.
귀납을 활용해 문제를 해결한다.
- 초기값을 설정하고, 불변량을 이용해 문제를 해결한다.
문제를 해결하고자 할때 불필요한 요소를 걷어내고, 간단하게 식으로 표현하는 연습부터 해야 겠다. 결국 좋은 질문도 그것부터 시작이니까
