반응형

 배열 회전 알고리즘은, 구현 문제에서 심심찮게 보이는 문제 중에 하나입니다. 우리는 n by n 배열을 시계, 그리고 반시계 방향으로 temp array를 쓰고 회전하는 방법을 배워보도록 하겠습니다. 물론, 면접에서는 n by n짜리를 안 쓰고 돌리는 방법을 물어볼 수도 있습니다. 이에 대한 방법은, 과제로 드리겠습니다.

 

 


 배열이 있습니다. 이것을 시계 방향으로 90도 회전시키면 어떻게 그려질까요?

 

 

 요렇게 그려집니다. 그런가요? 그러면 우리는 첫 번째 줄부터 특징을 잡아야 하는데요. 1번째 줄에는, [..][0]이 들어갔다는 것을 알 수 있습니다. 2번째 줄에는 [..][1]이, 3번째 줄에는 [..][2]가 들어갔다는 것을 알 수 있어요. 이제 0열부터 2열까지 열별로 볼까요?

 

 

 그러면, 0열은 [2][..]을 대입함을 알 수 있어요. n이 3이므로, 이는 [n-1][..]의 값을 대입하는 것과 같습니다.

 

 

 다음에 1열은 어떤가요? 공통적으로 회전하기 전의, [1][..]의 값을 넣고 있음을 볼 수 있어요. 이는 (n-1)-1과 같습니다. 2열의 값들은 어떨까요?

 

 

 공통적으로 [0][..]을 넣고 있어요. 이것은 (n-1)-2와 같아요. 정리하면 회전 후의 [i][j]는, 회전 전의 [n-1-j][i]의 값을 넣었다고 보셔도 좋겠습니다. 보통 값을 교환할 때, temp라는 임시 변수를 두는데요. 저는, 이것을 임시 배열로 두겠습니다.

 

 

 제가 언급한 내용을 코드로 구현해 봅시다. rorate는 시계 방향으로 90도 회전하는 것입니다.

 

 

 temp 배열에 먼저 90도 회전시킨 결과물을 넣고, 그것의 결과를 다시 arr에 복사합니다.

 

 


 그러면 반시계 90도는 어떻게 구현할 수 있을까요? 함수를 따로 빼서 구현하실 수도 있습니다만, 함수의 재사용을 할 수도 있다는 방법에서 그리 현명하지는 않습니다. 왜냐하면, 반시계로 90도 돌리는 연산은, 시계 방향으로 3번 돌리는 것과 같기 때문입니다.

 

 

 즉, rotate를 3번 돌리면, 반시계로 1번 돌린 것과 같습니다. 따라서, 그냥 rotate 함수만 구현이 되어 있다면, 그것을 3번 호출하기만 하면 됩니다.

 

 

 간단하게 구현을 끝낼 수 있었습니다. 그런데, 이것을 임시 배열을 쓰지 않고 할 수도 있습니다.

 

 

 이것은 회전 전과 회전 후의 모습을 봐도 쉽게 짐작이 가능합니다. 노란색으로 칠한 부분이 어떻게 변했나요? 시계 방향으로 읽어보면, [0][0], [0][2], [2][2], [2][0]이였습니다. 이 값들이 rotate 후에는 [2][0], [0][0], [0][2], [2][2]로 바뀌었습니다. 이는 요소 4개가 1칸씩 뒤로 rotate가 돌아갔다는 이야기가 됩니다.

 

 

 보라색 부분은 어떤가요? [0][1], [1][2], [2][1], [1][0] 부분이 [1][0], [0][1], [1][2], [2][1]이 되었음을 알 수 있어요. 역시 뒤로 1칸씩 밀어진 겁니다. 이렇게 ㅁ자형이 돌아갔을 때를 1 사이클이라고 봅시다.

 

 

ㅁ자에 대해서 4개씩 잡아서 돌리면 됩니다. n by n 배열에서 n by n 짜리 임시배열을 사용하지 않고, 시계, 혹은 반시계로 돌리는 방법입니다. 구현은 그리 어렵지 않으니, 이 포스팅에서는 생략하도록 하겠습니다.

반응형

댓글을 달아 주세요

  1. 내로라하다

    역시 영리하십니다. ㅎ

  2. 상식체온

    참 기막힌 발상이네요.
    "왼쪽으로 한번 돌리는 것은 오른쪽으로 3번 돌리는 것과 같다."
    한번도 생각지도 못한 새로운 방법을 알고 갑니다.

  3. hunnek

    프로그래밍 배운지 좀 됐지만 이건 기억이 새록새록 나네요
    잘보고갑니다.

  4. 한번사는인생.

    이런건 직접 짜시는건가요?
    rotate하는 함수같은걸 본게 있었는데, 어디서 봤는지 기억은 잘 안나지만.....

  5. eveforever623

    질문있습니다

    n*n의 배열이 아닌 m*n의 경우에는 임시 배열을 사용하지 않고 어떻게 돌릴 수 있나요?

    보기의 예와 같이 구간을 잡는게 쉽지가 않네요. 좋은 글 잘 봤습니다.

    • 코딩강아지
      2020.03.21 23:24 신고

      저게 면접 질문으로 나오면
      전 good game 할 거 같습니다만..

      시도해 볼 만한 방법은
      m*n짜리를 max(m,n) * max(m,n)으로 보고
      똑같은 알고리즘 적용하면 되지 않나 싶어요.

  6. 22

    3 by 3에서는 이해가 되는데 4by4에서는 어떻게 동작해야하죠?