플로우차트

Mandatory

Bonus

인자값

1

./push_swap 4 2 1 3 5

인자가 입력된 순서대로 스택 A에 저장한다.

즉, 가장 먼저 들어온 인자는 스택 A의 맨 밑에, 가장 나중에 들어온 인자는 스택 A의 맨 위에 위치한다.

자료구조

스택을 구현하기 위해 원형 양방향 연결 리스트를 사용했다.

스택의 상단 뿐만 아니라 하단으로도 접근하여 연산횟수의 최소화를 이루고자 했다.

특히, 이번 과제에서는 모래시계 알고리즘을 사용했기 때문에 하단에 위치한 원소를 빠르게 상단으로 올릴 필요가 있었다.

스택 A에서 스택 B로 옮기기

인덱싱

인자로 들어온 원소들의 값을 인덱스 값으로 바꾼다.

예를 들어, 인자로 5 2 99 0 가 들어왔다면, 2 1 3 0 과 같이 바꾸는 것이다.

인덱스 값으로 바꾸는 이유는 스택으로 넘겨야 할 순서를 명확하게 정하기 위함이다.

인덱스로 변환하는 작업은 정렬 알고리즘을 사용하면 되는데, 이번 과제에서는 퀵 정렬을 사용했다. 퀵 정렬은 평균 시간 복잡도가 $n\ log_2n$ 이기 때문에 빠른 연산을 위해 사용했다.

모래시계 알고리즘

모래시계 알고리즘이란 push_swap 과제를 수행하기 위해 사용하는 특수한 알고리즘이다.

스택 A에 저장된 원소들을 스택 B로 옮겼을 때 큰 값들은 스택의 양 끝에 위치하고, 작은 값들은 스택의 중앙에 위치한 모습이 모래시계 모양과 비슷해서 모래시계 알고리즘으로 불리고 있다.

모래시계 알고리즘을 사용하는 이유는 연산횟수를 크게 줄일 수 있기 때문이다.

스택 B에서 스택 A로 값을 넘길 때, 스택 B의 상단과 하단에서만 값을 찾기 때문에 상대적으로 연산을 적게한다.

위와 같이 모래시계가 아닌 형태에서는 연산을 총 3번 수행한다.

한편, 모래시계 형태에서는 다음으로 넘겨야 할 수가 스택의 상단에 위치한다면 연산을 한번만 수행한다.

또는 스택의 하단에 위치해도 모래시계 형태가 아닐 때보다 연산 횟수가 상대적으로 적어진다.

정렬해야 하는 수가 더 많아진다면 모래시계 형태에서는 연산 횟수는 더욱 많이 줄어들 것이다.

구간을 나누기 위한 chunk

스택 A에서 스택 B로 넘길 때 스택 B가 모래시계 구조를 유지하기 위해서 chunk(덩어리)를 사용한다.

chunk는 숫자를 일정 구간으로 나누어주는 역할을 한다.

위의 그림처럼 가운데를 중심으로 대칭을 이루며 일정 구간에 속한 숫자들이 분포하도록 스택 A에서 스택 B로 원소들을 넘겨주기 위해 chunk를 사용한다.

나중에 스택 B에서 스택 A로 원소들을 옮길 때, 스택의 상단과 하단 근처에 넘겨야 하는 값들이 위치하도록 하는 것이 핵심이다.

다만, 숫자의 개수에 따라서 chunk의 값을 적절하게 조정해주어야 한다.

chunk가 작으면 일정 구간에 있는 숫자들의 편차가 작아지면서 정밀한 모래시계 모양이 만들어지지만, 연산 횟수가 증가한다.

아래의 사진은 300개의 숫자에 대해 chunk를 5로 설정한 결과이다.

반대로 chunk가 과도하게 크면 숫자들의 편차가 커지면서 모래시계 모양이 엉성하게 만들어진다.

아래의 사진은 300개의 숫자에 대해 chunk를 150으로 설정한 결과이다.

그리고 아래의 사진은 동일한 숫자 300개에 대해 chunk를 25개로 설정한 결과이다.

chunk가 과도하게 큰 경우보다 촘촘하지만, 과도하게 작은 경우보다는 약간 엉성한 모양을 띄고 있다.

하지만, 연산 횟수는 다른 경우보다 가장 적은 것으로 나왔다.

chunk에 따른 연산 횟수는 다음과 같다.

즉, 이를 통해 숫자의 개수에 따라 적절한 chunk를 설정해주어야 연산 횟수를 최소화 할 수 있다는 것을 알 수 있다.

그렇다면 적절한 chunk를 어떻게 구할 수 있을까?

우선, 직접 값을 넣어가며 귀납적으로 구하는 방법이 있다.

하지만 이미 과제를 구현하신 분들께서는 아래와 같은 방정식을 구하셨다.

위의 식을 이용하면 숫자 x 개에 따라 적절한 chunk y 를 구할 수 있다.

구현

num은 현재 스택 A에 남아있는 가장 작은 수라 해보자. 실제 값들을 인덱스로 바꾸었기 때문에 num은 0부터 시작한다.

현재 스택 A의 상단에 있는 값을 top이라 하면, 다음과 같은 규칙을 적용한다.

top ≤ num

top이 num보다 작거나 같다는 것은 스택 B의 중앙에 위치해야 한다는 의미이다.

그렇기 때문에 바로 스택 B로 넘긴다.

top > num && top ≤ num + chunk

top이 num보다 크고, num + chunk보다 작거나 같다는 것은 스택의 중앙보다는 조금 더 위에 있거나 밑에 있어야 한다는 것을 의미한다.

그래서 스택 B로 보낸 다음 rb를 수행해서 스택의 양쪽으로 큰 값들이 위치하도록 한다.

만약, rb를 수행하지 않으면 모래시계 모양이 형성되지 않는다.

top > num + chunk

top이 num + chunk보다 크다는 것은 스택 B로 넘겨야 하는 값이 아니라는 의미이다.

그래서 ra를 수행해서 다른 값을 top으로 올리는 것이다.

최악의 경우

하지만 위와 같이 구현한다면 다음과 같은 케이스(526개)에 대해서는 성능이 좋지 않다.

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를 수행해서 연산 횟수가 크게 증가했다. (연산 횟수 : 7414번)

임의의 숫자 500개에 대해서 수행했을 때 평균 5000번인 것에 비하면 성능이 좋지 않다는 것을 알 수 있다.

성능 개선

성능을 저하시키는 원인은 top > num + chunk 인 경우에 ra 만 수행하기 때문이다.

만약 다음으로 넘길 숫자가 스택의 하단에 있다면 ra 가 아닌 rra 를 수행하면 연산 횟수를 줄일 수 있을 것이다.

그래서 스택의 상단 또는 하단에서 top <= num + chunk 이 되는 지점을 찾아서 해당 지점까지 rra 또는 ra 를 해주는 것으로 해결했다.

의사 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10

while (스택의 상단에서 num + chunk보다 같거나 작을 때 까지)
	상단 개수 += 1
while (스택의 하단에서 num + chunk보다 같거나 작을 때 까지)
	하단 개수 += 1
if (상단 개수 < 하단 개수)
	while (상단 개수만큼)
		rra(a)
else
	while (하단 개수만큼)
		ra(a)

덕분에 약 2배 정도 연산 횟수를 줄일 수 있었다. (연산 횟수 : 3925번)

과연 정말 최적화가 된 것일까?

최악의 경우에 대해 rra 도 함께 사용하도록 알고리즘을 바꾸면 다른 케이스들에서 평균 연산 횟수가 약 20% 증가하는 trade-off 관계를 발견했다.

즉, 오히려 ra 만 수행했을 때 연산이 더 적었다는 것이다.

평균적인 케이스와 최악의 케이스를 모두 잡기 위해 사용할 수 있는 최적의 알고리즘은 찾기 어려웠다.

이를 해결하기 위해 스택 A에서 스택 B로 넘기는 방법 2가지를 모두 시뮬레이션 해보고, 더 적은 연산을 수행하는 경우를 선택하는 그리디 알고리즘을 적용했다.

2가지 경우에 대해 모두 연산을 수행하다보니 시간 복잡도는 많이 증가했지만, 과제에서 요구하는 성능을 충족시키기 위해서는 최선의 선택이었다.

스택 B에서 스택 A로 옮기기

모래시계 모양으로 정렬된 스택 B에서 스택 A로 옮기는 것은 간단하다.

상단과 하단 중에서 스택 B에서 가장 큰 수를 찾아서 rb 또는 rrb 를 수행한 다음 pb 를 수행하면 된다.

보너스

보너스는 Mandatory를 잘 마쳤다면 수월하게 해결할 수 있다.

보너스는 Mandatory에서 실행한 결과로 스택 A에 정렬이 잘 되었는지, 스택 B에 남은 원소는 없는지 판단하는 checker 를 만드는 것이다.

Mandatory에서 만든 파일을 아래와 같이 실행하면 수행한 연산들이 출력되는데, 이 연산들을 그대로 수행해서 결과를 확인하면 된다.

1
2
3
4
5
6
7
8
9

./push_swap 4 5 1 3 2
ra
ra
pb
ra
pb
rra
pa
pa

push_swap 실행 결과는 stdout 으로 출력되는데, checker 는 파이프를 통해 이 결과를 get_next_line 함수를 사용해서 받아오면 된다.

이 부분에 대해서는 file descriptor 를 이해하면 금방 해결할 수 있으므로 자세한 설명은 생략한다.

회고

최고의 알고리즘은 없다.

데이터를 효율적으로 정렬하기 위해 수 많은 알고리즘이 존재하며, 자료구조도 많다.

문제를 해결하기 위해 어떤 알고리즘을 적용하면, 다른 알고리즘의 장점이 상쇄되는 trade-off 상황을 자주 접했다.

결국 알고리즘은 어떤 문제를 해결하기 위해 고안된 방법론 중 하나일 뿐, 모든 문제에 적합하다고는 할 수 없는 것이다.

문제에 맞는 알고리즘을 사용하되, 여러 제약 조건 중에서 포기할 수 있는 것과 포기하면 안되는 것을 선택하는 것이 중요하다는 것을 배웠다.

정석은 없다.

사실 이 과제를 모래시계 알고리즘으로 해결하는 것에 대해 일종의 죄책감 내지는 불편함을 느끼고 있었다.

퀵 정렬이나 병합 정렬 같이 널리 알려진 정렬이 아닌 이 과제에만 적용할 수 있는 모래시계 알고리즘을 쓴다는 것이 약간 편법처럼 느껴졌기 때문이다.

하지만, 문제 하나를 해결하기 위해 정답은 여러 개가 있을 수 있는 것이기 때문에 이에 대한 불편함은 내려놓기로 했다. 어차피 모래시계 알고리즘을 구현하기 위해서 전처리 과정에서 퀵 정렬을 사용했으니, 어느 정도 과제의 목표를 달성한 것 아닐까 싶다.

대신, 모래시계 알고리즘이 왜 문제를 해결하는데 효율적이며, 내부적으로 어떻게 작동하는지 이해하기 위해 노력했다.

그리고 최악의 케이스를 해결하기 위해 그리디 방식으로 연산이 적은 횟수를 택하도록 했다.

어찌보면 이 과제를 해결하기 위해 퀵 정렬, 모래시계 알고리즘, 그리디 3가지 방식을 적용한 셈이다.

함께하면 금방 한다.

push_swap은 2서클 과제에서도 수문장으로 소문난 과제였기에 두려움이 앞섰다.

하지만, 운이 좋게도 so_long 과제에 이어 이번 과제도 마음이 맞는 동료들과 함께 페어 프로그래밍을 하며 과제를 진행했다.

오프라인으로 모이기 어려운 상황이라서 주로 온라인으로 진행했는데, 보너스까지 구현하는데 약 2주 정도 소요되었다.

매일 스터디를 하지는 않았지만, 시간이 맞을 때마다 모여서 문제를 해결하니 혼자 과제를 할 때보다 훨씬 많은 것을 배울 수 있었다.

조건문에서 부등호 방향을 반대로 하거나, 변수 초기화를 안해서 생기는 에러를 동료가 빠르게 발견해준 덕분에 시간을 절약할 수 있었다.

이 자리를 빌어 함께 고생한 동료들에게 감사하다는 인사를 전한다.