알고리즘 - Swap

Swap 

Swap은 영문적 의미로 바꾸다, 교환하다의 의미를 갖고 있는 단어 입니다. 

그리고 프로그래밍에서 Swap또한 바꾸다, 교환하다의 개념을 일컫고 있습니다. 

현실에서 사람 A가 사과를 가지고 있고 사람 B가 바나나를 가지고 있다면 서로 교환을 하면 됩니다.

프로그래밍에서 서로 교환을 하는 말처럼 간단하지 않습니다. 

2가지 변수 A와 B를 선언하면 그림과 같이 메모리 공간위에 올라올 것입니다.

int A = 5;
int B = 10;

소스코드의 연산을 통해서 두 값을 변경을 한번 해보겠습니다.

A = B ; 
B = A ;

A = B ;
즉 A라는 메모리 공간에 B의 값 10을 대입

이미 A = B 라는 대입연산을 하였기 때문에 변수 A에의 값은 5에서 10으로 변경이 됩니다. 

우리의 목적은 A 와 B안의 값을 변경하고 싶었는데 위의 방법으로는 불가능 하다는 것을 알 수 있습니다. 

그렇다면 swap을 하기위한 몇가지 알고리즘 기법에 대하여 알아보겠습니다.

 

Swap 임시 변수를 이용한 방법

2가지 변수의 값을 변경하려면 위와 같은 연산으로는 불가능 하다는 것을 알았습니다. 대입 연산을 하는 순간 기존에 있던 값의 정보가 사라지기 때문입니다. 따라서 임시 변수공간을 하나 생성을 해서 기억을 하는 방법을 사용합니다.

int A = 5;
int B = 10;
int Temp = 0;
Temp = A ; // Temp = 5
A = B ; // A = 10
B = Temp; // B = 5

이처럼 임시변수를 하나 메모리 공간위에 선언하여 잠깐 하나의 변수를 저장한 후에 다시 사용하는 방식입니다.

가장 대표적인 Swap 알고리즘 기법 중 하나 입니다. 구현은 간단하나 하나의 임시 저장할 변수의 메모리 공간이 필요하다는 단점이 있습니다. 하지만 간단한 대입 연산 3번이기 때문에 속도가 빠릅니다.

 

Swap 연산을 통한 방법

만약 우리가 사용할수 있는 메모리공간이 더이상 없는 상황에서 두 변수의 값을 바꿔야한다면 위의 방법으로는 구현이 불가능 합니다. 이런 상황에서 두 변수의 값을 바꾸기 위해서는 2가지 해결법이 존재 할 것 입니다.

• 메모리공간을 추가한다.
• 다른 Swap알고리즘 기법을 찾아 구현한다.

이 방법은 Swap의 다른 알고리즘 기법에 대하여 말해보도록 하겠습니다. 간단한 연산을 통해 구현이 가능합니다.

int A = 5;
int B = 10;


A = A+B;  //   15
B = A-B;  //   -5
A = A-B   //    10
B = B-A   //    5

 

이와 같은 방법으로 연산을 통해서 Swap 구현 또한 가능합니다. 하지만 이 방법은 연산과정이 많습니다.. 따라서 메모리 공간에 대해서는 효율적이나 연산을 많이 하기 때문에 속도가 비교적 느립니다.