Haebi's Labortory

나름 간단하게? 구현해본 백트래킹 (맞는지는 잘 모르겠으나 어쨋든 백트래킹으로 명명)입니다.

입력받은 배열의 값에 대해서 가능한 모든 순서조합을 만들어냅니다.
단, 모든 순서조합을 위해서는 최초에 배열의 수가 오름차순으로 정렬되어져 있어야 합니다.

최종적인 형태는 내림차순정렬이 되어져 있으며, 이때 함수는 더이상 처리를 하지 않고 들어온 값 그대로 리턴 시켜 버립니다.

내림차순 정렬이 완료 되었으나, 맞는 조합이 없었다면, 해당 문제는 해가 없는 것이 됩니다. (즉, 풀수 없는 문제...)

매번 시도 마다 다음 조합으로 만들어 냅니다. (1차 배열만, 배열의 크기는 무관)
현재 배열의 순서가 답이 될수 없다면, 배열을 다시 백트랙 돌리면 바로 다음 배열 순서의 조합을 만들어냅니다.

1-2-3-4-5-6-7-8-9 의 항이 있었다고 가정할 때...
이 값의 순서가 해당 문제의 답으로서 맞지 않는다면 다음 항으로는
한칸 앞으로 돌아와서(이것이 백트랙이죠)
순서를 바꾸어 볼수 있습니다.
따라서,
1-2-3-4-5-6-7-9-8 을 생각해 볼수 있습니다.

그리고 몇번만 시도를 해보자면...
1-2-3-4-5-6-8-7-9
1-2-3-4-5-6-8-9-7
1-2-3-4-5-6-9-7-8
1-2-3-4-5-6-9-8-7
1-2-3-4-5-7-6-8-9
(...)
9-8-7-6-5-4-3-1-2
9-8-7-6-5-4-3-2-1 (최종값)

예) Array = BackTrack(Array)
(* Array는 1차 배열 변수)

아래 그림은 배열에 현재 값이 {6,7,3,5,4,2,1}이 들어있을 때, 함수 내부에서 다음 배열의 순서인 {6,7,4,1,2,3,5} 로 바뀌는 과정을 설명합니다.

            // 1. 배열에서 마지막 증가위치가 배열의 끝 일때...
            if (BT_LTop == Array.Length - 1)
            {
                // 마지막 증가위치
                Array = ArrSwitch(Array, BT_LTop, BT_LTop - 1);
            }
            // 2. 마지막 증가위치의 값 바로 앞의 수를 다음 수로 바꾼뒤 뒷부분 정렬
            else
            {
                //마지막 증가값의 위치 앞부분이 -1 이 아닐때...
                if (BT_LTop - 1 != -1)
                {
                    // 2-1. 마지막 증가위치 바로 앞의 값을 임시 변수에 저장
                    SU_tmp1 = Array[BT_LTop - 1];
                    // 2-2. 마지막 증가위치 바로 앞부분으로 부터 뒷부분 정렬
                    Array = ArrSort(Array, BT_LTop - 1);
                    // 2-3. 마지막 증가위치 바로 앞부분부터 뒤로 스캔하여 다음으로 큰값 찾아서 스위칭
                    Array = ArrSwitch(Array, BT_LTop - 1, ArrNext(Array, BT_LTop - 1, SU_tmp1));
                    // 2-4. 마지막 증가위치로 부터 뒤로 다시 오름차순 정렬
                    Array = ArrSort(Array, BT_LTop);
                }
                else
                {
                    return Array;
                }
            }
            return Array;
        }


백트래킹 함수의 소스는 여기까지 입니다만, 이 함수의 내부에서 쓰여진 함수들 또한 별도로 만들어야 합니다.
- ArrLTop()
- ArrSwitch()
- ArrSort()
- ArrNext()


--------------------------------(여기부터 내부에서 쓰인 함수들)------------------------------------------

        // ===============================================================================================
        // ArrLTop()
        // 제작자 : haebi.kr
        // 작성일 : 2010-02-03
        // 수  정 : 2010-02-03
        // 내  용 : 배열에서 마지막으로 값의 변화가 증가된 곳을 리턴
        // ===============================================================================================
        private int ArrLTop(int[] Array)
        {
            int i=0;
            int LTop=0;

            for (i = 0; i < Array.Length - 1; i++)
            {
                if (Array[i] < Array[i + 1])      // 바로 다음 배열의 값이 현재 값 보다 큰지 체크!
                {
                    LTop = i + 1;                 // LTop 가장마지막에 이전값과 비교해 증가한 값의 배열 위치 갱신
                }
            }
            return LTop;
        }



        // ===============================================================================================
        // ArrSwitch()
        // 제작자 : haebi.kr
        // 작성일 : 2010-02-03
        // 수  정 : 2010-02-03
        // 내  용 : 배열에서 Value1과 Value2의 위치에 있는 값을 교환
        // ===============================================================================================
        private int[] ArrSwitch(int[] Array, int Value1, int Value2)
        {
            int tmp;
            tmp = Array[Value1];
            Array[Value1] = Array[Value2];
            Array[Value2] = tmp;
            return Array;
        }



        // ===============================================================================================
        // ArrSort()
        // 제작자 : haebi.kr
        // 작성일 : 2010-02-03
        // 수  정 : 2010-02-03
        // 내  용 : 배열에서 Pos위치 부터 뒤로 오름차순 정렬
        //          (버블소트 알고리즘 응용)
        // ===============================================================================================
        private int[] ArrSort(int[] Array, int Pos)
        {
            int i = 0;
            int j = 0;
            int icnt = 0;

            // --------------------------------------------------
            // 버블소트 알고리즘 (선택범위 정렬)
            // --------------------------------------------------
            for (i = Pos; i < Array.Length - 1; i++)
            {
                for (j = Pos; j < Array.Length - 1 - icnt; j++)
                {
                    if (Array[j] > Array[j + 1])
                    {
                        Array = ArrSwitch(Array, j, j + 1);
                    }
                }
                icnt++;
            }
            // --------------------------------------------------
            return Array;
        }



        // ===============================================================================================
        // ArrNext()
        // 제작자 : haebi.kr
        // 작성일 : 2010-02-03
        // 수  정 : 2010-02-03
        // 내  용 : 배열에서 시작위치(stPos)부터 뒤로 스캔하여 입력값(Num)보다 바로 다음으로 큰수를 리턴
        // ===============================================================================================
        private int ArrNext(int[] Array, int stPos, int Num)
        {
            int i = 0;
            byte detect = 0;
            // 입력받은 배열을 tmpArray에 복사
            int[] tmpArray = (int[])Array.Clone();
            // stPos 으로 부터 뒷부분 정렬
            tmpArray = ArrSort(tmpArray, stPos);

            for (i = stPos; i < tmpArray.Length; i++)
            {
                // 바로 같은 값이 발견된 상태이면
                if (detect == 1)
                {
                    // 배열에 같은값이 존재 할 경우...
                    if (tmpArray[i] == Num)
                    {
                        detect = 0; // 발견 플래그 초기화
                    }
                    else
                    {
                        return i; //바로 다음 항목 출력
                    }
                }

                // 입력받은값과 배열의 값이 같은경우
                if (Num == tmpArray[i])
                {
                    detect++; // 발견 플래그 설정
                }
            }
            return -1;
        }

C# 으로 만든 초간단 팩토리얼 함수 입니다.
인자로 INT값을 하나 받으면 리턴값 또한 INT입니다.

        // ----------------------------------------------------------------------
        // 팩토리얼 함수
        // 1*2*3* ... *n
        // ----------------------------------------------------------------------
        private int Factorial(int Num)
        {
            if (Num == 0)               // 입력된 값이 0 이면 0을 리턴
            {
                return 0;
            }

            int i=1;
            int Fac_Value=1;

            for (i = 1; i <= Num; i++)  // 1부터 입력받은 수 까지 반복
            {
                Fac_Value *= i;         // Fac_Value에 반복카운트의 수를 계속 곱함
            }
            return Fac_Value;           // 반복이 끝나면 곱한 수의 결과값을 리턴
        }
        // ----------------------------------------------------------------------

ThreadEx1.1.zip

ThreadEx1의 개량형 버젼입니다.

기존에는 반복횟수를 카운트 하는 쓰레드 에서 표시까지 직접하였었는데, 컨트롤에 텍스트 표시하는데 걸리는 CPU의 부하 라던가 시간을 생각하다가 그냥 반복만 돌면 스피드가 얼마나 나올까 하는 생각에 제외시키기로 해보았습니다.

하지만 반복이 끝나기까지 마냥 기다리려면 좀 답답한 감이 있으니... 별도로 쓰레드를 생성하여 반복루프를 도는 작업쓰레드의 진행상황을 표시해 주는것으로 짜 보았습니다.

실제로 루프 카운트 는 AA() 에서 올라가고, BB()는 AA()의 현재 진행상황을 비동기로 알려주고 있습니다.

예상했던 대로 엄청난 스피드를 보여주더군요^^

120000000 번의 반복을 10초도 안걸려서 끝내버렸습니다.
(Core 2 Duo T7300, 4GB DDR2, Win7, .NET2.0)

쓰레드2의 반복(표시)횟수는 쓰레드1과 동기화를 하지 않고 있으며, 쓰레드1이 끝날 때 같이 끝나게 되어있으므로 매번 카운트 횟수는 다르게 나옵니다.

기존에는 모든 반복카운트에 표시를 해주었다면...

이번에는 중간중간 빼먹어 가면서 표시를 해 주고 있다고 보면 됩니다.

Microsoft Office 2007 삭제 후 ODAC설치.

ORA-01861 literal does not match format string 

원인 : 문자 형식이 일치 하지 않음으로 발생하는 문제.

예) DATE 형식의 칼럼에 String 형식의 값을 대입할 경우... 등

해결) TO_DATE('2009-12-02','YYYY-MM-DD')

그러나 같은 소스파일인데 다른곳에서는 잘 되는 경우...

즉 한 곳에서는 그냥 정상적으로 실행되는 쿼리가 그대로 가져왔는데 안된다면 문자셋을 확인해 보기 바랍니다.

[환경변수] (instant client 10g 기준)

변수 이름 : NLS_LANG // 변수 값 :  KOREAN_KOREA.KO16MSWIN949
변수 이름 : TNS_ADMIN // 변수 값 : C:\Ora\instantclient

* TNS_ADMIN 경로는 자신의 컴퓨터에 오라클 instantclient 가 설치되어있는 경로를 지정합니다.

레지스트리 부분 

HKEY_LOCAL_MACHINE\SOFTWARE\ORACLE
키 : NLS_LANG // 값 : KOREAN_KOREA.KO16MSWIN949

REPLACE
값을 치환합니다.

구문
REPLACE(String, str1, str2)
String 치환할 값이 들어있는 칼럼 입니다.
str1 치환할 대상 값 입니다.
str2 바뀔 값 입니다.

예)
SELECT REPLACE('2001-01-01','-','') FROM DUAL 의 결과값은 
20010101 입니다.

REPLACE()를 붙여서 '-'를 ''로(제거)한 예시 입니다.

구문2
TRUNC(SYSDATE)
SYSDATE 현재 시스템 날짜&시간 입니다.

예)
시스템 날짜 SELECT SYSDATE FROM DUAL 의 결과값은 
2009-11-16 오후 3:06:53 입니다.

TRUNC()를 붙이게 되면 시간부분은 잘려나가게 됩니다.

SELECT TRUNC(SYSDATE) FROM DUAL 의 결과값은
2009-11-16 입니다.