n>=1개의 원소를 가진 집합이 주어졌을 때 이 집합의 모든 가능한 순열을 출력해보자. 예를들어 주어진 집합이 {a,b,c}라면 순열의 집합은

{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)이다. n개의 주어진 원소에 대해 n!개의 서로 다른 순열이 있다는 것은 쉽게 알 수 있다.

네개의 원소 (a,b,c,d)로 된 집합을 살펴보면 간단한 알고리즘을 얻을 수 있을 것이다. 해답은 다음과 같이 출력해 보면 얻을 수 있다.

 

 (1) a로 시작하는 (b,c,d)의 모든 순열

 (2) b로 시작하는 (a,c,d)의 모든 순열

 (3) c로 시작하는 (a,b,d)의 모든 순열

 (4) d로 시작하는 (a,b,c)의 모든 순열

 

 '~로 시작하는 ~의 모든 순열'이라는 표현이 바로 순환의 실마리이다. 이것은 n-1개의 원소에 동작하는 알고리즘이 있다면, n개의 원소를 가진 집합에 대한

문제도 해결 할 수 있다는 것을 의미한다. 이러한 생각으로 프로그램을 만들어 낼 수 있고, 이 함수는 Perm(a,0)이라는 식으로 호출된다.

 

 순환이 유용한 또 다른 예는, 알고리즘이 다루는 자료 구조가 순환적으로 정의되어 있는 경우이다.

 

C# 코드

namespace 순열
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] datas = new char[] { 'a', 'b','c' };

            Perm(datas, 0);

            Console.ReadKey();
        }

        /// <summary>
        /// 순열을 출력한다.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="k"></param>
        private static void Perm(char[] a, int k)
        {
            if (k == a.Length - 1)//순열을 출력
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("{0} ", a[i]);
                }
                Console.WriteLine();
            }
            else
            {
                for (int i = k; i < a.Length; i++)
                {
                    //a[k]와 a[i]를 교환
                    char temp = a[k];
                    a[k] = a[i];
                    a[i] = temp;

                    Perm(a, k + 1); //a[k+1],…,a[n-1]에 대한 모든 순열
                    //원래 상태로 되돌리기 위해 a[k]와 a[i]를 다시 교환
                    temp = a[k];
                    a[k] = a[i];
                    a[i] = temp;
                }
            }
        }
    }
}

 

순열.zip

 

참고 : C++ 자료구조론 - 이석호

저작자표시 비영리 동일조건

'.Net > Algorithm' 카테고리의 다른 글

C# 이진탐색  (0) 2012.10.10
C# 선택정렬  (1) 2012.10.10

 n>=1개의 서로 다른 정수가 이미 정렬되어 배열 a[0], …, a[n-1]에 저장되어 있다. x=a[j]인 x가 존재하면 j를 반환하고, 그렇지 않으면 -1을 반환한다.

이 집합이 정렬되어 있다는 사실을 이용해서 효율적인 다음 방법을 생각할 수 있다.

 

 left, right는 탐색하고자 하는 배열의 왼쪽, 오른쪽 끝지점을 가리킨다. 초기값으로 left=0, right=n-1로 하고 리스트의 중간 위치 middle=(left+right)/2로 설정한다.

a[middle]과  x를 비교할 경우 다음 세 가지의 경우 중에서 하나를 고려할 수 있다.

 

 (1) x<a[middle] : 이 경우 x가 존재한다면 그것은 0과 middle-1 사이에 있으므로 right는 middle-1로 설정한다.

 (2) x==a[middle] : 이 경우는 middle을 반환한다.

 (3) x>a[middle] : 이 경우 x가 존재한다면 middle+1과 n-1사이에 있으므로 left를 middle+1로 설정한다.

 

 x가 발견되지 않고 검사할 정수도 아직 남아 있다면 middle을 다시 계산하고 탐색을 계속한다. 알고리즘은 두 작업을 한다.

 

 (1) 검사할 정수가 아직 남아 있는지 결정하고

 (2) x를 a[middle]과 비교한다.

 

 

C# 코드

namespace 이진탐색
{
    class Program
    {

        static void Main(string[] args)
        {
            //이미 정렬되어있는 int 배열
              int[] datas = new int[] { 1,2,3,5,12,13,31,53,56};

            int result = BinarySearch(datas, 1);

            View(result);

            Console.ReadKey();
        }

        /// <summary>
        /// 이진 탐색을 수행한다.
        /// </summary>
        /// <param name="datas">배열</param>
        /// <param name="data">검색할 데이터</param>
        /// <returns></returns>
        private static int BinarySearch(int[] datas,int data)
        {
            int right = datas.Length - 1;
            for (int left = 0; left <= right; )
            {
                int middle = (left + right) / 2;
                switch (Compare(data, datas[middle]))
                {
                    case '>': left = middle + 1; break;//x>datas[middle] 
                    case '<': right = middle - 1; break;//x<datas[middle]
                    case '=': return middle; //x==datas[middle]
                }
               
            }
            //발견되지 않음
            return -1;
        }

        /// <summary>
        /// x와 y를 비교한다.
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        private static char Compare(int x, int y)
        {
            if (x > y)
                return '>';
            else if (x < y)
                return '<';
            else 
                return '=';
        }

        

        /// <summary>
        /// 화면에 출력한다.
        /// </summary>
        /// <param name="result"></param>
        private static void View(int result)
        {
            Console.Write("{0} ", result);
        }
    }
}

 

 

 

 

이진탐색.zip

참고 : C++ 자료구조론 - 이석호


 

저작자표시 비영리 동일조건

'.Net > Algorithm' 카테고리의 다른 글

C# 순열  (2) 2012.10.10
C# 선택정렬  (1) 2012.10.10 
            for (int i = 0; i < n; i++)
            {
                //a[i]에서부터 a[n-1]까지의 정수 값을 검사한 결과 a[j]가 가장 작은 값이라고 하자;
                //a[i]와 a[j]를 서로교환;
            }

 

위의 코드를 완전한  C# 프로그램으로 변환하기 위해서는 두 가지 작업이 필요하다. 즉, 최소 정수를 찾는 작업과 이 최소 정수 값을 a[i]값과 교환하는 작업이다.

두번째 작업을 처리하기 위해서는 다음 코드를 사용한다.

 

temp=a[i]; a[i] = a[j]; a[j] = temp;

 

첫번째 작업에서는 먼저 최소값이 a[i]라 가정하고, a[i]를 a[i+1], a[i+2], …와 비교하여 작은 값이 나타날 때마다 그 값을 새로운 최소값으로 간주한다.

마지막으로 a[n-1]을 현재의 최소값과 비교하면 종료된다. 이런 과정을 모두 종합하면 함수 SelectSort를 얻는다.

 

C# 코드

namespace 선택정렬
{
    class Program
    {

        static void Main(string[] args)
        {
            int[] datas = new int[] { 32,12,51,2,13,12,53,10,2,3 };

            int[] result = SelectSort(datas);

            View(result);

            Console.ReadKey();
        }

        /// <summary>
        /// 선택정렬을 수행한다.
        /// </summary>
        /// <param name="datas"></param>
        /// <returns></returns>
        private static int[] SelectSort(int[] datas)
        {
            for (int i = 0; i < datas.Length; i++)
            {
                for (int j = i+1; j < datas.Length; j++)
                {
                    if (datas[i] > datas[j])
                    {
                        int temp = datas[j];
                        datas[j] = datas[i];
                        datas[i] = temp;
                    }
                }
            }
            return datas;
        }

        /// <summary>
        /// 화면에 출력한다.
        /// </summary>
        /// <param name="result"></param>
        private static void View(int[] result)
        {
            foreach (var data in result)
            {
                Console.Write("{0} ", data);
            }
        }
    }
}


 

선택정렬.zip

 

 

참고 : C++ 자료구조론 - 이석호

저작자표시 비영리 동일조건

'.Net > Algorithm' 카테고리의 다른 글

C# 순열  (2) 2012.10.10
C# 이진탐색  (0) 2012.10.10

+ Recent posts

티스토리툴바