push swap 문제와 해결 알고리즘 복잡도 증명

push_swap 문제

양방향 스택 자료구조 a와 b가 주어진다. 처음에 겹치지않는 숫자 n개가 무작위로서 스택 a에 존재한다. 그럼 아래 주어진 operator만을 이용해 스택 a가 위에서부터 오름차순이 되도록 정렬하는 문제이다

sa: swap a - a의 가장 위에 있는 두 요소를 교환한다.
sb: swap b - b의 가장 위에 있는 두 요소를 교환한다.
ss: sa와 sb를 동시에 수행한다.
pa: push a - b의 가장 위에 있는 요소를 a의 가장 위에 넣는다.
pb: push b - a의 가장 위에 있는 요소를 b의 가장 위에 넣는다.
ra: rotate a - a의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막 요소가 된다.
rb: rotate b - b의 모든 요소를 1만큼 위로 이동시킨다. 첫 번째 요소는 마지막 요소가 된다.
rr: ra와 rb를 동시에 수행한다.
rra: reverse rotate a - a의 모든 요소를 1만큼 아래로 이동시킨다. 마지막 요소는 첫 번째 요소가 된다.
rrb: reverse rotate b - b의 모든 요소를 1만큼 아래로 이동시킨다. 마지막 요소는 첫 번째 요소가 된다.
rrr: rra와 rrb를 동시에 수행한다.

알고리즘

(제 머리에서 나온것이 아닌 다른 외국인의 코드를 직접 읽으면서 알아낸 알고리즘 입니다)

1. 전처리 인덱싱

만약에 인풋이

1 88 2 33 99

가 들어온다면

실 자료구조에서는 숫자가

0 3 1 2 4 가 되도록 인덱싱을 합니다.

push_Swap는 실제로 값을 알필요가 없습니다 값간의 대소비교만 명확하면 내부에서 어떤 수를 사용해도 상관이없습니다

2. swap

큰틀에서 swap 방식은 다음과 같습니다.

가 : 스택 a에 있는 값을 모두 다 b로 넘깁니다.

나 : 스택 b에 있는 모든 값을 a로 넘깁니다. 이때 가장 큰 값을 스택 top으로 올려서 큰 값부터 넘깁니다 그러면 자연스레 정렬이 되면서 넘어갑니다.

다 : 정렬 끝.

가. 세부 규칙

num의 값을 0이라 하고 chunk 라는 상수가 15 (전체 size 가 500개일 때는 30)로 임의로 정합니다

당연하겠지만 chunk 값은 size에 비례해 효율의 값이 다르지만 이 식을 구체적으로 알아내지 못했습니다.이 공식을 찾아 알아보는 것은 어떨까요?

top의 값을 다음의 세 구간으로 구분하여 처리합니다.

top이 num보다 작을때 넘기고 , num + chunk 사이일때만 B로 넘기고 한번 뒤집고 num + chunk 보다 클때는 B로 넘기지 않습니다

png

500개를 a를 넘긴 후

나 : b의 큰값부터 a로 차례로 넘기면 된다.

실제 chunk 구해보기

실제로 돌려보면서 size당 적당히 잘 되는 chunk는 다음과 같다.

100 15
500 30
1000 45
2000 65
5000 150

이걸 hmoon님이 식을 직접 풀어오셨다.

png

\[y = 0.000000053 x^2 + 0.03 x + 14.5\]

정도가 적당할 것으로 예상

최악의 경우 시간복잡도

chunks 수를 k라하자

‘나’의 작업을 먼저 고려하자면 최대 $2kn + n$이다.

한 숫자를 최상단에서 올리는 최악의 작업은 $2k$이고 이를 모든 n에 대해서 pa를 한번씩 수행한다.(실제로 2kn 작업횟수로 일어나는 케이스는 없는데 일단 느슨하게 잡았다.)

‘가’의 작업은 조금 나눠서 생각해보자.

일단 모든 n을 b로 한번씩만 넘기므로 pb의 작업횟수는 n이다.

이 중 pb후 rb를 하는 경우는 최대 n번이다. 이를 $\alpha$라 했을때

a에서 숫자를 골라서 넘기는 최대 작업은 $n + \alpha (\alpha <= n)$ 이다.

그럼 남은 작업은 ra를 하는 경우이다.

이것이 가장 큰 영향을 받기 위해서는 a 스택이 ra를 하는 경우에 가장 큰 영향을 받는다.

그럼 이때 a 스택이 ra를 가장 많이하는 최악의 경우를 생각해보자.

그럼 전체 a스택에서 0~k 구간이 가장 끝에 있는 경우라 할 수 있다.

그럼 0 ~ k구간 앞을 모두 ra를 한후에 0 ~ k를 push b를 할 것이다.

예를들어 526개의 경우 k = 30일때

496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

이런 순서가 ra를 가장 많이하는 최악의 경우의 수가 될 것이다.

참고로 이때 모두 첫번째 경우에만 해당하기에 rra를 하는 경우가 없고 b가 역정렬이 되어있는 상태이기에 b에선정확히 500번만 작동하기에 해당 알고리즘에서 가장 느린 케이스라고 할 수는 없다.

하지만 일단은 ra의 최악의 경우 시간복잡도를 구하는 거이기에 b의 $O(n)$의 상황은 일단 무시한다.

이럴때 최대 작업횟수를 구하면

\[\sum_{i = 1} ^{n/k} (n - ik) = \frac{n^2}{k} - k * \frac{1}{2} * \frac{n}{k} *\frac{n + k}{k} = \frac{n^2}{2k} - \frac{n}{2}\]

전체 시간복잡도는

\[\frac{n^2}{2k} - \frac{n}{2} + n + 2kn + n\]

.따라서 최고차항이 2차식이기에 $O(n^2)$이 된다.

여기에서 해당 식을 미분해서 k에 대해 정리하면 k에대한 2차식이나온다 여기서 나오는 k값이 전체 연산을 최소로하는 chunk 상수값이 된다. 하지만 일반적으로 $\alpha$ 값이 불확실하며 추가적으로 최악의 케이스는 현실성이 없는 상황이라 정확한 값을 구하기가 힘들다.

500개일때 총 ra의 횟수는

int num = 500;
const int chunk = 30;
int sum = 0;
for (int i = 1; chunk * i <= num; i++)
{
    sum += num - chunk * i;
}
cout << sum;

3920회이고

pa까지하면 총 4420 회 전체 push swap 수행작업은 4920회가 된다.

최선의 시간복잡도.

ra가 없는 경우가 최고의 시간복잡도가된다. 이는 당연히 정렬이 되어있는 경우이고 (참고로push_swap은 정렬되어있는 상태에서 작동하지않는것이 보장되어있다) ra는 작동하지않기에 최선의 시간 복잡도는 $O(n)$이다

평균시간복잡도 계산.

아까와 같이

ra의 최소 시간복잡도는 $O(n)$은 아닐거라 예상하고 앞과 마찬가지로 b의 $O(n)$의 상황은 일단 무시한다.

가 연산중 rb를 하는 연산을 제외한 나머지 평균 연산을 구하는것은 다음의 상황과 같다고 볼 수 있다.

보이지 않는 주머니에 공 n개중 빨간생 공 k개가있고 파란색 공 n - k 개가 있다. 이때 처음 빨간색 공을 뽑는 횟수의 평균이 알고 싶다.

첫번째 시도에서 빨간색 공을 뽑을 확률은

\[\frac{k}{n}\]

이다.

이때 공이 파란색이고 공을 다시 주머니에 넣지않고 다음색공을 뽑을 때, 빨간색 공일 확률은

\[\frac{n - k}{n} * \frac{k}{n-1}\]

이다.

n이 k보다 충분히 크다고 하자. n이 k보다 작을때는 각 상황은 무조건 n번 일어난다.

이때 n이 k보다 클때 평균 연산을 구하면 다음과 같다.

\[\frac{k}{n} + \sum_{\alpha = 0}^{n - k - 1} \left( \frac{k}{n} \left( \prod_{x = 0}^{\alpha}\frac{n - k - x}{ n - x} \right) \right)\]

이 사건의 평균 연산은 뽑은 공이 빨간색이 아닐때 주머니를 다시 넣고나서 다시 뽑는 상황인(독립) 초기하분포의 평균연산보다 크기에 해당 사건의 상한을 제공해 줄 수 있다.

기하분포의 평균은 $\frac{n}{k}$이다

\[\sum_{\alpha = 0}^{n - k - 1} \left( \frac{k}{n} \left( \prod_{i = 0}^{\alpha}\frac{n - k - i}{ n - i} \right) \right) + \frac{k}{n} \le \frac{n}{k}\]

특정 x일때의 평균 연산은 $\frac{n-x}{k}$ 이 되고 전체 연산은

\[\sum_{n = 0}^{N-k} \frac{N-n}{k} + \sum_{i = 1}^{k} i\]

이 된다.

따라서 $O(n^2)$

하한은 최선일때로 갈음하고 추가 증명은 생략.

따라서 $\Theta(n^2)$

Posted 2022-04-15

42seoul