18789 - 814 - 2
본문
숫자 0~9 로만 이루어진 8 × 14 크기의 표를 만들어 출력해보자. 다음과 같은 방식으로 만들어진 수를 표에서 “읽을 수 있다“라고 한다:
표 위의 어떤 칸에서 시작하여, 상하좌우 혹은 대각선으로 인접한 칸으로 이동하면서 칸에 적힌 숫자를 순서대로 이어붙여 수를 만든다.
지나갔던 칸을 다시 방문하여 수를 이어 붙이는 것은 가능하지만, 칸을 건너뛰거나, 같은 칸에 계속 머물러서 수를 이어 붙이는 것은 안 된다.
아래와 같은 2 × 3 크기의 표를 예로 들어보자.
원으로 표시된 1에서 시작해서, 아래쪽, 오른쪽, 왼쪽위, 왼쪽으로 이동하면 12314가 만들어지므로, 이 표에서는 12,314를 읽을 수 있다. 만약, 4에서 시작해서 역순으로 이동하면 41,321도 읽을 수 있을 것이다.
그러나, 4에서 시작해서 칸을 건너뛰어 이동하는 것은 불가능하므로 46은 읽을 수 없으며, 1에서 시작해서 같은 칸에 계속 머물러 있을 수 없어서 11또한 읽을 수 없다.
입력
입력은 주어지지 않는다.
출력
숫자 0 ~ 9 로만 이루어진 8 × 14 크기의 표를 출력하면 된다.
출력된 표에서 1부터 X까지의 수를 모두 읽을 수 있는데, X+1은 읽을 수 없다면 X점을 받게 된다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 0.814sec | 814MB |
풀이
Step 0
util 함수 정의하기
실제로 표를 만들고 정답을 찾아가기 전에 먼저 해야할 것이 있다.
표를 얼마나 만들지 모르기 때문에, 나만의 체계를 만들어서 실험을 돌릴 수 있도록 구현해야 할 필요성이 있었다. 다른 것들은 내가 편한대로 만들어 사용하므로 실질적으로는 필요 없는 함수들이지만, 딱 한가지는 필수적으로 만들어야했다. 바로 점수를 계산하는 함수이다. 내가 구현한 방법들이 얼만큼의 효율을 내는지는 정량적으로 평가해야하므로, 표를 만들기 전에 이 부분부터 작업에 들어갔다.
점수는 일반적인 dfs를 활용하여 계산할 수 있다. 다만 일반적인 dfs에서 사용하던 visit는 여기서는 사용하지 않는다. 사실 visit을 체크하면 안 된다. 이미 방문했던 칸도 재방문할 수 있기 때문이다.
문제에서 제시하는 점수는 “1부터 시작하여 읽을 수 있는 연속적인 수들 중 최댓값”이다. 즉 $1$부터 $N$까지의 수는 모두 읽어낼 수 있지만 $N+1$을 읽지는 못할 때, $N$이 점수가 된다. 문제에서 제시하는 목표는 $8140$점 이상이므로, $1$부터 $8140$까지는 모두 읽을 수 있는 표를 찾는 것이 목표가 되는 것이다. 그리고 이것을 계산하는 함수를 하나 만들어 점수 측정으로 활용하였다. sparse array를 이용하여 어떤 수를 읽었는지를 체크하고, 체크되지 않은 수들 중 최솟값을 찾아내어 점수를 계산하는 방식이다. 구현이 어렵지는 않으므로 스스로 해보자.
계획 짜기
일단 우리는 어떤 방법을 쓰던 8x14 크기의 표를 만들고 그것의 점수를 계산하여 문제를 해결할 것이다. 하지만 단순히 몇 개만 만들어서 풀려고 시도하면 택도 없다. 표의 크기가 8x14 이므로 가능한 표의 총 개수는 $10^{8 \times 14}$이다. 문제에는 전략적으로 접근해야할 것이다.
작년에 어떤 논문 작업에 참여하면서 알게 된 알고리즘이 있다. 유전 알고리즘이 그것인데, 요약하면 “우월한 유전자를 가진 애들끼리 합치면 더 좋은 애들이 나오지 않을까?” 에서 고안된 알고리즘이다. 이 문제를 보자마자 제일 먼저 떠오른게 이 알고리즘이고, 궁극적으로는 이 알고리즘이 해답을 줄 수 있는지 테스트해보려한다. (풀지 못한다면 다른 방법을 찾아봐야하겠지만..)
아래 단계부터는 문제를 풀기까지 시도한 것들을 2차 테스트때의 시점부터 나열한다. 1차 테스트에는 체계 없이 중구난방으로 Step 5까지 실행해봤었고, 그 때의 최대 점수는 $4495$였다. 이전 것들은 기록이 안남았으니 기억 저 뒷편으로 버리고, 이후 단계에서 얻은 결과들만 공식으로 생각하려한다.
Step 1
표 랜덤 생성하기
max score : 768
말 그대로 8x14 크기의 표를 모두 랜덤한 수로 채워넣었다. 총 1천만개의 표를 랜덤으로 만들어서 실험해봤고, $500$점이 넘는 표를 총 8개 얻을 수 있었다. 결과를 요약하면 아래와 같다.
| epoch | score |
|---|---|
| 641807 | 556 |
| 1292582 | 667 |
| 1808444 | 557 |
| 3017373 | 619 |
| 3802803 | 555 |
| 7182881 | 505 |
| 7829777 | 556 |
| 9775839 | 768 |
물론 여기서 나오는 점수는 단순히 운이다! 운이 좋다면 바로 8140점을 얻을 수도 있는 것이고, 안 좋다면 300점을 넘기지 못할지도 모르는 단계이다. 사실상 표를 만들어보고 점수 계산 함수가 제대로 동작하는지 확인하는 단계. 다행히도 모든 표의 점수가 백준에 제출했을 때의 점수와 같았으므로, 점수 계산에는 문제가 없음을 확인했다는 것에 만족했다.
Step 2
한 자리만 바꿔 최대 점수에 도달하기
max score : 2378
어떤 표에 대해 계속해서 한 자리만 바꿔 가능한 최대 점수에 도달하는 것을 목표로 구현했다. 하나의 표에 대해 가능한 모든 가능성에 대해 점수를 계산하고, 그들 중 최대 점수를 찾아 표를 바꾼다. 그 과정을 여러번 반복하여 더 이상 점수가 올라가지 못하는 지점까지 반복한다. 시간이 오래 걸릴 것 같지만, 한 자리만 바꾸는 것은 하나의 표에 대해서 총 $8\times 14 \times 10 = 1120$개의 표를 생성하고 그들 중 최댓값을 찾는 과정이 되는 것이다. 생각보다 오래 걸리지는 않는다.
아래 표는 Step 1에서 얻은 표를 Step 2에 돌려봤을 때의 결과이다.
| epoch | score |
|---|---|
| 641807 | 2266 |
| 1292582 | 2054 |
| 1808444 | 2054 |
| 3017373 | 2202 |
| 3802803 | 2378 |
| 7182881 | 2337 |
| 7829777 | 2067 |
| 9775839 | 2239 |
Step 1과 비교했을 때는 점수가 확 오른 것을 볼 수 있었다. 그러나 여기서 점수가 계산되었다는 것은, 이 표에서는 자리 하나만 바꿔가는 연산으로는 더 이상 점수를 올릴 수 없다는 것을 의미하게 되는 것이었다. 흔히 local optimal에 빠졌다고 하는데, 다른 알고리즘을 쓰지 않는 이상 이 표는 더 이상 가망이 없음을 의미하는 것이었다. local optimal을 빠져나오는 다른 방법을 생각해봐야한다.
Step 3
mutate 개념의 도입
max score : 3223
한 자리만 바뀌는 것으로는 local optimal에 빠진다고 얘기하였다. 그럼 local이라는 구렁텅이에 빠지게 된다면 탈출시켜 주어야 한다는 것이 가장 먼저 떠오를 것이다.
그래서, 그런 상황에서 표를 약간 바꾸어 탈출시키는 방법을 떠올리게 된 것이다. 유전알고리즘에서 활용하던 “돌연변이”, mutate 방법을 사용해보았다. local optimal에 빠지면 각 자리에 대해 특정 확률로 그 위치의 숫자가 무조건 바뀌도록 구현하였다. Step 3의 과정을 자세히 설명하면 아래와 같다.
- Step 1처럼 표를 랜덤으로 하나 만든다
- 아래의 과정을 반복한다 (epoch = 1000으로 설정)
- 현재 표에 대해 Step 2를 진행한다
- 역대 최고 점수와 비교하고, 최대 점수라면 기록을 갱신한다
- 이전 epoch의 점수와 비교한다
- 만약 같다면, local optimal에 빠졌다고 판단하고, mutate 확률을 2배 올린다
- 만약 다르다면, 다른 state로 움직였다고 판단하고, mutate 확률을 기본으로 되돌린다
- 각 원소에 대해 mutate 연산을 수행한다
- 모든 epoch를 수행한 다음 역대 최고 점수를 가졌던 표만 기록된다
이 과정이 수행되면서 $3000$점을 넘는 표들이 보이기 시작했다. 아래는 Step 3의 결과를 기록한 표다.
| index | score |
|---|---|
| 1 | 3353 |
| 2 | 3098 |
| 3 | 3098 |
| 4 | 3063 |
| 5 | 3055 |
| 6 | 3186 |
| 7 | 3223 |
| 8 | 3016 |
궁극 목표인 유전알고리즘을 도입하기 전까지, 가능한 것들 중에서는 다 시도해본 것 같다. 하지만 3000점을 넘는다고 해서 얘네가 좋은 유전자를 가진 것인지 판단하기가 어려웠다. 유전알고리즘을 오래 돌리고 싶지는 않았어서, ‘굳이’ 유전알고리즘을 사용하지 않고도 최고점을 갱신할 수 있는 방법이 있을까 고민을 좀 더 해보기로 했다.
Step 4
점수 계산 방식을 다르게
max score : 3448
문제의 관점을 다르게 보고 점수 계산 방식을 변경해보았다. 어짜피 정답을 찾기 위해서는 $1$부터 $8140$까지의 모든 수를 읽어낼 수 있어야 한다. 즉, 점수를 “1부터 시작하여 읽어낼 수 있는 최대의 값”이 아니라, “1부터 8140까지 읽어낼 수 있는 수의 개수”로 점수 계산 방식을 변경해보는 것이다. 점수를 $8140$점 얻을 수 있는 표를 찾는 것이 궁극적인 목적이 되겠다.
실질적인 알고리즘은 Step 3와 같다. 점수 계산 방식만 다르게 진행하였다.
| index | secondary score | real score | Step 2 |
|---|---|---|---|
| 1 | 8107 | 1187 | 2338 |
| 2 | 8116 | 1008 | 3057 |
| 3 | 8112 | 1167 | 2275 |
| 4 | 8109 | 1047 | 2771 |
| 5 | 8111 | 1428 | 3448 |
| 6 | 8116 | 1121 | 2979 |
| 7 | 8106 | 1104 | 3002 |
| 8 | 8111 | 1124 | 2982 |
문제를 풀기까지 읽지 못하는 수가 30개 이내라는 사실을 알아냈다. 좋은 알고리즘을 사용한 것도 아닌데 이정도 읽어낼 수 있다는 사실이 놀라웠고, 저 30개를 읽어낼 수 있도록 표를 만드는 방법이 결국 문제에서 원하는 방향이라는 사실을 깨닫는 데까지는 오래 걸리지 않았다.
secondary score 하나만 사용하는 것은 오히려 독임을 깨달았다. 결과에서 보다시피, secondary score가 가장 좋은 2번이 오히려 실제 점수는 가장 낮았다. 다른 수들은 많이 읽을 수 있지만, 읽지 못하는 수들 중 가장 작은 값이 다른 index보다 더 적었다는 결과라는 것. 그래도 다른 수들을 많이 읽어낼 수 있도록 조정하는 것이어서, Step 2를 한번만 실행해도 높은 점수가 나오긴 했다.
Step 5
Step 3와 Step 4의 융합
max score : 4499
그럼 두 점수 계산법을 이용하여 번갈아 최적화하면 어떨까? 번갈아가며 최대 점수를 찾아나가게 된다면, “원래 점수도 늘리고 읽어나갈 수 있는 수도 최대화할 수 있지 않을까” 하는 생각에서 시작된 단계이다.
구현은 간단하다. Step 3와 Step 4가 이미 구현되어있으므로, 두 단계를 합치기만 하면 되는 것. mutate는 epoch 마지막에 한번만 실행되며, 실제 점수 기준점은 Step 3를 기점으로 잡았다.
순서는 Step 4 -> Step 3 -> mutate.
| index | score |
|---|---|
| 1 | 4409 |
| 2 | 3818 |
| 3 | 4455 |
| 4 | 4276 |
| 5 | 4333 |
| 6 | 4003 |
| 7 | 4405 |
| 8 | 4499 |
2024-06-23 추가
알고리즘에 문제가 있음을 알아냈다. Step 3부터 있었던 오류로, epoch를 한 번 진행한 후 표를 제대로 복사해주지 않아 원하는대로 알고리즘이 동작하지 않았다. 결과도 이상하게 출력되었다. 프로그램에서는 4499점을 얻은 표를 백준에 제출했더니 4477점을 받았다. 직접 점수를 계산하니 4477점인 것을 보아 표를 복사하는 타이밍이 문제였음을 알아냈다.
그럼 Step 3부터 모든 단계가 오류를 가지고 있다는 점을 의미하는 것이었다. 이전 단계는 사실 큰 의미가 없지만, Step 5의 결과는 Step 6에서 input으로 사용할 예정이었으므로 결과를 새로 도출하게 되었다.
| index | score |
|---|---|
| 1 | 4266 |
| 2 | 4459 |
| 3 | 4468 |
| 4 | 4285 |
| 5 | 4223 |
| 6 | 4427 |
| 7 | 4167 |
| 8 | 4004 |
Step 6
순열을 이용한 숫자 변환
max score : 4885
지금까지 얻은 표의 secondary score를 보면, $1$부터 $8140$까지의 수들 중 읽지 못하는 수가 30~40개 정도만 있다는 것을 알아냈다. 이를 통해 만들어낸 표가 어느 정도는 모든 수를 읽을 수 있는 경향성을 가졌다고 생각할 수 있겠다고 느꼈다. 즉, 숫자들이 어느 정도 잘 붙어있어서, 모든 수를 읽을 수 있도록 잘 산개해있다고 판단하게 되었다. 그러면 이 정도 숫자들이 잘 산개되어있는 것을 이용할 수 있는 방법이 없을까?
숫자의 분포는 잘 되어있다고 가정하면, 숫자들의 위치는 바꾸지 않고 값만 바꾸면 점수를 더 올릴 수 있지 않을까 고민해보게 되었다. 숫자를 바꿀 때, 같은 수였던 것들은 모두 다른 같은 수로 바꿔버리는 것이다. 예를 들면, 표 안에 있는 모든 $1$이 $4$가 된다거나, 모든 $0$이 $2$가 된다거나 하는 식으로 바뀌는 것이다. 다만 모든 수가 $0$으로 바뀌는 등의 문제가 생기면 안되기에, 모든 수가 각자 대응되도록 한가지 수로 바뀌어야한다고 생각했다.
그럼 사용할 수 있는 변환법이 있다. 백트래킹 등을 이용하여 $0$부터 $9$까지 모든 수가 1번씩만 등장하는 수열을 하나 만들고, 모든 수가 그 수열에 맞춰 변화하도록 하는 것이다. $0$부터 $9$까지 등장하는 수열을 ‘순열’이라고 한다는 듯 하다. 10개의 수를 순열로 세우는 방법은 총 $10! = 3628800$번, 생각보다 프로그램에서 돌릴만 한 숫자이다.
그래서 Step 5에서 얻은 결과를 Step 6의 input으로 사용해보았다.
| index | score |
|---|---|
| 1 | 4397 |
| 2 | 4497 |
| 3 | 4497 |
| 4 | 4333 |
| 5 | 4397 |
| 6 | 4438 |
| 7 | 4438 |
| 8 | 4497 |
점수의 변화가 크지 않는 것도 그런데, 완전히 다른 표가 점수가 똑같은 상황이 여러 번 발생했다는 점을 알아냈다. 4번을 제외하고는 끝자리가 $7$ 또는 $8$인 것으로 보아, 이 표들은 $8$과 $9$의 숫자가 부족하여 결과를 잘 얻지 못한 것이 아닌가 생각해보게 되었다. 그럼 그들의 개수를 조금 더 올려주어야하는데, 그걸 어떻게 해결해야할지가 다음 과제가 될 것 같다.
24-06-24 추가
Step 6에서 사용하는 방법은 총 3개다. 아래가 그 리스트.
- Secondary Score : $1$부터 $8140$까지 중 읽어낼 수 있는 수의 개수
- Score : 문제에서 제시한 점수 계산 방법. $1$부터 읽어낼 수 있는 연속된 수들 중 최댓값
- Permutation : 순열을 이용하여 숫자들의 분포를 깨지 않으면서 더 좋은 결과를 얻어보려는 시도 (점수 계산법은 아님)
여기서 나는 secondary score에 집중해보았다. $1$부터 $8140$까지의 수들 중 읽어낼 수 있는 수들의 개수. 즉 앞자리가 $0$에서 $7$인 숫자들은 $000$부터 $999$까지 고려해야만 좋은 점수를 얻을 수 있는 반면, 앞자리가 $8$인 숫자는 $000$부터 $140$까지만 고려하면 된다. 심지어 앞자리가 $9$인 숫자는 아예 고려 대상도 아니다. 그래서 $8$이나 $9$는 상대적으로 다른 숫자들에 비해 중요하지 않다고 판단되었을 수 있고, 이게 점수의 끝자리가 $7$이나 $8$이었던 경우가 많았던 이유이지 않을까 고민해보게 되었다.
이를 해결하기 위해, 모든 숫자에 대해 동일한 기여를 할 수 있도록 조절해야한다고 생각했고, secondary score의 점수 계산 체계를 바꾸게 되었다.
- Secondary Score : “$1000$부터 $9999$까지의 수들 중 읽어낼 수 있는 수의 개수” // $1000$부터인 이유는, $1$부터 $999$까지는 어짜피 읽지 못한다면 그 이후의 수들은 모두 못 읽어내기 때문에, 애초에 중요한 고려 요소가 아님!
이렇게 되면 Step 4부터 적용되던 secondary scoring의 전면 수정이 필요해졌다. 그래서 수정하게 되었다. 그리고 Step 5부터 다시 프로그램을 실행하고 그 결과를 기록하게 되었다. Step 4의 경우, secondary scoring이 제대로 동작하는지 확인하는 용도였기 때문에 패스.
| index | Step 5 | Step 6 |
|---|---|---|
| 1 | 4023 | 4393 |
| 2 | 3943 | 3987 |
| 3 | 4489 | 4489 |
| 4 | 3992 | 3992 |
| 5 | 4219 | 4498 |
| 6 | 4084 | 4486 |
| 7 | 4427 | 4438 |
| 8 | 4084 | 4885 |
24-06-26 추가
Step 6의 시간이 너무 오래 걸린다는 문제가 있었다. 한 번의 데이터에 대해 10~20시간이 소요되기도 했다. 기존에 사용하던 방법은 아래와 같다.
- 데이터를 읽고, 그 데이터의 숫자를
Permutation_value에 계산된 순열값으로 모두 변환하고 변환된 표에 대한 점수 계산을 실행한다
이렇게 되니, 총 $10! = 3628800$개의 표를 만들고, 그것들의 점수를 모두 계산하는 과정을 겪게 되며, 그래서 시간이 오래 걸리게 되는 것이라고 판단했다. 그래서, 1. 표를 재생성하지 않으면서 2. 점수 계산 함수도 재실행하지 않도록 Step 6을 조정할 필요성이 생기게 되었다.
일단 1번 목표를 해결하기 위해, 표를 만들 때 숫자들을 바꾸지 말고 점수를 계산할 때 인식되는 숫자들에서 변환이 일어나게끔 조정했다. 이미 순열에 대한 모든 경우에 대해 숫자들을 배열로 저장해두었기 때문에, 숫자를 변환하는 과정 자체는 $O(1)$이었고, 표를 만드는 과정을 제거할 수 있었다. 이에 따라 연산 횟수는 표를 만드는 과정에 쓰이는 연산 $8 \times 14 = 112$번을 줄일 수 있었고, 표의 메모리만큼을 절약할 수 있었다. 하지만 점수 계산 함수는 어쨌든 $10!$번 실행되고 있었고, 시간적으로는 절약하지 못했다. 점수 계산을 위해 실행되는 연산이 최소 5만번이 넘어갔기 때문. 그래서 점수 계산을 할 때, 읽었던 숫자들을 일반적인 숫자가 아닌 문자열 형식으로 읽었다고 여기고, 그에 따라 visit 체크 방식을 변경하였다. 그리고, 읽혀진 문자열에 대해서만 각 숫자들을 변환하여 new_score를 계산할 수 있었고, 결과적으로는 점수 계산 함수를 1번만 실행하여 모든 순열변환 표의 점수를 계산할 수 있었다.
하지만 new_score를 계산하는데도 아직까지 문제가 있었다. 개선한 알고리즘은 실행 시간을 10분 내외로 줄일 수 있었지만, 이것도 길다고 생각했다. 그래서 더 좋은 방법을 생각해보아야한다.
읽어내야할 수는 현재로써는 1만개지만, 점수 문자열의 길이는 최대 4이므로 사실 4만개의 칸에 대해 내가 이 문자열은 읽었다를 판별하여 변환을 진행하였다. 여기서 생각을 반전시켜보자. 점수 계산 함수는 ‘읽어낼 수 있는 4자리 수’가 대략 $46000$개 정도 되고, 더 짧은 수들은 더 많이 읽어낼 수 있으므로, 진위여부는 모르겠지만 읽어낼 수 있는 수가 읽지 못하는 수보다는 많겠다라고 생각해볼 수 있다. 그래서, 읽어낼 수 있는 수에 초점을 맞추는 게 아니라 읽지 못하는 수에 대해 초점을 맞춰볼 필요성이 있다.
그리고 이것이 효과가 뛰어났다! 10분 정도 걸리던 기존 방법에서, 단 30초 정도면 전체 순열에 대한 검사를 진행할 수 있게 되었다. 이정도면 Step에서 하나의 단계로도 사용할 수 있을 듯.
Step 7
지금까지의 모든 알고리즘의 총집합
max score : 5598
지금까지의 모든 단계를 이용하여 점수를 올릴 수 있는지 확인한다! 이 방법으로도 목표 점수를 채우지 못한다면, 실행하는 프로그램 자체를 바꿔야할 필요성이 생길지도 모른다.
Step 7.1
이 단계에서는 Step 2와 Step 6의 융합이다. 랜덤으로 생성된 표에 대해 하나의 수만 바꾸는 연산, 모든 순열에 대해 표를 변환하는 연산 2가지를 진행한다. 점수 계산 체계는 원래 문제에서 원하는 점수 계산 방식이다.
그런데 epoch 1~3번이면 최대에 도달해버린다! 지역해에 도달하는 횟수가 내 예상보다 빨랐다. 그래서 mutate를 추가하기로 하였다.
Step 7.2
mutate 개념은 Step 3에서 도입하였으니, 이 단계는 Step 3와 Step 6의 융합이 되겠다. 계산된 최대 점수가 같다면 mutate 확률을 2배 증가시켜 연산하는, 기존 방식을 그대로 채용하고 실행하였다.
결과는 8개의 프로그램이 대부분 최대 $3300$점대까지는 올라가는 것을 확인했다. 하지만 거기까지였다. epoch를 350까지 돌아보았지만 별다른 점수 증가를 보지 못했다. 다른 방법을 시도해보자.
Step 7.3
Step 6를 구현할 때, 요점을 “읽지 못하는 수를 최소화”해야함을 강조했다. 검사 시간을 줄이기 위해, 읽어낼 수 있는 수가 아니라 읽지 못하는 수에 중점을 두고 순열변환 연산을 진행시켰기 때문이다. 그래서 이번에는 Step 4와 Step 6의 융합이다. 읽지 못하는 수의 개수를 최소화하는 것이다.
결과는, $1000$부터 $9999$까지의 숫자들 중 약 30개 정도만 못 읽는 정도까지 표를 만들어낼 수 있었다. 다만 거기까지가 한계인 것처럼 보였다. 대부분 비슷한 결과까지만 도달하는 것으로 보아, 표본의 수를 꽤 많이 늘리거나, 완전히 다른 방식을 채용해야할수도 있겠다고 생각했다.
다음이 지금까지 내가 구현했던 방법들의 최종집이다.
Step 7.4
Secondary Scoring + 기본 Scoring + Permutation 변환 + mutate 변환. 이 모든 것을 총집합시켜 결과를 얻어내보도록 하자.
epoch 250정도까지 돌린 상태에서 최고 점수는 $4663$점. 사실 epoch를 더 돌리면 더 높은 결과가 나올 것 같긴 한데, 점수 개선 폭이 너무 낮았다. 심지어 점수가 계속 떨어지기도 했다. 다른 step들에서는 1000 epoch까지 실행했었는데, 이번 step에서도 최종장 느낌답게 1000 epoch까지는 돌려보기로 했다.
epoch 400 넘어갔을 때 최고점인 $4886$점의 데이터를 발견했다. 기존 최대 점수보다 $1$점 많다.
최종 결과로 $5598$점을 얻은 데이터가 나왔다.
Step 8
표본을 많이 탐색해보자
max score : 8189
지금까지는 하나의 프로그램이 1개의 matrix에 대해서만 연산이 가능했다. 총 8개의 프로그램을 동시에 실행했었으니, 총 8개의 grid만을 생성하고 그것들의 점수를 올리는 과정이었다. 아무리 랜덤성을 넣었다고는 하지만, 결국 탐색 공간 자체가 매우 좁다는 것을 알 수 있다.
그래서 탐색 범위를 최대한 늘려보려는 시도를 하게 되었다. 가능한 표의 수는 $10^{8 \times 14}$이므로 죄다 돌려보겠다, 어느 정도는 돌려보겠다 하는 망상은 일찍이 접도록 하자. 결론적으로 만든 단계는 아래처럼 진행된다.
- 각 grid를 저장할 수 있는 DB를 만들었다. //
size= $50$- DB : 각 grid와 그에 대한 score를 저장
- 특성
- DB의 모든 grid는 점수가 높은 순으로 정렬되어있다.
- DB에 존재하는 모든 grid는 점수가 다르다.
epoch만큼 반복한다. (epoch의 제한은 따로 두지 않았다. 이론상 무한반복)- grid 지정 단계 (어떤 grid를 사용할 것인가?)
- optimize 단계 (grid에서 점수를 더 늘릴 방안이 있는가?)
- DB 갱신 단계 (DB에 저장할 정도로 유망한 정보를 가졌는가?)
- 절차
- 현재 grid가 DB의 존재하는 grid들 중 점수가 같은 grid가 있다면, DB의 grid를 현재의 grid로 대체한다
- 현재 DB에 존재하는 grid들 중 점수가 가장 낮은 grid를 $A$라고 할 때, optimize를 마친 현재의 grid가 $A$의 점수보다 높다면 $A$를 제거하고 현재의 grid를 넣는다
- 현재 grid가 $A$의 점수보다 낮다면 DB 수정을 하지 않는다
- DB 갱신을 총
DB_RENEW_THRESHOLD만큼 하면 epoch를 종료한다. //DB_RENEW_THRESHOLD= $20$
- 절차
이 과정에서 optimize 단계를 업데이트해가며 더 좋은 점수를 얻을 수 있도록 진행하였다.
Step 8을 만든 목적은 “grid를 최대한 많이 만들고 관리할 수 있도록” 하기 위해서였다. 실제로 이전 step들보다 더 많은 탐색을 진행하는 것을 확인하였다.
Step 8.1
max score : 3979
이 단계에서 사용한 optimize는 Step 2와 같다.
- 현재 가진 grid에서 숫자 하나만 바꾸어 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다.
IF더 좋은 결과를 가져오지 못한다면 탐색을 종료한다.
탐색을 종료하는 이유는 grid가 지역해에 빠졌다고 판단해서다. 실제로 Step 2의 역량으로는 그 지점으로부터 빠져나올 방법이 없다. Step 3에서 만든 mutate 방식이 있지만, Step 8부터는 최적화 랜덤성은 최대한 제거하고싶었다. 그래서 생각해낸 방법이 숫자 2개를 바꾸는 방법이었다. Step 2의 경우 숫자 하나만 바꾸므로, 그것보다 많은 수를 한 번에 바꾸게 된다면 지역해를 빠져나올 수 있다고 판단했다. 그래서 임의로 2곳을 지정하고 원래 값과는 다른 랜덤한 값으로 변경하도록했다.
사실 Step 8은 substep을 만들 생각이 없었다. 하지만 어느 순간부터는 epoch를 계속 돌아도 항상 점수가 낮아지는 상황이 발생했다. DB 안에 있는 데이터들이 대부분 지금 방법으로는 점수를 올릴 수 없는 상황이라고 판단했다. 그래서 optimize를 계속 업데이트해야함을 깨닫게 되었다.
Step 8.2
max score : 5004
이 단계에서 사용한 optimize는 Step 4와 같다. Step 3는 랜덤성이 짙은 mutate 방식이라 사용하기 꺼려졌었다.
- Step 4 :: 현재 가진 grid에서 숫자 하나만 바꾸어 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다.
- 점수 계산 방식 : $1000$ ~ $9999$까지 읽을 수 있는 수의 총 개수
IF더 좋은 결과를 가져오지 못한다면 반복을 종료한다.
- Step 2 :: 현재 가진 grid에서 숫자 하나만 바꾸어 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다.
- 점수 계산 방식 : $1$부터 읽어낼 수 있는 연속적인 수의 최댓값
IF더 좋은 결과를 가져오지 못한다면 탐색을 종료한다.
Step 8.1에서 얻은 DB와 Step 8.2에서 새로 만들게된 DB의 점수 차이가 8점이다. 하루정도 돌려서 epoch를 100개 정도 보는데, 이미 만들어진 표들은 이전 policy에 너무 국한되어 점수 증가하는 속도가 매우 더뎠다. 표를 새로 만든 Step 8.2에서 점수를 앞지르는데 얼마 걸리지도 않았었다. 그래서, 시스템이 가능하다면 각 Step마다 DB를 하나씩 더 만들어야겠다고 생각하게 되었다.
Step 8.3
max score : 4954
이 단계에서 사용한 optimize는 Step 6과 같다. 순열을 이용하여 점수를 더 올려보자.
- Step 6 :: 현재 가진 grid에서 순열변환을 통해 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다
- 점수 계산 방식 : $1000$ ~ $9999$까지 읽을 수 있는 수의 총 개수
- Step 4 :: 현재 가진 grid에서 숫자 하나만 바꾸어 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다
- 점수 계산 방식 : $1000$ ~ $9999$까지 읽을 수 있는 수의 총 개수
IF더 좋은 결과를 가져오지 못한다면 반복을 종료한다
- Step 6 :: 현재 가진 grid에서 순열변환을 통해 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다
- 점수 계산 방식 : $1$부터 읽어낼 수 있는 연속적인 수의 최댓값
- Step 2 :: 현재 가진 grid에서 숫자 하나만 바꾸어 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다
- 점수 계산 방식 : $1$부터 읽어낼 수 있는 연속적인 수의 최댓값
IF더 좋은 결과를 가져오지 못한다면 반복을 종료한다
DB를 여러개 만들어서 실행하기 위해 코드를 수정하는 과정에서 이전 DB를 모두 날려버렸다.. 그래서 이 단계부터 DB를 하나 다시 만들어서 결과를 얻었다.
그런데… 이게 생각보다 효과가 좋지 않았다. 최고점이 $4954$점이었다. 각 step이 너무 오래 걸리기도 했고, step이 과도하게 크다고 생각이 들어서 아래와 같이 수정했다. (Step 6.-1 에서 썼던 방법이다)
- Step 4 :: 현재 가진 grid에서 숫자 하나만 바꾸어 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다.
- 점수 계산 방식 : $1000$ ~ $9999$까지 읽을 수 있는 수의 총 개수
IF더 좋은 결과를 가져오지 못한다면 반복을 종료한다.
- Step 6 :: 현재 가진 grid에서 순열변환을 통해 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다.
- 점수 계산 방식 : $1$부터 읽어낼 수 있는 연속적인 수의 최댓값
- Step 2 :: 현재 가진 grid에서 숫자 하나만 바꾸어 더 좋은 결과를 가져올 수 있다면 그 결과를 선택한다.
- 점수 계산 방식 : $1$부터 읽어낼 수 있는 연속적인 수의 최댓값
IF더 좋은 결과를 가져오지 못한다면 반복을 종료한다
그리고 DB 갱신을 위한 threshold를 $10$으로 수정했다.
그런데… 이게 생각보다 효과가 없었다. DB의 최고점이 갱신되지 못했다. 순열 기능의 쓰임새가 사실상 무의미하다고 결론내리게 되었다. Step 8에서 최종적으로 내린 결론은, 8140점을 넘는 grid를 찾는 것이 목적이 아니라 “유망한 grid를 찾는 것이 목적”.
Step 8.4
max score : 8189
유망한 grid를 더 많이 탐색하기 위해, 기존 epoch 시간을 줄이면서 Step을 간소화시켰다. 그리고 최대한 많이 탐색하는 것을 목적으로 오랫동안 프로그램을 실행시켰다.
Step 8.2로 다시 복귀했다. 그리고 그냥 무작정 반복을 시작했다. 그렇게 얻은 최고점은 Program 2에서 $6099$점이었다. 하지만 무작정 반복하더라도 어느 순간부터는 점수가 올라가지 않았었다. 그래서 이때 DB에 존재하는 데이터들을 모두 순열화 변환을 시켰다. 그 때 얻은 최고점은 $6445$점. 그리고 변환된 데이터를 또 다시 Step 8.2의 반복에 넣어버렸다.
DB들의 모든 점수가 $4500$점은 가뿐히 넘어버렸기 때문에, random grid를 생성하는 것은 의미가 없다고 판단하고 관련 기능을 비활성화하였다.
아래가 이 step의 진행도를 정리한 것이다.
- 1차 step 최고점 : $6099$
- 순열화 최고점 : $6445$
- 2차 step 최고점 : $7108$
- 순열화 최고점 : $7658$
우리의 목표는 결국 점수를 8140점 이상 얻는 것이 목적이다. 우리가 중점적으로 봐야 할 것은 secondary score가 아닌 first score. 이전 step들은 두개를 모두 올려가는 것이 좋다고 판단했지만, 이정도까지 왔다면 score를 조금만 더 올려서 합격점을 찾겠다는 목표를 세우게 되었다. 그래서, 기존 epoch에서 secondary scoring을 빼고 first score만을 최적화하는 방법으로 나아가기 시작했다.
결국 이 방법으로 $7666$점, $7757$점 등을 얻어가며, 현 시점의 최고 점수는 $7996$점이다. 얼마 남지 않았다.
그리고 같은 방법으로 마침내, $8189$점을 얻으면서 문제를 해결할 수 있었다. 최적화도 해야하고 1만점을 목표로 해보고 싶지만 일단 보류.
- 참고 알고리즘 :
코드
사용 언어 : C
최종 수정일 : 2024 / X / X
1