[C++#2-3] 밀기 알고리즘

이번 시간에는 밀기 알고리즘을 정리하려고 한다.

밀기 알고리즘은 한마디로 정의하자면 '당기는' 알고리즘이다.

[C++#2-1] 회전 알고리즘의 연장된 내용이라고 할 수도 있다.

다음과 같이 회전판을 이동시키거나, 

 

아니면 회전할수 있는 어떤 장소에 있는 사람을 이동시키는 알고리즘을 구현하려면 어떻게 할까?

이같은 문제에 대한 해결책이 밀기 알고리즘이다.

1. 밀기 알고리즘

다음과 같은 회전판이 있을 때, 우리는 회전판을 배열로 나타내는 것을 지난시간에 했었다.

회전 알고리즘에서는 회전했을 때의 '결과 값'만 생각하고 회전을 구현하지 않았지만, 

밀기 알고리즘에서는 회전판의 '회전'을 구현하려 한다.

1-1. 1차원 밀기

처음 밀기 알고리즘을 구현할 때 가장 많이 실수하는 점이 시작점을 잘못 잡는 것이다.

시작점부터 밀기를 시작한다면, 밀어낸 값을 계속 밀어내서 배열에 최종적으로 같은 값이 저장되는 오류가 발생할 것이다.

글의 시작에서도 말했지만, 밀기 알고리즘의 핵심은 '당긴다'는 것이다.

먼저 배열의 모든 인덱스들을 왼쪽(정방향)으로 민다고 생각하면, 우리는 0번 index가 아닌 마지막 index부터 이동을 시켜주어야 한다.

하지만 배열의 범위를 넉넉히 잡았다면 상관이 없지만, 마지막 index인 4를 배열 밖으로 밀어낼 수는 없다.

그래서 밀기 알고리즘을 구현하기 위해서는 새로운 하나의 변수가 있어야 한다.

그 변수를 임의로 temp라고 지정하겠다.

아래 그림과 같이, 마지막 index인 4를 먼저 temp 변수에 저장한다.

그 후에 0번 index까지 이전 index의 값들을 현재 index에 넣어준 후, 

마지막으로 temp에 있는 값을 0번 index에 넣어주면 회전된 회전판의 배열을 얻을 수 있다.

위의 알고리즘을 코드로 나타내면 다음과 같다.

 
int arr[4] = {1,2,3,4};
int temp;
 
temp = arr[3];
for(int i = 3; i > 0; i--){
    arr[i] = arr[i-1];
}
arr[0] = temp;
 
 

1-2. 2차원 밀기

2차원으로 밀기를 구현하는 것도 어렵지 않다.

같은 알고리즘으로 2차원 배열에서 행연산을 해주면 다음 같은 회전을 구현할 수 있다.

 

2차원에서의 밀기를 코드로 구현하려면 아래와 같이 코드를 작성하면 구현할 수 있다.

 
int arr[4][4] = { { 0, 1, 0, 0 },
                { 0, 2, 0, 0 },
                { 0, 3, 0, 0 },
                { 0, 4, 0, 0 } };
int temp;
 
temp = arr[1][3];
for(int i = 3; i > 0; i--){
    arr[1][i] = arr[1][i-1];
}
arr[1][0] = temp;