투 명 테 잎

#include <iostream>

#include <cstring> // strlen 사용

using namespace std;

class LevenshtainDistance

{

private:

static int min(int a, int b, int c);

public:

static int LD(char *s, char *t);

};

int LevenshtainDistance::min(int a, int b, int c)

{

int m = a;

if (b < m) m = b;

if (c < m) m = c;

return m;

}

int LevenshtainDistance::LD(char *s, char *t)

{

int slen = strlen(s), tlen = strlen(t);

int i, j;

int cost;

int **d = new int*[slen + 1];

for (i = 0; i <= slen; ++i) d[i] = new int[tlen + 1];

if (slen == 0) return tlen;

if (tlen == 0) return slen;

for (i = 0; i <= slen; ++i) d[i][0] = i;

for (i = 0; i <= tlen; ++i) d[0][i] = i;

for (i = 1; i <= slen; ++i)

{

for (j = 1; j <= tlen; ++j)

{

if (s[i - 1] == t[j - 1]) cost = 0;

else cost = 1;

d[i][j] = min(d[i - 1][j] + 1,

d[i][j - 1] + 1,

d[i - 1][j - 1] + cost);

}

}

int dis = d[slen][tlen];

for (i = 0; i <= slen; ++i)

delete d[i];

delete d;

return dis;

}

int main()

{

char *s = "GUMBO";

char *t = "GAMBOL";

cout << LevenshtainDistance::LD(s, t) << endl;

return 0;

}

#include <iostream>
#include <vector>
#include <algorithm> // for swap()
using namespace std;

class Permutation
{
private:
	int n; // 원소 개수
	vector<int> v;
	bool isAsc; // true : 오름차순으로 진행?

public:
	void assign()
	{
		int i;
		v.reserve(n);
		for (i = 0; i < n; ++i)
		{
			if (isAsc)
				v.push_back(i + 1);
			else
				v.push_back(n - i);
		}
	}

	Permutation(bool asc)
	{
		cout << "Input n : ";
		cin >> n;
		isAsc = asc;
		assign();
	}

	Permutation(int num, bool asc = true)
	{
		n = num;
		isAsc = asc;
		assign();
	}

	// 오름차순일때 사용
	bool next()
	{
		if (isAsc)
		{
			int k, j, r, s;
			k = n - 2;
			while (v[k] > v[k + 1])
			{
				if (k == 0)
					return false;
				k--;
			}

			j = n - 1;

			while (v[k] > v[j]) j--;
			swap(v[j], v[k]);

			r = n - 1;
			s = k + 1;

			while (r > s)
				swap(v[r--], v[s++]);
			return true;
		}
		return false;
	}

	// 내림차순 일때 사용
	bool previous()
	{
		if (!isAsc)
		{
			int k, j, r, s;
			k = n - 2;
			while (v[k] < v[k + 1])
			{
				if (k == 0)
					return false;
				k--;
			}
			j = n - 1;

			while (v[k] < v[j]) j--;
			swap(v[j], v[k]);

			r = n - 1;
			s = k + 1;

			while (r > s)
				swap(v[r--], v[s++]);
			return true;
		}
		return false;
	}

	// 출력
	void print()
	{
		int i;
		for (i = 0; i < n; ++i)
			cout << v[i];
		cout << endl;
	}

	void fullprint()
	{
		if (isAsc)
		{
			for (; next(); )
				print();
		}
		else
			for (; previous(); )
				print();

	}
};

int main()
{
	Permutation p1(4), p2(5, false);

	cout << "----- 오름차순 순열 -----" << endl;
	p1.print();
	for (; p1.next(); )
		p1.print();

	cout << endl << "----- 내름차순 순열 -----" << endl;
	p2.fullprint();
	return 0;
}