흥미로운 주제로군요. 비슷하다면 비슷한데 또 다르다면 다른 주제로 동영상 압축 기법인 벡터 양자화(vector quantization)가 있습니다. 이를테면... 16x16 크기의 샘플 패턴 N개를 생성합니다. 이후 동영상의 각 프레임들을 16x16 격자로 나눈 후 거기에 대응되는 샘플 패턴의 번호로 나타내는 것이죠. 만일 패턴이 256개라면 1바이트로 표현할 수 있으니까 RGB 각 1바이트로 나타낸 색 공간에서라면 동영상은 1/3크기로 줄어들게 되겠죠.
샘플 패턴을 어떻게 정할 것인가는 자명한 방법이 있습니다. 해당 샘플 패턴을 사용할 격자들과의 제곱오차를 최소로 하는 패턴을 사용하면 되겠죠. 다시 말해서 그 격자들의 기하평균을 구하면 됩니다.
그렇다면 결국 각각의 격자값을 어떤 패턴에다 대응시키는 것이 화질 열화를 최소로 하는 방법인지 찾아내야 하는데 고려해야 할 변수가 많기 때문에 그리 쉽지는 않습니다. 이 경우에도 LP 등의 기법을 많이 동원하더군요. 그런데 Genetic algorithm에다가 local optimization을 동원한 알고리즘이 상당히 좋은 성능을 보인다는 얘기를 봤어요.
1. 여러 흥미로운 보충 설명에 감사드립니다. 영상의 손실 압축에서 화질 열화를 최소화하는 기법에도 그런 방식의 문제가 있다는 것도 처음 알았고요. 그리고 문 교수님이 그 분야에도 손대신 적이 있다는 것도요.
그리고 엘리베이터.. 그것도 좌석 배당만큼이나 경험적인 전략이 필요한 아주 실용적인 주제임이 틀림없어 보입니다. 아주 초창기에 1회 IOI 때 대놓고 엘리베이터 시뮬레이션 문제가 나온 적이 있었지만 그때는 너무 옛날이어서 대회 진행 방식이 정착하기 전이었고, 9회(97년) 6번 문제 컨테이너 쌓기도 비슷하다면 비슷한 주제 같습니다. 승객 대신 컨테이너이고, 좌석의 단편화 대신 스택 구조가 있는 셈이죠.