Home > Archive > CPP_DS > ๐Ÿ†™[Cpp DataStructure] ๊ตํ™˜(Swap)๊ณผ ์ •๋ ฌ(Sort)

๐Ÿ†™[Cpp DataStructure] ๊ตํ™˜(Swap)๊ณผ ์ •๋ ฌ(Sort)
Cpp DataStructure

Swap(๊ตํ™˜)

๋จผ์ € ์•„๋ž˜์˜ ์ฝ”๋“œ๋ฅผ ๋ณด๊ณ  a์™€ b๋ฅผ ๊ตํ™˜ํ•ด๋ด…์‹œ๋‹ค.

#include <iostream>

using namespace std;

int main()
{

	// Swap
	{
		int a = 3;
		int b = 2;

		cout << a << " " << b << endl;

		// TODO:

		cout << a << " " << b << endl;	
	}

	return 0;
}

์‹คํ–‰ ๊ฒฐ๊ณผ

3 2
3 2

โ€œTODOโ€ ์—๋Š” ์–ด๋–ค ์ฝ”๋“œ๊ฐ€ ๋“ค์–ด๊ฐ€์•ผ ํ• ๊นŒ์š”?

โ€œ์šฐ๋ฆฌ๊ฐ€ ์–‘ ์†์— ์‚ฌ๊ณผ๐ŸŽ์™€ ๋ ˆ๋ชฌ๐Ÿ‹์„ ๋“ค๊ณ  ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ด…์‹œ๋‹ค.โ€

  • ๊ทธ๋Ÿผ ์™ผ์†์—๋Š” ์‚ฌ๊ณผ๐ŸŽ์™€ ์˜ค๋ฅธ์†์—๋Š” ๋ ˆ๋ชฌ๐Ÿ‹์„ ๋“ค๊ณ  ์žˆ์„ ๋•Œ ์‚ฌ๊ณผ๐ŸŽ์™€ ๋ ˆ๋ชฌ๐Ÿ‹์„ ๋ฐ”๊พธ๋ ค๋ฉด ์–ด๋–ป๊ฒŒ ํ•ด์•ผํ• ๊นŒ์š”?
    • ์ €๋Š” ํ•˜๋‚˜์˜ ์ ‘์‹œ๋ฅผ ๊ฐ€์ ธ์™€ ๊ทธ ์ ‘์‹œ์— ์‚ฌ๊ณผ ๋˜๋Š” ๋ ˆ๋ชฌ์„ ์ž ์‹œ ์˜ฌ๋ ค๋‘๊ณ  ๋น„์–ด์žˆ๋Š” ์†์œผ๋กœ ๊ณผ์ผ์„ ์˜ฎ๊ธด ๋’ค ์ ‘์‹œ์— ์žˆ๋Š” ๊ณผ์ผ์„ ์ง‘์„๊ฒƒ ์ž…๋‹ˆ๋‹ค.
      • ๊ทธ๋Ÿผ ์ฝ”๋“œ๋„ ๋˜‘๊ฐ™์ด ๋งŒ๋“ค ์ˆ˜ ์žˆ์ง€ ์•Š์„๊นŒ์š”?
#include <iostream>

using namespace std;

int main()
{

	// Swap
	{
		int a = 3;
		int b = 2;

		cout << a << " " << b << endl;

		// TODO:
        // ๋จผ์ € a๋ฅผ ์‚ฌ๊ณผ b๋ฅผ ๋ ˆ๋ชฌ์ด๋ผ๊ณ  ์ƒ๊ฐํ•˜๊ณ ,
        // temp๋ผ๋Š” ์ ‘์‹œ๋ฅผ ๋งŒ๋“ค์–ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.
        // ๊ทธ ์ ‘์‹œ์— a๋ผ๋Š” ์‚ฌ๊ณผ๋ฅผ ์˜ฌ๋ ค๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.
        int temp = a;
        
        // ๊ทธ๋Ÿผ ๋น„์–ด์žˆ๋Š” ์†์œผ๋กœ ๋ ˆ๋ชฌ์„ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ๊ฒŒ๋˜์—ˆ๋„ค์š”.
        // ๋น„์–ด์žˆ๋Š” ์†์œผ๋กœ ๋ ˆ๋ชฌ์„ ์˜ฎ๊ฒจ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.
        // a๊ฐ€ ์žˆ๋˜ ์†์œผ๋กœ b๋ฅผ ์˜ฎ๊น๋‹ˆ๋‹ค.
        a = b;
        
        // ์ด๋ฒˆ์—๋Š” b๊ฐ€ ์žˆ๋˜ ์†์ด ๋น„์—ˆ๋„ค์š”.
        // b๊ฐ€ ์žˆ๋˜ ์†์œผ๋กœ ์ ‘์‹œ(temp)์— ์žˆ๋Š” a๋ฅผ ๋“ค์–ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.
        temp = a;

		cout << a << " " << b << endl;	
	}

	return 0;
}

์‹คํ–‰ ๊ฒฐ๊ณผ

3 2
2 3
  • ์–‘ ์†์— ์žˆ๋˜ ์‚ฌ๊ณผ(3)๊ณผ ๋ ˆ๋ชฌ(2)์˜ ์ž๋ฆฌ๊ฐ€ ๋ฐ”๋€Œ์—ˆ์Šต๋‹ˆ๋‹ค
    • โ€œ์ฆ‰, ๊ตํ™˜(Swap)์ด ์ด๋ฃจ์–ด์กŒ์Šต๋‹ˆ๋‹ค.โ€

ํ•˜์ง€๋งŒ ํ•ญ์ƒ ์ด๋ ‡๊ฒŒ 3์ค„์˜ ๋ผ์ธ์ธ

int temp = a;
a = b;
b = temp;
  • ์œ„ ์ฝ”๋“œ์ฒ˜๋Ÿผ ์ฝ”๋“œ๋ฅผ ๋งŒ๋“ค์–ด์„œ ์‚ฌ์šฉํ•  ๊ฒฝ์šฐ์—๋Š” ๋งค์šฐ ๋งŽ์€ ๊ตํ™˜(Swap)์„ ํ•ด์•ผํ•  ๊ฒฝ์šฐ ์ฝ”๋“œ์˜ ์–‘๋„ ๋Š˜์–ด๋‚˜๊ณ  ๊ฐ€๋…์„ฑ๋„ ์ข‹์ง€ ์•Š์€ ๊ฒƒ ์ž…๋‹ˆ๋‹ค.

โ€œ๊ทธ๋Ÿผ ์ด๋ฒˆ์—๋Š” ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด์„œ ๋‘ ์ˆซ์ž๋ฅผ ๊ตํ™˜ํ•ด๋ด…์‹œ๋‹ค.โ€

๋จผ์ €, ์œ„ ๊ตํ™˜ ์ฝ”๋“œ๋ฅผ ๊ทธ๋Œ€๋กœ ๊ฐ€์ ธ๋‹ค๊ฐ€ ์‚ฌ์šฉํ•ด๋ณผ๊นŒ์š”?

void MySwap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}
  • ์ด ๊ฒฝ์šฐ์—๋Š” ๋ฆฌํ„ด ๊ฐ’์ด ์—†๊ธฐ ๋•Œ๋ฌธ์— ๋ถˆ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
    • ๋งŒ์•ฝ ๋ฆฌํ„ด๊ฐ’์ด int ํ˜•์ด๋ผ๊ณ  ํ•ด๋„ ๋ฆฌํ„ด์€ 1๊ฐœ๋งŒ ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์–ด๋ ต์Šต๋‹ˆ๋‹ค.
      • cpp์˜ ๋‹ค๋ฅธ ๊ธฐ๋Šฅ์ธ ๊ตฌ์กฐ์ฒด๋‚˜ ์—ฌ๋Ÿฌ ๊ธฐ๋Šฅ์„ ์‚ฌ์šฉํ•ด์•ผ ํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค.

๊ทธ๋Ÿฌ๋ฉด ์–ด๋–ป๊ฒŒ ํ•ด์•ผํ• ๊นŒ์š”?

  • โ€œC์˜ ํฌ์ธํ„ฐ์™€ CPP์˜ ๋ ˆํผ๋Ÿฐ์Šค๋ฅผ ํ™œ์šฉํ•˜๋ฉด๋ฉ๋‹ˆ๋‹ค.โ€

1. C์˜ ํฌ์ธํ„ฐ ํ™œ์šฉ

#include <iostream>

using namespace std;

void MySwapPtr(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

int main()
{

	// Swap
	{
		int a = 3;
		int b = 2;

		cout << a << " " << b << endl;

		MySwapPtr(&a, &b);

		cout << a << " " << b << endl;	
	}

	return 0;
}

์‹คํ–‰ ๊ฒฐ๊ณผ

3 2
2 3

์‹คํ–‰ ๊ฒฐ๊ณผ๋Š” ์˜ฌ๋ฐ”๋ฅด๊ฒŒ ๋‚˜์™”์Šต๋‹ˆ๋‹ค.

โ€œC ์Šคํƒ€์ผ์˜ ํฌ์ธํ„ฐ ์‚ฌ์šฉ์€ *(๋ณ„)์„ ์‚ฌ์šฉํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.โ€

void MySwapPtr(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
  • temp์— ๋จผ์ € a์˜ ์ฃผ์†Œ๊ฐ’์„ ๋„ฃ์–ด ์ค๋‹ˆ๋‹ค.
    • ์ดํ›„ a์˜ ์ฃผ์†Œ๊ฐ’์— b์˜ ์ฃผ์†Œ๊ฐ’์„ ๋„ฃ์–ด ์ค๋‹ˆ๋‹ค.
      • b์˜ ์ฃผ์†Œ๊ฐ’์—๋Š” temp(a์˜ ์ฃผ์†Œ๊ฐ’)์„ ๋„ฃ์–ด์ค๋‹ˆ๋‹ค.

โ€œ์ด๋ ‡๊ฒŒ ๋˜๋ฉด ๊ฐ ์ฃผ์†Œ๊ฐ’์ด ๊ตํ™˜์ด ๋ฉ๋‹ˆ๋‹ค.โ€

C ์Šคํƒ€์ผ์˜ ๋‹จ์ ์€ ์„ ์–ธ๊ณผ ํ˜ธ์ถœ์‹œ์— ๋‚˜ํƒ€๋‚ฉ๋‹ˆ๋‹ค.

  • ์„ ์–ธ์‹œ์—๋Š” ์œ„์™€ ๊ฐ™์ด *์„ ๋ชจ๋‘ ๋ถ™์—ฌ์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ํ˜ธ์ถœ์‹œ์—๋Š” ์•„๋ž˜์™€ ๊ฐ™์ด &๋ฅผ ๋ถ™์—ฌ์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.
MySwapPtr(&a, &b);

โ€œํ•˜์ง€๋งŒ CPP ์Šคํƒ€์ผ์˜ ๋ž˜ํผ๋Ÿฐ์Šค ๊ตํ™˜์€ ๋‹จ์ˆœํ•ฉ๋‹ˆ๋‹ค.โ€

// ์„ ์–ธ์‹œ
void MySwapRef(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

// ํ˜ธ์ถœ์‹œ
MySwapRef(a, b);
  • ๋‚ด๋ถ€ ๊ตฌํ˜„์€ ๋˜‘๊ฐ™์ง€๋งŒ ๋ณ„๋‹ค๋ฅธ ์–ด๋…ธํ…Œ์ด์…˜ ์—†์ด ์ผ๋ฐ˜์ ์ธ ๋ณ€์ˆ˜ ํ• ๋‹น๊ณผ ๊ฐ™์ด ํ•ด์ฃผ๋ฉด ๋ž˜ํผ๋Ÿฐ์Šค ๋Œ€์ž…๋˜๊ณ  ๊ตํ™˜์ด ์ด๋ฃจ์–ด์ง€๋Š” ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ํ˜ธ์ถœ์‹œ์—๋„ ์–ด๋…ธํ…Œ์ด์…˜์„ ๋”ฐ๋กœ ๋ถ™์ผ ํ•„์š”์—†์ด ์ผ๋ฐ˜์ ์ธ ๋งค๊ฐœ๋ณ€์ˆ˜(parameter)๋ฅผ ๋„ฃ์–ด์ฃผ๋“ฏ์ด ๋„ฃ์–ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
#include <iostream>

using namespace std;

void MySwapRef(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

int main()
{

	// Swap
	{
		int a = 3;
		int b = 2;

		cout << a << " " << b << endl;

		MySwapRef(a, b);

		cout << a << " " << b << endl;	
	}

	return 0;
}

์‹คํ–‰ ๊ฒฐ๊ณผ

3 2
2 3

โ€œ์ด๋ฒˆ์—๋Š” ๊ตํ™˜์„ ํ™œ์šฉํ•ด์„œ ์ •๋ ฌ์„ ํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.โ€

  • ๊ฐ’๊ณผ ์ƒ๊ด€ ์—†์ด ํ•ญ์ƒ ์ž‘์€ ๊ฐ’์ด ๋จผ์ € ์ถœ๋ ฅ๋˜๊ฒŒ ํ•˜๋ ค๋ฉด ์–ด๋–ป๊ฒŒ ํ•ด์•ผํ• ๊นŒ์š”?
    • ์ฆ‰, ๋‘ ๊ฐ’์ด ๊ฐ™์„ ๋•Œ๋Š” ์ˆœ์„œ๊ฐ€ ์ƒ๊ด€์ด ์—†์ง€๋งŒ ํฐ ๊ฐ’์ด ๋จผ์ € ์ถœ๋ ฅ๋˜์ง€ ์•Š๊ฒŒ ํ•ด์•ผํ•ฉ๋‹ˆ๋‹ค.

๋จผ์ € ๋‘ ๊ฐ’์ด ๊ฐ™์ง€ ์•Š๊ฑฐ๋‚˜ ํฐ ๊ฐ’์ด ๋จผ์ € ์ถœ๋ ฅ ๋˜์—ˆ์„ ๊ฒฝ์šฐ์— false๋ฅผ ์ถœ๋ ฅํ•˜๊ณ  ๊ทธ์™€๋Š” ๋ฐ˜๋Œ€์ผ ๊ฒฝ์šฐ์—๋Š” true๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

#include <iostream>

using namespace std;

// ์ •๋ ฌ(sorting)
int main() {
	int arr[2];

	// TODO:
	for (int j = 0; j < 5; j++) {
		for (int i = 0; i < 5; i++) {
			arr[0] = i;
			arr[1] = j;

			cout << boolalpha;
			cout << arr[0] << " " << arr[1] << " "
				<< (arr[0] <= arr[1]) << endl;
		}
	}
	return 0;
}
  • ๋จผ์ € ๋ฐฐ์—ด์„ ์„ ์–ธํ•ฉ๋‹ˆ๋‹ค. ๋ฐฐ์—ด์€ ์ˆœ์„œ๊ฐ€ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
    • ๊ทธ๋ฆฌ๊ณ  2์ค‘ for๋ฌธ์„ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ์ฒซ ๋ฒˆ์งธ for๋ฌธ์ด 1๋ฒˆ ๋Œ ๋•Œ ๋‘ ๋ฒˆ์งธ for๋ฌธ์€ 5๋ฒˆ ๋Œ๊ฒŒ๋ฉ๋‹ˆ๋‹ค.
      • ๊ทธ๋ ‡๊ฒŒ ๊ฐ๊ฐ์„ i์™€ j์— ๋ผ๋Š” ๋ณ€์ˆ˜์˜ ์ด๋ฆ„์œผ๋กœ arr ๋ฐฐ์—ด ์ธ๋ฑ์Šค 0๋ฒˆ์งธ์™€ 1๋ฒˆ์งธ์— ๋„ฃ์–ด์ค๋‹ˆ๋‹ค.

์‹คํ–‰ ๊ฒฐ๊ณผ

0 0 true
1 0 false
2 0 false
3 0 false
4 0 false
0 1 true
1 1 true
2 1 false
3 1 false
4 1 false
0 2 true
1 2 true
2 2 true
3 2 false
4 2 false
0 3 true
1 3 true
2 3 true
3 3 true
4 3 false
0 4 true
1 4 true
2 4 true
3 4 true
4 4 true
  • ์‹คํ–‰ ๊ฒฐ๊ณผ ๊ฐ’์ด ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ๊ฐ’์ด ์ธ๋ฑ์Šค 0๋ฒˆ ์ฆ‰ ์˜ค๋ฆ„์ฐจ์ˆœ์ผ ๊ฒฝ์šฐ์—๋Š” true ์ž…๋‹ˆ๋‹ค.
    • ๊ทธ์™€๋Š” ๋ฐ˜๋Œ€๋กœ ํฐ ๊ฐ’์ด ์ธ๋ฑ์Šค 0๋ฒˆ ์ฆ‰ ๋‚ด๋ฆผ์ฐจ์ˆœ์ผ ๊ฒฝ์šฐ์—๋Š” false ์ž…๋‹ˆ๋‹ค.

โ€œ์ด์ œ ๋‘ ๊ฐ’์„ ๋น„๊ตํ•˜์—ฌ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜๋Š” ๊ฒƒ์„ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค์—ˆ์œผ๋‹ˆ ์ด๋ฒˆ์—๋Š” ์‹ค์ œ ์ •๋ ฌ์„ ํ•ด๋ณด๋„๋กํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.โ€

#include <iostream>

using namespace std;

bool CheckSorted(int a, int b) {
	// TODO: ...
	if (a <= b) {
		return true;
	} else {
		return false;
	}
}

// ์ •๋ ฌ(sorting)
int main() {
	int arr[2];

	// TODO:
	for (int j = 0; j < 5; j++) {
		for (int i = 0; i < 5; i++) {
			arr[0] = i;
			arr[1] = j;

			// swap ์†Œ๊ฐœ
			if (arr[0] > arr[1]) {
				swap(arr[0], arr[1]);
			}

			cout << boolalpha;
			cout << arr[0] << " " << arr[1] << " "
				<< (CheckSorted(arr[0], arr[1])) << endl;
			
		}
	}
	return 0;
}

์‹คํ–‰ ๊ฒฐ๊ณผ

0 0 true
0 1 true
0 2 true
0 3 true
0 4 true
0 1 true
1 1 true
1 2 true
1 3 true
1 4 true
0 2 true
1 2 true
2 2 true
2 3 true
2 4 true
0 3 true
1 3 true
2 3 true
3 3 true
3 4 true
0 4 true
1 4 true
2 4 true
3 4 true
4 4 true
  • CPP์—๋Š” swap์ด๋ผ๋Š” ํ•จ์ˆ˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค swap์„ ์‚ฌ์šฉํ•  ๊ฒฝ์šฐ์—๋Š” ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ๋ฐ›์€ ๋‘ ๊ฐ’์„ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค.
    • ๋”ฐ๋ผ์„œ ์œ„์™€ ๊ฐ™์€ ์‹คํ–‰ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.