가희가 개최한 코딩 테스트에 나온 상대속도에 대한 이야기

 안녕하세요. 조가희입니다. 최근에 가희와 함께하는 코딩 테스트 1회와 2회를 개최하였습니다. 이 중에서, 제일 잘 했다고 생각하는 것 중 하나는 1회에서 나온 상대 속도의 개념을 2회에 똑같이 연계했다는 점이였습니다. 그리고 21773번을 출제자인 제가 왜 물리 카데고리로 분류했는지 이유도 같이 설명해 보겠습니다.

 

---

 상대 속도는, 관찰자가 보았을 때 물체의 속도를 의미해요. 예를 하나 들어보겠습니다.

 

 

 저는 동쪽으로 1초에 1m씩 가고 있습니다. 차는 1초에 20m씩 서쪽으로 오고 있습니다. 하나씩 구해 볼게요. 제가 보았을 때, 차는 어떻게 오는 것처럼 보일까요? 먼저 이 때, 제 동쪽으로 21m 떨어진 거리에 차가 있었습니다. 1초 후에는 어떻게 될까요?

 

 

 차는 저랑 같은 위치에 있습니다. 제가 보면, 차는 서쪽으로 1초에 21m씩 가는 것 처럼 보입니다. 뭔가 상대 속도는 저를 기준으로 했으니까, 차의 속도에서 제 속도를 뺀 거 같은 느낌이 드네요. 또 다른 예를 들어보겠습니다.

 

 

 저는 동쪽 방향으로 초당 1m씩 이동하고, 차는 동쪽 방향으로 20m씩 이동합니다. 제가 보았을 때, 차는 어느 방향으로 초당 몇 m씩 이동하는 것으로 보일까요? 제일 쉬운 방법은 1초 후의 상황을 그리는 것입니다.

 

 

 1초 후에, 동쪽으로 차는 19m만큼 멀어졌습니다. 차의 속도에서 제 속도를 뺀 겁니다. 차에 있는 관찰자가 보았을 때, 저는 서쪽으로 19m만큼 멀어졌습니다. 제 속도에서, 기준점인 차의 속도를 뺀 셈입니다. 결국 상대 속도는 기준점이 핵심인 셈입니다. 이제, 21773번 문제를 봅시다.

 

---

 21773번 문제는 아래와 같은 문구가 있습니다.

 

 무슨 이야기일까요? 나머지 프로세스들 갯수의 최댓값은 99999이므로, 얘네들의 우선 순위 모두를 1 상승시키면 시간초과를 면할 수 없을 겁니다. 어떻게 해야 할까요? 이 때 상대 속도의 개념을 적용시킬 수 있어요. 두껍게 칠한 좀 큰 격자 하나가 1 by 1 정사각형이라 합시다.

 

 

 보라색으로 표시한 것이 선택된 프로세스라 해 봅시다. 1초 후에는 선택되지 않은 프로세스들의 우선 순위가 1 높아진다고 했습니다.

 

 

 그렇다면 그림은 이렇게 될 겁니다. 정지된 보라색 입장에서 보면, 갈색들은 어떻게 이동하는 것처럼 보일까요? 동쪽 방향을 +, 서쪽 방향을 -라고 하면, +1만큼 이동하는 것처럼 보일 겁니다. 그런데 갈색들이 최대 10^5 - 1개이므로, 얘를 기준으로 보면 안 됩니다. 대신에, 우리는 우선 순위가 계속 1씩 증가하는 프로세스를 기준으로 볼 수 있습니다.

 

 

 굵은 선을 1이라고 합시다. 갈색을 기준으로 보면, 보라색은 처음에 4만큼 떨어져 있었어요. 1초 후에는 어떻게 되나요?

 

 

 보라색은 + 방향으로 3만큼 떨어져 있어요. 보라색이 서쪽으로 1만큼 온 것처럼 보입니다. 따라서, 21773번 문제는 스케쥴러가 선택하지 않은 프로세스들의 우선순위를 +1씩 증가시키는 것이 아니라, 스케쥴러가 선택한 프로세스 하나의 우선순위를 -1씩 증가시키면 됩니다.

 

---

 정확하게 이 개념을 연계한 문제가 2회 때 가희와 btd5, 가희와 거북이 인형이였습니다. 이 중에 가희와 btd5는 21773번과 유사하게 생각하면 쉽게 풀릴 것이니, 가희와 거북이 인형 문제인 22237번 문제를 보겠습니다. 거북이 인형을 이루는 컴포넌트는 문제 조건상 최대 10^6 - 1개만큼 올 수 있고, 장애물은 20개, 집은 1개만 올 수 있어요. 여기서 우리가 파악해야 할 것은 10^6 - 1보다는 20, 1이 매우 작다는 것입니다.

 

 그러므로, 거북이 인형이 특정 방향으로 움직였을 때, 거북이를 기준으로 집이나 장애물이 상대적으로 어떻게 오게 되는지를 봐야 합니다. 거북이가 동쪽으로 1칸 이동했다 해 봅시다.

 

 

 이동한 후에는 이렇게 될 겁니다. 거북이 기준에서 보았을 때는, 집은 동쪽의 반대 방향인 서쪽으로 오는 것처럼 보입니다. 왜요? 집은 고정되어 있었고, 기준점이 되는 거북이는 동쪽으로 움직였기 때문입니다. B가 본 A의 속도는 A의 속도에서 B의 속도를 뺀 건데요. 여기에서는 A가 집이였고, B가 거북이였습니다. 집은 움직이지 않았으니, 크기가 0이고요. B는 동쪽으로 1만큼 간 겁니다. 속도는 벡터입니다. 크기 0인 벡터에서 동쪽으로 1만큼 간 걸 빼면 서쪽으로 1만큼 간 게 되어 버립니다.

 

 즉 거북이가 특정 방향으로 1만큼 이동한다는 명령이 주어졌을 때, 그 반대 방향으로 장애물들과 집을 이동시켜서 거북이와 겹치는지 보면 됩니다. 같은 상황이기 때문입니다. 예를 들어서, 거북이가 밑으로 내려갔다면 어떨까요? D 방향인가요? D 방향의 반대는 U입니다. 그러므로, 거북이들을 밑으로 내리지 말고, 장애물과 집들을 위로 올려버리면 됩니다.

 

 

 어렵지 않네요. 사실, 이것 말고도 처리해야 하는 세세한 것들 (집과 장애물 등의 처리 순서와 box) 때문에 실제 난이도는 연계한 문제인 21773번 보다는 더 높습니다. 그에 대한 것은 다음에 이야기 해 보도록 하겠습니다.