이진 트리 검색, 기수검색은 트리구조를 사용한다. 이때 사용되는 트리는 in-order 방식으로 이진트리 검색의 경우는 좌

C,C++ 공통으로 태그를 사용해 모두 통하게 하려면 다음과 같이 선언해야 한다. typedef struct _tagNode { TCHAR szDir[2048]; struct _tagNode *pNext; } Node; Node test; 맨 윗줄 _tagNode라는 이름을 생략해도 별 무리없지만 정확한 c문법은 아니라고 한다. 앞의 예처럼 구조체 안에서 선언한 구조체의 포인터를 선언하는 경우는 반드시 구조체 안에서는 c문법을 지켜서 struct 태그네임을 붙여야 되는 듯 하다. struct를 생략하면 컴파일 에러났다.(C파일로 테스트해 보았다.)

이분 검색의 삽입방식은 맨 끝에 요소를 놓고 노말하게 삽입정렬을 하는 방식이다. 이 부분을 조금 더 빨리 개선할 수 있는 점이 보인다. 이미 정렬된 상태이므로 find와 유사한 함수를 만들어 들어갈 자리를 쉽게 찾을 수 있으리라 본다. 가령 1,3,5,9,11 등에서 7을 집어 넣는다 할 때 우선 7을 찾아보면 인덱스 2 중간값 5보다 큰 수이므로 오른쪽으로 가고 인덱스 3 중간값 9보다는 작으므로 다시 찾는 루틴을 시도하지만 조건 불만족으로 탈출할 것이다. 탈출시 조사한 곳의 mid값을 가지고 위치판단이 가능할 것이다. 위와 같은 식으로 자리를 찾는 수고를 덜 수 있으리라 본다. 찾을 때 O(N)을 O(lon(2)N) 수준으로 줄인다. 그 뒷자리 메모리를 일괄적으로 한칸씩 미는 수고는 어쩔 수 없지만,..

재귀의 형태로 분할시키고 merge와 sort를 나누는 방식이 보통이다. [code cpp:nocontrols] void MergeSort(int iArray[], int iTemp[], int iStart, int iEnd) { if (iStart < iEnd) { int iMid = (iStart + iEnd)/2; MergeSort(iArray, iTemp, iStart, iMid); MergeSort(iArray, iTemp, iMid + 1, iEnd); Merge(iArray, iTemp, iStart, iMid, iEnd); } } void Merge(int iArray[], int iTemp[], int iLow, int iMid, int iHigh) { int h = iLow, i = i..

이 알고리즘 역시 이해는 어렵지 않다. 트리구조로 파악 후 하위트리들을 작은수를 앞에 놓는 식으로 차례차례 상위로 이동하면서 병합하는 방식이다. 그런데 이해는 쉽게 되는데 선뜻 코드가 바로 짜여지지 않는다. 아무래도 트리구조로 탐색, 이동해야 되니 이동방식에 대한 고민이 만만찮고 배열 갯수가 2의 제곱으로 나누어지지 않는 부분에 대한 처리도 신경써야 되기 때문일 것이다. 여기저기 참고하고, 손질 좀 하고 시간 좀 걸려 짜 놓은 소스를 보니 참 길고 루프문도 많이 사용됨을 볼 수 있었다. 사용된 지역변수가 11개나 된다. 원래 각 트리 단계별로 보통 버퍼에 결과를 저장한 후 다시 원본배열로 이를 복사하는 방식을 사용하기도 하지만 이를 개선하는 방법도 있다.(이재규 알고리즘 서적 참조) 어차피 버퍼와 원본배..

생각보다 코딩 작업이 더디었다. 개념은 이해하기 쉬운 데 막상 코딩을 할려니 이것저것 세밀하게 따져야 하는 부분이 상당수 있어서 그런듯 하다... 시작과 끝 인덱스라든지, 노드 공식, 갯수 파악 등 신경써서 해야하는 부분이 많으므로 시간이 좀 오래 걸렸다. 일부 알고리즘 서적이나 강의에서 계산의 편의로 실제 인덱스에 +1을 하고 작성하는 경우가 있는 데(이재규 알고리즘 참조) 굳이 그렇게 하지 않고 그냥 작성했다. 충분히 직관적으로 쉽게 파악가능하고 어차피 나중에 실제 요소값 바꿀 때는 원래의 인덱스를 취해야 하므로 그렇다. 인트형 무작위 100만개를 입력해 테스트해보았는데 책에서 나오는대로 bottomup방식이 쬐금 더 빨랐다....;;; 퀵소트랑 비교해봣는데 역시 퀵소트한테는 못당한다.... medi..

STL의 sort, stable_sort 알고리즘 분석 및 고찰(왜 이렇게 복잡한 걸까??) 2009/06/11 16:35 [Construction/C++ & STL] STL에 구현된 sort()와 stable_sort()을 알아보기 전에 간략하게 sort의 종류와 시간복잡도에 대해서 설명을 해보도록 하겠다. sort 알고리즘에는 insertion sort, bubble sort, quick sort,... 등 다양한 종류가 있다. 일반적으로 sort 알고리즘을 구분하면 아래와 같이 시간복잡도로 구분을 할 수 있다. O(n^2): insertion sort, bubble sort, selection sort, ... O(nlogn): quick sort, merge sort ... O(n): radix ..

보통 알고리즘 강의에서 NlogN 이런식으로 얼버무리는 경우가 많은 데,,, 이런 부분들을 자세히 밝혔다. 물론 수학을 좀 알아야 수월하게 이해할 것이다.

데브피아 질문글 발췌,,,, 비스타에서는 아직 좀 문제가 있는 듯 하다. 아래는 새 익스플로러창으로 원하는 사이트를 열어주는 함수입니다. XP에서는 문제 없이 잘 열립니다. 그런데 vista에서는 제가 열려고하는 pWebBrowser가 열린다음 새로운 익스플로러창을 또 열려서 그곳에서 사이트가 열려 버리네요. 열고자 하는 pWebBrowser에는 아무런 내용도 나타나지 않구요. 비스타에서는 아래와 같이 사용하면 안되는것인지 궁금합니다. // IWebBrowser2를 사용하여 사이트를 여는 함수 BOOL CExplorerPopup::OpenNewWindow(LPCTSTR pAddress) { IWebBrowser2 *pWebBrowser; HRESULT hr; // 웹브라우저 객체를 생성한다. hr = :..