반응형

안녕하세요 단편으로는 처음 쓰는 것 같습니다.

이 단락으로는 조금 어색할 지도 모르겠지만 윈도우 에서 지원하는 INI 파일의 입출력 입니다.

그래서 API 의 메뉴에 쓰게 됩니다.

게임이나 기타 유틸등을 만들때 상당히 파일 입출력에 대해 고민을 하게 됩니다.

그래서 이번에 이렇게 글을 올리게 됩니다.

아직 모르시는 분이 있을지? 도 몰라서 ^^;

여기에서 쓰이는 함수에는 여러가지가 있습니다.

그 중에서도 가장 많이 쓰이는 Int 형과 String 형에 대해 알아보겠습니다.

struct 와 Section 이 있지만 Section 은 거의 쓰이지 않는 편 이고 Struct 와 같은 경우는 바이너리로 쓰는게 더 편하기 때문에^^; 생략합니다.

미리 알아 두어야 할 점은 쓰기에는 STRING 으로 INT 를 그냥 쓸수 있어서 INT 형을 쓰는 함수는 없습니다.

그리고 INI 파일에 쓰이는 형식이 있습니다.

[TITLE] //단락의 시작

NAME = JAEJIN //변수 = 값

이런 식 으로 되어 있습니다. 단락의 시작으로 부터 그 아래의 값들을 찾는 형식으로 되어 있습니다. 단락은 대 괄호로 나타내구요^^

첫번째로 쓰기에 쓰이는 함수는

WritePrivateProfileString 입니다.

WINBASEAPI
BOOL
WINAPI
WritePrivateProfileStringA(
IN LPCSTR lpAppName,
IN LPCSTR lpKeyName,
IN LPCSTR lpString,
IN LPCSTR lpFileName
);

선언에는 이렇게 되어 잇습니다.

lpAppName 에는 단락의 시작 의 이름이 들어 갈 것이고,

lpKeyName 은 변수가 들어 갑니다.

lpString 은 값이 들어 갈 것이고

lpFileName 에는 파일의 경로와 이름이 들어갑니다.

#include <windows.h>


int _tmain(int argc, _TCHAR* argv[])
{
::WritePrivateProfileString( "TITLE", "STRING_KEY", "NAME", "./TEST.INI" );
::WritePrivateProfileString( "TITLE", "NUMBER_KEY", "1024", "./TEST.INI" );
}

자 이렇게 쓴다면 INI 파일에는

[TITLE]
STRING_KEY=NAME
NUMBER_KEY=1024

이렇게 기록이 될 것 입니다.

눈으로 보이기 때문에 상당히 편안한 점이 있습니다.

자 그다음은 읽기 차례 입니다. 위에서는 String 으로 썼지만 NUMBER_KEY 는 INT 형 입니다.

그래서 타입 캐스팅을 하지 않기 위해 INT 형을 읽는 함수가 제공이 됩니다.

여기서 제공 되는 함수는

GetPrivateProfileString

GetPrivateProfileInt

2가지 입니다.

WINBASEAPI
DWORD
WINAPI
GetPrivateProfileStringA(
IN LPCSTR lpAppName,
IN LPCSTR lpKeyName,
IN LPCSTR lpDefault,
OUT LPSTR lpReturnedString,
IN DWORD nSize,
IN LPCSTR lpFileName
);

일단 String 의 원형은 이렇게 됩니다.

lpAppName 은 단락의 시작을 쓰시면 됩니다.

lpKeyName 은 변수가 될 것 이고,

lpDefault 는 만약 저 변수가 없다면 기본으로 읽을 대체문자열을 나타냅니다.

lpReturnString 은 값을 받을 버퍼를 나타내고,

nSize 는 버퍼의 사이즈를 입력 하면 됩니다.

lpFileName 은 파일을 읽을 경로와 이름을 쓰시면 됩니다.

WINBASEAPI
UINT
WINAPI
GetPrivateProfileIntA(
IN LPCSTR lpAppName,
IN LPCSTR lpKeyName,
IN INT nDefault,
IN LPCSTR lpFileName
);

Int 의 원형 입니다.

lpAppName 은 단락의 시작을 쓰시면 되고

lpKeyName 은 변수입니다.

nDefault 는 값을 못찾으면 대체로 쓸 숫자를 적고,

lpFileName 은 파일의 경로와 이름을 쓰시면 됩니다.

#include <windows.h>


int _tmain(int argc, _TCHAR* argv[])
{

char szBuffer[ 256 ] = {0, };
::GetPrivateProfileString( "TITLE", "STRING_KEY", "Unknown", szBuffer, 256, "./TEST.INI" );
int iResult = ::GetPrivateProfileInt( "TITLE", "NUMBER_KEY", 0, "./TEST.INI" );

}

아까 썼던 것을 다시 읽는 소스 입니다.

아까 TITLE 이란 단락으로 STRING_KEY 에 NAME 이란 값을 입력 했습니다. 만약 이 단락을 찾지 못하면 Unknown 이라는 STRING 이

szBuffer 에 찰 것이고, 찾았다면 NAME 이라는 값이 Buffer 에 들어옵니다.

아래 것도 마찬가지로 TITLE 이라는 단락으로 NUMBER_KEY 에 1024 를 썼습니다. 찾지 못하면 0 이 리턴되고 찾았다면 1024가 리턴 될 것 입니다.

소스도 첨부 하겠습니다.

이제는 txt 로 노가다 뛰시는 분들은 텍스트 노가다를 줄여 주시고. 텍스트는 그리고 위험하게 버퍼가 어긋나면

바로 뻑이 납니다.

그래서 저는 이걸 자주 씁니다^^

주의 할 점은 마지막 인자에 FileName 을 쓰는데 앞에 ./ 를 꼭 붇여서 CurrentFolder 라고 명시를 하셔야 합니다.

하지 않으면 못 읽습니다.

또 유용한 점이 있다면 게임을 만드는 개발자 입니다.

유저의 해상도를 파일에 기록하여 런처를 만든다고 합시다. 그러면 int 형으로 기본 1024 로 기록을 하였다 한다면,

유저가 이걸 1280 으로 바꾸었습니다. 하지만 Read 시에 해상도의 단락을 찾지 못하면,

여기에 있는 Default 로 1024로 마춰 줄 수도 있습니다.

짧은 내용이고 대부분 많은 분들이 아는 내용이지만. 혹여나 해서 올려봅니다^^


반응형

'프로그래밍(Programming) > c++, 11, 14 , 17, 20' 카테고리의 다른 글

함수포인터  (0) 2012.10.31
GetAsyncKeyState  (0) 2012.10.31
forceinline VS inline  (0) 2012.10.31
보다 더 완성도 있는 프로그램을 위한 assert(0) 함수  (0) 2012.10.31
enum with namespace  (0) 2012.10.31
반응형

inline : 컴파일시 알아서 인라인으로 함수를 만들지의 여부를 결정

forceinline : 무조건 inline 으로 생성

반응형
반응형

assert

assert는 코드 차원에서 프로그램의 안정성을 높이는 역할을 한다. assert라는 단어를 영한 사전에서 찾아 보면 "단언하다, 확실히 하다"라는 뜻을 가지고 있는데 코드가 정확하게 동작할 수 있는 상황이라는 것을 확인한다. 함수는 입력과 출력을 가지는데 입력이 정확하면 출력도 항상 정확하지만 호출부에서 틀린 값을 주면 함수를 아무리 잘 만들어도 안정적인 동작을 할 수 없다. 예를 들어 다음 함수를 보자.

int divide(int a, int b)

{

return a/b;

}

이 함수는 인수로 주어진 두 정수 a와 b의 나누기 연산을 하여 그 결과를 리턴하는데 divide(6,3)을 호출하면 당연히 2라는 결과를 리턴할 것이다. a와 b만 정확하다면 이 함수가 절대로 틀릴 수 없겠지만 만약 나누는 수 b가 0이면 이 함수는 치명적인 에러를 일으키고 다운되어 버릴 것이다. 이런 에러를 방어할 때는 통상 if문을 사용하는데 if는 어디까지나 에러를 피해 다니는 방법이지 에러를 근본적으로 수정하는 방법은 아니다.

이런 에러를 수정하려면 결국 호출부가 b로 0을 전달하지 않도록 해야 하며 개발자는 이런 상황이 발생했을 때 호출부를 수정해야 한다. divide 함수에 필요한 코드는 b가 0이 되었을 때를 적발해 내는 감시 코드인데 이럴 때 assert문을 사용한다. assert는 assert.h 헤더 파일에 정의되어 있는 매크로 함수이므로 이 헤더 파일을 인클루드해야 한다.

: Assert

#include <Turboc.h>

#include <assert.h>

int divide(int a, int b)

{

assert(b!=0);

return a/b;

}

void main()

{

divide(6,3);

divide(1,0);

}

assert 함수는 표현식을 인수로 전달받아 이 인수가 참인지를 점검한다. 조건이 참이면 이 함수는 아무 일도 하지 않지만 거짓이면 에러 발생 위치와 표현식 등으로 구성된 상세한 에러 메시지를 출력하고 프로그램을 강제로 종료시킨다. assert는 괄호안의 조건식이 확실히 맞는지 확인하는 역할을 하는데 assert (b!=0); 문은 b가 0이 아니라는 것을 확실히 하라는 뜻이다. 특정 시점에서 반드시 참이어야 하는 조건을 assert 의 인수로 작성한다. 그렇다면 다음과 같이 쓰는 것과는 무엇이 다를까?

int divide(int a, int b)

{

if (b==0) exit(-1);

return a/b;

}

이 코드는 b가 0일 때 프로그램을 강제로 종료함으로써 아래의 a/b 연산을 하지 않도록 하기는 하지만 왜 프로그램이 종료되었는지는 알려 주지 못한다. 반면 assert는 버그가 있다는 것 뿐만 아니라 프로그램이 어디서 어떤 이유로 종료되었는지를 자세히 알려준다. 이 예제의 main에서 b로 0을 넘기고 있으므로 이대로 실행하면 다음과 같은 에러 메시지가 출력된다.

Assertion failed: b!=0, file C:\CExam\Assert\Assert.cpp, line 6

Assert.cpp의 6번째 줄에서 b!=0 조건이 맞지 않아서 프로그램이 종료되었다는 것을 표시하고 있다. 콘솔 프로젝트는 이 메시지가 stderr 표준 출력(결국 화면)으로 나타나지만 그래픽 프로젝트에서는 다음과 같은 대화상자가 나타나며 이 대화상자로 에러 위치와 원인을 정확하게 알 수 있다.

개발자는 이 메시지를 받았을 때 다시 시도 버튼을 누른 후 중단된 시점의 콜 스택과 주요 변수의 상태를 확인하여 에러의 원인을 쉽게 알 수 있다. 위치만 알면 원인과 해결책은 금방 파악된다. 디버깅은 버그를 고치는 작업이라기보다는 버그를 찾아 내는 것이며 찾기만 하면 고치는 것은 아주 쉽다.

그렇다면 assert가 없을 때와는 또 무엇이 다를까? 어차피 이 예제를 실행하면 바로 다음 행의 나누기 연산식에서 에러가 발생하며 프로그램은 강제로 종료된다. 프로그램이 죽는다는 것을 알면 디버거로 단계 실행해서 죽은 위치와 원인을 알아 내는 것도 가능하다. 그러나 예외가 발생하는 시점과 예외의 원인이 발생하는 시점이 이 예제처럼 인접해 있는 경우보다는 그렇지 못한 경우가 훨씬 더 많다. 다음 예제를 보자.

: Assert2

#include <Turboc.h>

#include <assert.h>

size_t getsize()

{

int size;

size=0;

return size;

}

void main()

{

char *p;

int size;

size=getsize();

p=(char *)malloc(size);

strcpy(p,"test");

free(p);

}

getsize 함수는 어떤 대상의 크기를 조사하며 main은 이 함수가 조사한 크기만큼 메모리를 할당해 사용한다. 어떤 에러로 인해 getsize가 크기를 제대로 조사하지 못해 0으로 조사했다고 하자. 이럴 때 프로그램이 죽는 위치는 getsize가 아니라 이 잘못된 크기를 사용하는 곳인데 이 예제의 경우 strcpy 또는 free에서 죽을 수 있다. 에러의 원인은 getsize가 제공했지만 이 에러가 문제가 된 곳은 main인 것이다. 이럴 때 getsize에 assert 문을 작성한다.

size_t getsize()

{

int size;

size=0;

assert(size >= 6);

return size;

}

이렇게 해 두면 getsize에서 문제가 발생하는 즉시 assert가 이대로 두면 위험하다는 것은 적극적으로 알린다. 좀 더 대규모의 프로젝트에서는 최초 발생한 에러가 수천줄 이후에나 말썽을 일으키기도 하는데 이럴 때 죽은 자리의 코드만 봐서는 어디서부터 꼬였는지 찾기 대단히 어렵다. 그래서 에러의 원인이 될만한 곳에 assert를 삽입하여 미리 오동작을 발견하고자 하는 것이다.

assert는 가급적 많이 사용하는 것이 좋다. 조금이라도 의심이 가는 부분에 대해서는 항상 assert문을 삽입하여 조건을 확실히 만족하는지 점검해야 한다. assert는 에러를 잡기 위한 일종의 덫인 셈인데 덫을 많이 놓을수록 에러가 걸려들 확률은 높아지고 프로그램의 안전성이 향상된다. assert는 또한 문서화에도 도움을 주는데 코드를 읽는 사람에게 함수가 동작하기 위한 전제 조건을 잘 설명한다. 주석보다 오히려 assert가 더 간결한 설명문이다.

assert는 아무리 많이 써도 최종 프로젝트의 성능이나 크기와는 상관이 없다. 왜냐하면 assert 는 조건부 컴파일로 정의되어 있는 매크로 함수이기 때문이다. assert 매크로가 어떻게 정의되어 있는지 assert.h 헤더 파일을 보자. 이 정의문에 있는 조건부 컴파일 지시자와 # 연산자 등에 대해서는 다음에 상세하게 배울 것이다.

#ifdef NDEBUG

#define assert(exp) ((void)0)

#else

#define assert(exp) (void)( (exp) || (_assert(#exp, __FILE__, __LINE__), 0) )

#endif /* NDEBUG */

디버그 버전일 때 assert는 인수로 주어진 exp를 평가하고 이 값이 참이면 _assert 함수를 호출한다. 쇼트 서키트 기능에 의해 exp가 참이면 전체 식이 이미 참으로 판명났으므로 _assert 함수는 호출되지 않는다. _assert는 에러가 발생한 수식과 위치를 콘솔 또는 대화상자로 출력하고 프로그램을 종료하는 진짜 함수이되 exp가 거짓일 때만 호출된다.

릴리즈 버전일 때 assert는 그냥 0으로 평가되는 빈 문장이므로 프로그램의 속도를 감소시키지도 않고 크기를 늘리지도 않는다. 조건부 컴파일 지시자에 의해 assert를 한 번에 솎아낼 수 있는 장치가 마련되어 있으므로 필요한 곳에 마음껏 써도 상관없다. 그래서 완벽주의를 지향하는 개발자의 소스를 보면 코드만큼이나 assert가 많이 포함되어 있는 경우도 있다. 다음은 assert문의 주의 사항이다.

assert 매크로는 디버거 버전에서만 컴파일되므로 assert의 인수로는 생략해도 상관없는 조건식만 넣어야 한다. 릴리즈 모드에서도 실행해야 하는 의미 있는 동작을 assert 문에 작성해서는 안된다. 다음 코드를 보자.

assert((pSet=DoQuery())!=NULL);

pSet의 결과 출력

이 코드는 데이터 베이스에 질의를 보내 결과 셋을 받는데 결과 셋이 NULL이 아니라는 것을 확인하기 위해 assert문을 사용했다. 디버거 모드에서는 이 문장이 제대로 실행되지만 릴리즈 모드로 바꾸면 DoQuery 함수가 호출되지 않으므로 pSet은 쓰레기값을 가질 것이다. 이 코드가 확인하고자 하는 것은 결과 셋이 제대로 조사되었는가 아닌가이므로 DoQuery 호출문은 빼고 pSet값을 비교하는 조건문만 assert에 넣어야 한다.

pSet=DoQuery();

assert(pSet!=NULL);

pSet의 결과 출력

일단 DoQuery를 호출하여 결과를 조사하고 assert문으로 결과가 제대로 조사되었음을 확인했다. pSet!=NULL은 단순한 조건문일 뿐이므로 릴리즈 모드에서 이 조건문이 빠져도 아무 상관이 었다. assert는 어디까지나 확인용 함수일 뿐이므로 변수의 값을 바꾸거나 프로그램의 상태를 변경하는 코드는 assert안에 둘 수 없다.

assert는 절대로 발생해서는 안되는 조건에 대해서 사용하는 것이지 정상적인 에러 상황을 처리하는 문장이 아니다. 위 예에서 DoQuery 함수는 반드시 결과를 돌려 주는 것으로 가정하고 있으며 만약 질의 결과에 해당하는 레코드가 하나도 없다면 빈 결과셋이라도 리턴할 것이다. DoQuery가 실패하는 상황도 정상적이라면 assert 대신 if문을 사용해야 한다. 다음 예를 보자.

ch=getch();

assert(isalphs(ch));

입력한 영문자에 따른 작업

이 코드는 ch로 반드시 영문자만 입력하도록 요구하며 사용자는 반드시 영문자 중 하나를 입력하도록 강요한다. 사용자가 설사 입력을 잘못했다고 해서 프로그램이 종료되어서는 안되므로 여기에 사용된 assert문은 적합하지 않다. 잘못 입력했으면 다시 입력하라는 메시지를 출력하는 것이 정상적이지 프로그램이 종료되면 어떻게 되겠는가? 사용자는 언제나 실수할 가능성이 있으며 이런 상황은 아주 정상적인 처리 과정일 뿐 예외가 아니므로 여기에는 if문을 사용해야 한다.

assert 문에 조건을 작성할 때는 가급적이면 한 조건당 하나의 assert를 쓰는 것이 좋다. 줄 수를 줄이고자 여러 개의 조건을 하나의 assert에 넣는 것은 좋지 않다.

assert (a!=0 && p!=NULL && b==0);

이렇게 하면 셋 중 하나라도 거짓일 때 에러 메시지가 출력되기는 하지만 에러 메시지만으로는 셋 중 어떤 문제로 인해 프로그램이 정지되었는지 바로 알 수 없다. 세 개의 assert 문으로 각각 분리해 놓으면 어떤 조건이 거짓인지를 바로 알 수 있다. assert는 아무리 많아도 성능에 영향을 주지 않으므로 굳이 한 줄로 압축할 필요없이 에러 메시지로부터 원인을 바로 알 수 있도록 하는 것이 좋다.

C 라이브러리가 제공하는 표준 assert 매크로 외에도 각 라이브러리나 언어, 개발툴이 제공하는 고유한 확인 함수들이 있다. 예를 들어 MFC 라이브러리는 ASSERT, _ASSERT 등의 매크로를 제공하는데 약간의 기능 차이와 출력하는 메시지의 내용이 다를 뿐 사용하는 방법이나 목적은 동일하다.

출처 : www.winapi.co.kr

반응형

'프로그래밍(Programming) > c++, 11, 14 , 17, 20' 카테고리의 다른 글

GetPrivateProfileStringA  (0) 2012.10.31
forceinline VS inline  (0) 2012.10.31
enum with namespace  (0) 2012.10.31
eula.1028.txt 의 정체  (0) 2012.10.31
try , catch 예외처리를 쓰는 경우..  (0) 2012.10.31
반응형

namespace TYPES{

enum TYPE{ ZERO,ONE,TWO }; //열거형 선언

// 0 , 1 , 2 // 0,1,2 의 순인 n=n+1 으로 증가한다 , 단 n = 정수
};

int main(){

TYPES::TYPE m_data;

m_data=TYPES::TWO; //m_data 는 이름공간 안에 있는 열거형의 값을 담을 수 있는 열거형 변수

cout<<m_data<<endl;
}

출력 결과

2

* 이름 공간을 사용하는 이유 : 거대한 프로젝트에서 enum 은 이름 중복을 발생시킬 수 있는 문법중 하나인데

이를 효율적으로 방지하고자 이름공간(namespace) 를 사용한다

반응형
반응형





기준: Visual Studio 2008 Professional KOR.

 

C++ Win32 프로젝트를 추가하면 기본적으로 32비트 환경으로 Debug/Release가 생깁니다.

기존에 있는 Win32용 빌드 구성을 이용해서 x64용으로 구성을 복사할 수 있다.

 

'Hello64 프로젝트'로 64비트 환경 구축하기

Win32 콘솔 애플리케이션 프로젝트를 생성해서 64비트용으로 빌드를 해보겠다.

 

우선 VS2008을 실행하고, 새 프로젝트에서 Win32 콘솔 응용 프로그램을 생성한다.
이미 익숙하다고 가정하고 스크린샷을 붙인다.

1_make_proj.png 

 

'빈 프로젝트'를 선택한다.

2_empty_proj.png

 

간단하게 cpp파일을 추가하고 main()함수를 타이핑합니다.

3_main.png 

빌드를 해보면 별다른 성공해야 합니다.

 

기존 프로젝트에 솔루션 플랫폼 도구모음에 보면 기본적으로 Win32용으로 선택된 플랫폼이 있습니다.

"구성 관리자..." (Configuration Manger) 를 선택하면 아래와 같은 창이 나옵니다.

4_setup_configuration.png  

 

"새로 만들기..." (New...) 를 선택해서 '새 플랫폼 입력 또는 선택' (Type or select the new plaform:)에서 x64를 선택하고

5_configuration_new.png 

 

다음 나오는 창에서 '새 플랫폼 입력 또는 선택'에서 X64를 선택해 줍니다.

6_new_platform.png 

 

이후에 보면 기존의 'Win32'이외에 x64가 있습니다. 선택하고 빌드를 해봅니다.

7_build64.png 

 

출력되는 경로는 [프로젝트 경로]\x64 폴더 아래에 Debug 혹은 Release 폴더가 생긴다.

아래 그림은 Release로 빌드를 했다.

8_output_exe.png 

 

32비트로 빌드한 것과 비교해본다.(위: 64비트 / 아래: 32비트)

9_compare_32vs64.png 

아래 부분에서 선택한 영역은 'IMAGE_NT_HEADER' 영역의 시작부분인 Machine이다. (winnt.h에 정의되어 있다)

  1. typedef struct _IMAGE_FILE_HEADER {

        WORD    Machine;

        WORD    NumberOfSections;

        DWORD   TimeDateStamp;

        DWORD   PointerToSymbolTable;

        DWORD   NumberOfSymbols;

        WORD    SizeOfOptionalHeader;

        WORD    Characteristics;

    IMAGE_FILE_HEADER, *PIMAGE_FILE_HEADER;

 

WinNT.h에 있는 매크로의 정의를 보면 다음과 같다. (리틀엔디안이라 Byte order가 다르다)

  1. #define IMAGE_FILE_MACHINE_I386              0x014c  // Intel 386.

     

  2. ...

    #define IMAGE_FILE_MACHINE_AMD64             0x8664  // AMD64 (K8)

  3. ...

 

참고(PE)

IMAGE_NT_HEADER는 IMAGE_NT_HEADERS의 서브셋(부분집합)이다.

IMAGE_NT_HEADERS는 크게 3가지 타입이 있는데 IMAGE_NT_HEADERS64, IMAGE_NT_HEADERS32, IMAGE_ROM_HEADERS 이다.

3가지의 차이는 앞부분 PE시그너처랑 는 동일하고 뒷부분의 OptionalHeader 만 다르다.

  1. typedef struct _IMAGE_NT_HEADERS {

        DWORD Signature;

        IMAGE_FILE_HEADER FileHeader;

        {IMAGE_OPTIONAL_HEADER64 or IMAGE_NT_HEADERS32 or IMAGE_ROM_HEADERS} OptionalHeader;

    IMAGE_NT_HEADERS, *PIMAGE_NT_HEADERS;

 

IMAGE_FILE_HEADER 바로 전에 PE시그너처가 있는데 '50 45 00 00'이 바로 그것이다. (아래는 리틀엔디안 표현이라서 순서가 바뀌어져있다)

  1. #define IMAGE_NT_SIGNATURE                  0x00004550  // PE00

 

PE_signature.png 

 

참고(엔디안)

빅 엔디안: 높은 자리수를 먼저 저장(모토롤라 계열) - 사람이 읽기에 편함

리틀 엔디안: 낮은 자리수를 먼저 저장(인텔 계열) - 기계가 연산시에 편리(캐리지가 발생시 -> 방향으로 진행 가능)

image002.gif 

 

반응형
반응형

http://doodoori2.tistory.com/197

eula.1028.txt
eula.1031.txt
eula.1033.txt
eula.1036.txt
eula.1040.txt
eula.1041.txt
eula.1042.txt
eula.2052.txt
eula.3082.txt
globdata.ini
install.exe
install.ini
install.res.1028.dll
install.res.1031.dll
install.res.1033.dll
install.res.1036.dll
install.res.1040.dll
install.res.1041.dll
install.res.1042.dll
install.res.2052.dll
install.res.3082.dll
VC_RED.cab
VC_RED.MSI
vcredist.bmp


Visual C++ redistributable package 가 배포되면서 생기는 임시 파일이란다
압축을 그냥 무식하게 C:\ 혹은 D:\ 에다가 풀어버리고
설치한다음에 지우지 않은 것.

이미 설치된 상황일테니까 그냥 지워주면 된다.


http://answers.microsoft.com/en-us/windows/forum/windows_7-system/what-is-eula1028text-on-c/042cf4d8-0425-430f-88ca-b35da9439cfd

반응형
반응형

http://www.microsoft.com/download/en/confirmation.aspx?id=27543



Today in the BUILD keynote I had the opportunity to show some of the new functionality in Microsoft® Visual Studio® 11 Developer Preview and Microsoft® Team Foundation Server Preview. MSDN subscribers can download the previews today as well as the new release of .NET Framework 4.5 Developer Preview; general availability is on Friday, September 16.

Some exciting announcements are being made here at BUILD. Visual Studio 11 provides an integrated development experience that spans the entire lifecycle of software creation from architecture to code creation, testing and beyond. This release adds support for Windows 8 and HTML 5, enabling you to target platforms across devices, services and the cloud. Integration with Team Foundation Server enables the entire team to collaborate throughout the development cycle to create quality applications.

.NET 4.5 has focused on top developer requests across all our key technologies, and includes new features for Asynchronous programming in C# and Visual Basic, support for state machines in Windows Workflow, and increased investments in HTML5 and CSS3 in ASP.NET.

We’ve shared a lot at BUILD already, for more on the future of Windows development I suggest you take a look at Steven Sinofskyand S. Somasegar’s blogs. More details on Team Foundation Server including the new service announced at BUILD and how we’re helping teams be more productive can be found on Brian Harry’s blog.

Quick Tour around Visual Studio 11 Features

Visual Studio 11 has several new features, all designed to provide an integrated set of tools for delivering great user and application experiences; whether working individually or as part of a team. Let me highlight a few:

Develop Metro style Apps for Windows 8

Visual Studio 11 includes a set of templates that get you started quickly developing Metro style applications with JavaScript, C#, VB or C++. The blank Application template provides the simplest starting point with a default project structure that includes sample resources and images. The Grid View, Split View, and Navigation templates are designed to provide a starting point for more complex user interfaces.

From Visual Studio 11, seamlessly open up your Metro style app with JavaScript in Expression Blend to add the style and structure of your application.

Due to the dynamic nature of HTML it is often difficult to see how a web page is going to look unless it is running. Blend’s innovative interactive design mode enables you to run your app on the design surface as a live app instead of a static visual layout.


Enhancements for Game Development

We have added Visual Studio Graphics tools to help game developers become more productive, making it easier to build innovative games. Visual Studio 11 provides access to a number of resource editing, visual design, and visual debugging tools for writing 2D / 3D games and Metro style applications. Specifically, Visual Studio Graphics includes tools for:

Viewing and basic editing of 3D models in Visual Studio 11.

Viewing and editing of images and textures with support for alpha channels and transparency.

Visually designing shader programs and effect files.

Debugging and diagnostics of DirectX based output.

Code Clone Analysis

Visual Studio has historically provided tools that enable a developer to improve code quality by refactoring code. However this process depends on the developer to determine where such reusable code is likely to occur. The Code-Clone Analysis tool in Visual Studio 11 examines your solution looking for logic that is duplicated, enabling you to factor this code out into one or more common methods. The tool does this very intelligently; it does not just search for identical blocks of code, rather it searches for semantically similar constructs using heuristics developed by Microsoft Research.

This technique is useful if you are correcting a bug in a piece of code and you want to find out whether the same bug resulting from the same programmatic idiom occurs elsewhere in the project.

Code Review Workflow with Team Explorer

Visual Studio 11 Preview works hand in hand with Team Foundation Server 11 to provide best in class application lifecycle management. Visual Studio 11 facilities collaboration is by enabling developers to request and perform code reviews through using Team Explorer. This feature defines a workflow in Team Foundation Server that saves project state and routes review requests as work items to team members. These workflows are independent of any specific process or methodology, so you can incorporate code reviews at any convenient point in the project lifecycle.

The Request Review link in the My Work pane enables you to create a new code review task and assign it to one or more other developers.

The reviewer can accept or decline the review, and respond to any messages or queries associated with the code review, add annotations and more. Visual Studio 11 displays the code by using a “Diff” format, showing the original code and the changes made by the developer requesting the review. This feature enables the reviewer to quickly understand the scope of the changes and work more efficiently.

Exploratory Testing and Enhanced Unit Testing

As development teams become more flexible and agile, they demand adaptive tools that still ensure a high commitment to quality. The Exploratory Testing feature is an adaptive tool for agile testing that enables you to test without performing formal test planning. You can now directly start testing the product without spending time writing test cases or composing test suites. When you start a new testing session, the tool generates a full log of your interaction with the application under test. You can annotate your session with notes, and you can capture the screen at any point and add the resulting screen shot to your notes. You can also attach a file providing any additional information if required. With the exploratory testing tool you can also:

  • File actionable bugs fast. The Exploratory Testing tool enables you to generate a bug report, and the steps that you performed to cause unexpected behavior are automatically included in the bug report.

  • Create test cases. You can generate test cases based on the steps that caused the bugs to appear.

  • Manage exploratory testing sessions. When testing is complete, you can return to Microsoft Test Manager, which saves the details of the testing session and includes information such as the duration, which new bugs were filed, and which test cases were created.

What’s New in .NET 4.5

.NET 4.5 has focused on our top developer requests. Across ASP.NET, the BCL, MEF, WCF, WPF, Windows Workflow, and other key technologies, we’ve listened to developers and added functionality in .NET 4.5. Important examples include state machine support in Windows Workflow, and improved support for SQL Server and Windows Azure in ADO.NET. ASP.NET has increased investments in HTML5, CSS3, device detection, page optimization, and the NuGet package system, as well as introduces new functionality with MVC4. Learn more at Scott Guthrie’s blog.

.NET 4.5 also helps developers write faster code. Support for Asynchronous programming in C# and Visual Basic enables developers to easily write client UI code that doesn’t block, and server code that scales more efficiently. The new server garbage collector reduces pause times, and new features in the Parallel Computing Platform enable Dataflow programming and other improvements.

Start Coding

Visual Studio 11 includes several new features which will help developers collaborate more effectively while creating exciting experiences for their users. Here are some are some resources to help you get started.

반응형
반응형

http://www.microsoft.com/visualstudio/kor/downloads

Visual Studio 2012 평가판 소프트웨어 및 언어 팩

팀 규모나 프로젝트의 복잡성을 불문하고 Team Foundation Server에서 Visual Studio 2012를 사용하면 아이디어를 실제 소프트웨어로 구현하는 데 도움이 됩니다. 지금 Visual Studio 2012를 설치하여 시험해 보고 미래형 개발 도구를 손에 넣으십시오.

MSDN Subscriber는 다음에서도 다운로드 가능 MSDN Subscriber 다운로드.

Premium 2012 설치
지금 설치

Team Foundation Server 설치
지금 설치

Ultimate

Premium

Professional

Test Professional

Team Foundation Server

Visual Studio Express 2012

Visual Studio Express 2012 제품은 최신 플랫폼에서 현대적인 응용 프로그램을 만들어 내는 무료 개발 도구를 제공합니다.

Visual Studio Express 2012 for Web

Visual Studio Express 2012 for Windows 8

Visual Studio Express 2012 for Windows Desktop

Visual Studio Express 2012 for Windows Phone

Visual Studio Team Foundation Server Express 2012

반응형
반응형

google_protectAndRun("render_ads.js::google_render_ad", google_handleError, google_render_ad);
VB로 만든 프로젝트 솔루션에
MFC로 만든 프로젝트를 몇개 추가하고
빌드 모드를 기본 DEBUG와 RELEASE말고 하나 더 추가하여
컴파일 했더니 MFC프로젝트는 안되더라
검색해도 나오지도 않고 이상한 이야기만 하더라

답은 간단했다.

솔루션-마우스 우클릭-속성-구성속성-구성-빌드탭의 체크박스를 모두 체크해주자

반응형
반응형

첨부파일 mt.exe


http://coinz.tistory.com/455

아래처럼 해도 안되면 프로젝트 안에 빌드한 폴더안에 mt.exe 를 복사해 넣으면됨

반응형
반응형

http://blog.daum.net/enter2824/13006512

NAT Service. 이건 또 뭐야?

바쁘다는 핑계로 한동안 회사 컴퓨터 관리를 소홀히 했더니 인터넷 속도가 좀 느려지고, 다중작업시 컴퓨터가 느려졌습니다.
아직도 펜티엄 컴퓨터를 회사서 사용하고 있는중이라 조금만 이상있어도 바로 표가 나서 항상 신경을 써서 관리하는데 근래 좀 바빠서 신경을 못 썼더니 바로 이렇게 표가 나네요.

그러다 알아낸 내용입니다.

웹하드를 오랫동안 사용해온 이들이라면 중소규모 웹하드를 중심으로 상당수의 업체들이 반강제적으로 사용자의 PC에 그리드 프로그램을 설치해 네트워크 자원을 빼간다는 사실을 알고 있을 것이다.

웨하드 다운로더에 포함되어있기에 웹하드를 쓰면 반드시 깔아놓을 수 밖에 없는데, 그렇다고 그냥 놔두자니 인터넷 속도 저하의 주범에 하드디스크 자료를 빼내갈지도 모른다는 의구심을 떨칠 수 없어 무척이나 짜증나는 프로그램들이다. (무료사용자도 아니고 정액/ㅍ패킷 결제를 한유료 사용자에게까지 강제적으로 깔리니 더 열통터질 지경)

이러한 그리드로는 ExpressService.exe, Qdownservice.exe 등이 대표적인데, 최근 들어 비슷한 녀석이 하나 더 기승을 부리고 있어 p2pnews 회원들에게 알리고자 한다.

그것은 바로 NET Service다.

본 소프트웨어는 다운로드 속도 향상을 위해, 본 소프트웨어를 통해 다운받은 컨켄츠에 한하여 그리드 기술을 적용하며, 본 소프트웨어를 통해 다운받지 않은 파일, 컨텐츠에 대해서는 어떠한 기술적인 접근, 전송 , 관리의 대상으로 하지 않습니다.

얼마전부터 대형 웹하드 등에서도 갑작스레 몰래 이용약관을 바꾸어 배포하기 시작한 그리드로 기존 그리드와 마찬가지로 아주 짜등나는 녀석이다.

아 녀석이 깔린 PC는 해당 웹하드를 사용하지 않을 때에도 제멋대로 몰래 네트워크 자원을 마구 쓴다는 애기다.

따라서 웹하드 사용자 중 갑자기 다운로더를 다시 설치하라고 한다던지 혹은 이유없이 하드를 긁는 소리가 난다, 인터넷이 버벅인다 싶은 이가 있다면 반드시 이 프로그램이 깔였는지 확인해보고 대책을 세워야 한다.

그런데 문제는 해당 그리드가 없으면 문제를 일으키는 웹하드가 있다는 것이다. 또 문제를 일으키지는 않더라도 그리드 프로그램이 삭제되어있으면 다음 다운로드시에 자동으로 다시 깔아버리기에 웹하드를 사용하려면 울며 겨자먹기로 해당 프로그램을 띄워놓을 수 밖에 없어 난감한 상황을 맞이할 수가 있다.


- 해결 방법

해당 서비스를 중지시켜 네트워크 자원을 못쓰게 한다.


1. 시작 → 실행 창에서 services.msc 를 입력해서 서비스창을 불러옵니다.

2. 서비스(로컬) 창에서 NATService 항목을 찾아 더블클릭합니다.

3. 그럼 NATService 속성 창이 뜹니다.
여기서 시작유형을 사용 안 으로, 서비스 상태를 중지(T)를 클릭하여 프로그램 상태를 중지시킵니다.

4. msconfig에서 서비스 항목에 보면 이렇게 NATService라고 떡하니 실행 중 입니다.
이 항목 앞에 있는 체크표를 없애주고 적용(A)을 누른후 재부팅 합니다.


이렇게 하면 해당서비스를 사용하지 않게 됩니다.

이렇게 해뒀더니 컴퓨터가 좀 쓸만해 졌네요..^^

※ 이렇게해도 불안하신분들은 방화벽 등을 이용하여 해당 프로그램을 차단하여 실행을 막으시면 됩니다.
웹하드를 쓰지 않으신다면 이런 불필요한 작업은 필요없으실 겁니다만, 그렇지 않다면 어쩔수 없이 이런 불편한 방법을 써서라도 조심을 해야 합니다. 

반응형
반응형

DAG 공정 모델링( 공정 흐름 - 순서적인 걸 따질때 )

Reachabilitiy : 도달 가능성(방향 그래프에서 어느정점에서 어느 정점까지 도달 할 수 있는 지를 보는 것)

Transitive Closure : 우회적으로 어느 정점에서 어느 정점까지 도달 할 수 있는 것을 보느 것

결국 두개는 모든 정점에 대해서 해본다

강한결합( Strongly Connected Components) 방향성 있는 순환 노드 = 사이클을 찾을때, 특징 강한결합으로 이루어진 노드중 하나를 하나 제거해도

ex A,B,C 가 강한 결합인데 A 를 제거해도 B 와 C 는 연결 된다

위상 정렬(Topological sort) -AOV Network( 비선형 구조를 선형 구조로 탐색 하는 방법 )=흐름에 따른 여러 공정 모델링을 한사람이 처리 하는 정렬방법

(A처리 된다음 B 가 처리 되고 B 처리 된다음 C,D 가 동시에 처리 될 수 있고 C 다음 F 가 처리 되고 의 흐름을 선형적으로 한사람이 처리 하는 과정으로

정렬 하는 방법)

역위상 정렬(Reverse Topological sort)

위상정렬의 반대로 처리 하는 것 A->B->C, D 의 순이 위상이라면 C,D -> B ->A 순으로 처리 하는 것

위상정렬에서 AOE Network 이 나오는데 AOE Network 으로 간선에 작업을 놓고 간선에 비용을 쓰는 걸 이용해서 작업이 처리되는 소요 비용 , 시간

등을 알 수 있고 , 임계영역(=임계경로Critical Activity) 를 구할 수 있다 = 작업이 모두 끝나는 시간(= 가장 오래 걸리는 경로)

임계영역을 찾음으로써 임계영역의 처리 시간들을 줄이게 되면 공정의 작업 시간을 줄일 수 있다

반응형
반응형

A,B,C,D 작업을 간선으로 하여 공정을 의미하게 하는 것 AOV Network

[AOE Network]

C라는 작업은 A 가 걸처와야 작업이 가능하고

B라는 작업도 A 가 걸처와야 작업이 가능하다

D 라는 작업은 B,C 가 거처 와야지만 가능하다

AOE 처럼 하게 되다 보면 비용이 0(더미 엣지) 인 간선이 생길 수 있다

그런데 c,d 를 제거 하면 되지 안느냐 라는 의문이 생길 수 있는데

제거 하게 되면 b 와 e 의 중간 에 있는 작업들이 구분이 되지 않게 된다 => 어떤 작업이 끝나는지 명확히 구분하기 힘들다

그래서 중간에 비용이 0 인 더미 간선을 둔다 그러면서 c,d 를 두게 된다

그런데 c 는 없고 d 만 존재해도 가능한 형태이다

* b,e 사이에 C 가 있고 d,e 사이에 c 가 있으므로 구문이 가능하다


A ,B 중간에 있는 숫자가 소요 시간

전체 공정이 완료되는 시간은 최대 비용을 찾으면 된다

A->B->C->D->E->I->K->L->M 이 최대 비용 이 작업을 임계 작업이라 한다

이 작업들이 작업들이 실제로 작업 공정에 전체 완료 일자에 큰 영향을 미치므로

=> 이 공정에서 시간을 줄이면 새로운 임계경로가 잡히게 된다

즉 무엇을 줄여야 임계작업을 줄일 수 있는지를 알아 보는것이 AOV NetWork 이다


위의 아래 그래프에서는 위로 가는 쪽이 임계작업(임계경로)이다 (9)

최장시간, 최단시간은 C++ 알고리즘 참고

최장, 최단 시간은 각 노드에서 걸리는 최장, 최단 시간을 말한다

반응형
반응형

Acyclic(에싸이클릭) = 비순환

즉 강한결합요소가 없는 그래프이다

(강한결합요소 = 순환)

왼쪽 그림 순환, 오른쪽 그림 비순환

[공정모델링]

오른쪽 그림에서 A 가 완료 되어야 E,D,C,B 를 할 수 있고

B 와 D 가 완료 되어야 C 를 할 수 있다

F는 D 가 완료 되어야 할 수 있다

왼쪽 그래프는 공정모델링이 안된다 순환됨으로 개념적으로 끝나는 부분이 없다

선행작업 : 먼저 이루어져야 하는 작업

왼쪽 처럼 표를 만들고 나면 오른쪽 처럼 그래프로 만들 수 있다

D,G,L 작업이 끝나야만 모든 작업이 끝날 수 있다

시작은 A 하나

(D,E,F,G) 등이 동시에 공정이 진행 될수 있는 부분

(H,I,J)

위와 같은 그래프를 AOV Network 이라 한다


위상정렬 : 동시에 하지 않고 혼자서 어떤 순서로 공정을 거처야 하는가? 를 결정하는 것

비선형 모양을 순서대로 나열 하는 것

ex)G는 마지막이니 제일 나중에 해도 된다

indegree : 공정의 시작( 내차수 )

outdegree : 공정의 끝나는 지점들 ( 외차수 )

[위상정렬]

하는 법은 A 를 접근한 후 B 의 내차수는 1 이니 A->B 로 연결되는 간선을 없애고 B 의 내차수 는 들어오는 선이 1 이니 이것을 0 으로 만들어서

B 는 이제 위의 공정에서 시작점이 된다 (반복)

C 를 지울때 C 와 연결된 간선을 모두 지운다

그러면 D,E,F,G 들은 내차수가 0 이 됨으로 D,E,F,G 를 큐에 넣는다

D 를 큐에서 빼내고 D를 방문한 다음에 D 를 지우고

E를 큐에서 빼고 방문한다음 E 와 인접한 K 와의 간선을 지운다 하지만 K 의 내차수 0 이 아님으로 아직 큐에 넣지 않는다

그다음 F 가 없어지면 연결된 노드들의 차수는 0 이 되고 이 노드들을 큐에 넣고, 위 과정 반복...

[큐에서 나올때 방문한다]

[내차수가 0 이 되면 큐에 넣는다]

[역위상]

외차수가 0 인점을 선택해서 위상의 반대로 실행해준다

위상정렬을 위해 큐나, 스택을 사용하면 된다

[큐에서 나올때 방문한다]

[외차수가 0 이 되면 큐에 넣는다]

반응형
반응형

 방향그래프 , 깊이우선탐색 Warshall 알고리즘

강한결합요소 찾기 문제

위상정렬/ 역위상정렬

AOE Network

Network 방향그래프 이면서 간선의 가중치가 있는 그래프


방향그래프 : 간선에 방향성이 한방향으로만 연결되어 있는 그래프

(Tip : 무방향그래프의 간선은 양방향 간선이다)

내차수(In-degree) : 정점으로 들어오는 간선수

외차수(Out-degree) 정점에서 나가는 간선수


도달가능성(Reachability)

한 정점에서 다른 모든 정점을 방문할 수 있는 건 아니다(방향성이 있기 때문)

(깊이우선 탐색 : 모든 노드를 탐색 하는 방법)

그래서 깊이우선 탐색으로 시작점을 줄 수 있는 깊이우선 탐색으로 조금 변경한 후

해당 노드에서 인접노드를 스택에 넣고, 스택에 넣었던 노드중 하나를 꺼내어서 꺼낸 노드를 방문하고

이 노드의 인접 노드를 다시 스택에 넣고 또다시 방문하고를 바복하면서

방향성으로 갈 수 있는 노드를 따라 가다보면 시작하려고 했던 노드에서의 방향성이 어디까지 접근 할 수 있는지

도달가능범위를 알 수 있다


Transitive closure( 이행적 폐쇄 )

어떤 정점 A 에서 C 로 가는 방향에 대해서 직접 경로는 없지만, 우회 경로가 있을때 A->C 로 의 간선을 연결한 그래프( 방향으로 갈 수 있을 때 )


Warshall 알고리즘

그리고 A->A 도 가능하기에 배열 테이블의 대각선 값은 1 이 된다

A->B 와 B-C 를 만족하는 경로가 있으면 A->C로 가는 경로도 존재한다

그래서 A->C 로 접근 가능하다를 구현한 것 => 배열 테이블에서 A->C 로 가는 값을 세팅해준다

A->B 로 가는 값이 1로 세팅이 되어 있고 B 에서 C 로 가는 값에도 1 로 세팅 되어 있으면

A에서 C 로 가는 값을 1 로 세팅해준다( 접근 가능경로로 만든다 ) => warshall

그다음 반복...

위에서 A->C 로 가는 값이 1 이므로

C->F 로 가는 값이 1 이고 F->D 로 가는 값 또한 1 이라면 C->D 로 가는 값을 1 로 세팅해준다

[C++ 알고리즘 참고]


[강한결합요소]

: 정점 A 에서 B로 가는 방향성 경로도 존재하고 B 에서 A로가는 방향성경로도 존재

( 사이클로 이루어지고 한쪽 방향으로 도는 경우를 말함 )

- 강한결합요소는 정점 하나를 제거해도 연결은 유지된다

( 강한결합요소의 경우 정점 하나를 제거해도 나머지 노드들끼리는 연결되어 있다는 것 )

중요한 부분에서 는 강현 결합요소로 연결해주면 좋다

VS

이중연결(biconnectivity) : 한쪽 말고도 다른쪽으로도 연결 되어 있는 구조

[강한결합요소 찾기]

왼쪽 트리의 간선에 비용을 매겨서 깊이우선 탐색으로 모든 노드 방향에 대해 탐색 하는 경로를 얻은 후

오른 쪽에는 깊우우선 탐색으로 얻은 것을 먼저 그린후( 빨간선 제외)

모든 노드를 연결하는 경로 외의 선(오른쪽 그림에서 붉은 선) 에 대해서

왼쪽 방향대로 연결해주었을때 오른쪽 그림의 가장 하위 정점에서 자기자신 을 가르키게 되면 그것이 강한결합이 된다

(각 노드에서 빨간색을 타고 올라갔을때 1의 노드(비트리간선으로 자기자신)가 다시 나오면 강한결합이 된다)

오른쪽 그림에는 두가지의 강한결합을 보여주고 있다

빨간색선 : 난트리엣지( = 방문하지 안은 엣지)

파랑색 : 트리엣지 ( = 방문한 엣지)

1. A->D->F->E ->A , A 로 시작해서 가장 하위로 갔을때 그것이 자기자신을 가르키는 경우를 강한 요소라 한다

2. G->J->I ->G

반응형
반응형


가중그래프에 최소비용신장트리, 최단경로 찾기 등이 있다

최소비용신장트리(MCST) 에서의 우선순위 탐색은 비용 자체이지만

최단경로찾기의 우선순위탐색은 누적된 간선 비용값이 우선순위가 된다

반응형
반응형

[point]

해당 노드에서 직접 바라보는 부모노드와의 거리보다 다른 연결로 들어온 경로의 거리가 더 적다면

적은 거리로 온 노드를 부모로 바라본다


시작 A

모든 노드는 A 를 가르키고 (parent)

직접 가르키지 못하는 노드들은 무한대로 거리를 설정한다

1.A 를 처음 방문하고 방문하지 않은 최소 비용으로 연결된 노드에 대해서 탐색을 시작한다

2. 그래서 처음 C 를 방문하게 된다

(노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 )

3. C 를 살펴보면 C 는 D 와 연결 되어 있고 D 는 A 를 가르키고 있다

그런데 A에서 C 그리고 C 에서 D 로 가는 비용이 3 이고 A 에서 D 로 가는 비용이 2 총 3 이기 때문에

D 가 더 빨라 D 가 가르키는 부모와 distance를 바꾸지 않아도 된다

[반복..] 인접한 것과 방문은 다른 것

4. 노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 (D)

5. D 와 인접한 G 와 F 노드가 있는데

먼저 F 를 보면 F의 비용은 무한대 이기 때문에 D 에서 F 로 누적된 6 만큼 이동 하는 것이 더 빠르기 때문에

(F A 무한대) 를 (F D 6) 으로 바꿔준다

G 도 무한대 비용인데, D 에서 G 로 가는 누적된 6 이 더 작음으로

(G A 6) 을 ( G D 6 ) 으로 바꿔준다 (이렇게 parent 를 세팅해나간다)

6. 다시 노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 이번에는 (E) 가 선택 된다

반복...

결과

최종적으로 Vertex 가 바라보는 Parent 로 연결되는 선을 연결해주면 위 그림처럼 나오고

최단 경로는 시작점 A 에서부터 모든 점에 대한 최단 거리를 연결해 놓은 형태가 됨으로

A 가 아닌 어떤 노드에서 부모를 따라 가면 어떤노드에서 A 까지 가는 최단 경로가 나온다

반응형
반응형

MCST [Minimum Cost Spanning Tree]

신장트리(Spanning Tree) : 모든 정점(노드)을 방문하는 트리

트리 : 사이클이 없는 그래프를 말한다

그런데 간선에 비용이 있다 => 모든 정점을 방문하면서도 간선의 비용의 합이 최소인 트리를 신장트리라 한다

MCST = Minimum cost spanning tree

최소비용 신장트리로 알려진 알고리즘 들에는

1. 우선순위 탐색

2. Kruskal

3. Sollin

4. Prim

etc...

[1,2 가 성능이 좋다]


크루스칼 알고리즘 - 최소비용 신장트리( 사이클 없이 모든 노드를 연결하기 )

모든 노드를 사이클 없이 가장 적은 비용의 가선으로 연결 하는 알고리즘

[집합 Union-Find 알고리즘이 도입됨]

노드를 집합으로 보고 집합의 포함이 되어 있는지로 판별하면서 간선을 연결 한다

*모든 노드와 간선은 연결되어 있는 상황이고

*간선에는 비용이 있다

간선의 비용이 가장 적은 간선에 연결된 두개의 노드를 각각의 집합으로 만든다

그다음 순서의 간선을 선택 한다음 두개의 노드 모두가 기존 집합(각 한그룹에 두개가 모두)에 포함되어 있는 상태라면

경로가 사이클이 생김으로 간선을 연결하지 않는다, 기존 집합에 포함 하지도 않음(이미 조재 함으로)

자세한 내용은 C++ 알고리즘 참고

반응형
반응형

Find - 어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별

Union - 서로 다른 두개의 집합을 하나의 집합으로 합병

=> 상향식 트리구조로 구현 하는 것이 효율적이다

상향식트리구조 : 위에서 아래로 내려오는 구조가 아닌 아래에서 위로 올라가는 구조

일반적으로 알고 있는 하향식 트리구조는 부모가 자식들만큼의 포인터 개수를 가지고 있어야 하지만

상향식은 자식이 부모를 가르키는 구조이므로 각 노드는 하나의 포인터만 가지고 있으면 된다

그러므로 어느 집합에 포함된 노드의 parent 를 계속 따라가다보면 최종 root 인 어느 집합인지를 알 수 있게 된다

(각 root 집합 명)

반응형
반응형

MCST [Minimum Cost Spanning Tree]

신장트리(Spanning Tree) : 모든 정점(노드)을 방문하는 트리


트리 : 사이클이 없는 그래프를 말한다

그런데 간선에 비용이 있다 => 모든 정점을 방문하면서도 간선의 비용의 합이 최소인 트리를 신장트리라 한다

MCST = Minimum cost spanning tree


최소비용 신장트리로 알려진 알고리즘 들에는

1. 우선순위 탐색

2. Kruskal

3. Sollin

4. Prim

etc...

[1,2 가 성능이 좋다]


최소비용신장트리 - 우순순위 검색 에 의한 방법

( PrioityQueue 가 필요 ( PrioityQueue 는 힙으로 만든 것이 적절하다 Heap 은 O(logN)의 성능을 갖는다) )

* 비용을 우선순위로 둔다

모든 노드를 연결하는데 가장 최소의 비용으로 모든 노드를 연결하는 방법

간선 자체를 우선순위로 보고 비교한다

[C++ 알고리즘 참고]


[최단경로찾기 ]

A 부터 Z 까지 가는 길 중에 각 길마다 비용이 있고 가장 적은 비용으로 Z 까지 가는 비용을 얻기 위한 방법

* 누적으로 최단 경로를 구한다

먼저

출발점이 A 라면 A 와 인접한 것들을 우선순위 큐에 넣고 ( 이때 우선순위 큐에는 가작 작은 값이 최 상단에 위치하게 한다)

p 큐 가장 위에 있는 것을 뽑아와서 선을 연결 한다

뽑아온 노드의 인접 노드를 다시 p큐에 넣는다

이때!! 큐에 넣기전 현재 도착 노드가 p큐에 있는지 보고 p큐에 도착 노드가 있다면 이제까지 누적해온 경로의 길이를

비교해봐서 p큐보다 값이 작다면 기존 p큐에 있는 노드를 지우고 누적값이 적은 노드값으로 대체한다

- 최소 비용으로 모든 정점을 연결하는 방법

반응형
반응형

insert : 삽입을 하는 동작에서만의 시간

remove : 삭제를 하는 동작에서만의 시간

O(1) = 상수시간

[ArraySequenceMap] = 배열 => 검색이 O(N) 이 걸리는 이유는 첫번째 부터 찾을때까지 각 배열에 대해 맞는 것을 찾으려니 선형적으로 걸린다

[ListSequenceMap] = 리스트

BinMap(Binary) =이분검색

=> 트리를 이용하지 않는다!!!

=> 자료집합은 정렬 되어 있어야 한다, 정렬이 되어 있는 상태에서만 작동 가능

=> 삽입될때 만약 배열에 자료들에 배열에 들어가 있는 상태라면 정렬된 상태를 유지하기 위해서 들어갈 이후의 값들이 모두 뒤로 이동 되어야 한다

itpMap(interpolation) = 비례식에 의한 찾기 방식으로 검색은 자료가 선형적으로 있을때 빠른 속도를 보인다 , 수치자료에서만 사용 가능

하지만 O(loglogN) 삽입삭제는 역시 느리다

BinTreeMap(바이너리트리맵)

=> 이진 트리를 이용한 검색방법이다

=> 균형이 맞으면 O(logN) 의 성능을 보이지만 삽입시 균형이 맞지 않으면 한쪽으로 치우치는 최악인 경우 O(N) 의 성능을 보인다

=> chain 은 중복처리를 리스트에서 하기 때문에 저장공간이 자료수보다 큰 필요는 없다

[HashMap,ChainMap 은 상수 시간에 찾기 삽입, 지우기가 끝난다]

=> 관건은 해쉬 펑션을 어떻게 정의 하느냐 이고, 보통 Hash 는 입력 자료수의 2배 만큼의 공간으로 잡을때 성능이 좋다

HashMap(정적인 상황에 적합)

ChainMap (연결 법) => 해쉬 테이블에 이중리스트로 연결하여 데이터를 추가( 동적인 상황에 적합) , 최신 데이터를 리스트의 앞에 넣어줌으로서

노드의 뒤쪽으로 이동하는 시간을 줄일 수 있다

(=>chainmap 은 중복된 값을 리스트에 넣는 것이므로 값을 최근 헤드에 연결된 것을 리턴해 주면 됨으로 검색도 상수시간이다)

[radix tree,radix trie 둘다 자료가 비트로 표현될 수 있어야 한다]

이진트리에서의 한쪽으로 치우치는 현상을 방지된 구조가 된다 => 비트에 의해 좌,우가 결정 됨으로

그래서 검색,삽입,삭제 가 O(logN) 의 성능을 보인다

Radix Tree => 모든 노드가 정보노드

Radix Trie => 정보노드는 leaf 에, 내부(중간)노드는 분기노드

[B-Tree : 하나의 노드에 여러개의 자료가 들어 갈 수 있으면서 균형을 맞추는 구조]

O(logN) 의 성능을 보인다

[RB-Tree : 벨런슬르 자동으로 맞춰주면서 이진트리 구조의 형태를 지닌다]

find 도 O(logN) 이며 insert ,remove 도 O(logN) 이지만 실제 다른 logN 의 성능을 가진 것보다 상당히 빠른 속도를 보인다

검색 : 이진트리 검색과 동일

삽입 : 칼라상향변환 + 회전

삭제 : 칼라하향변환 + 회전

으로 이루어진다

[모든 벨런스 트리는 기본적으로 중복이 불가능하다]

chain, 이나 hash 가 가장 빠르다

반응형
반응형

Red Black Tree 의 특징 : 2-3-4 트리를 Binary Tree 로 표현 한것

(2-3-4 트리는 3차 B-Tree 와 돌아가는 것이 동일하다)

먼저 2-3-4 트리를 알아야 하는데

노드의 자식이 2,3,4 개가 존재 할 수 있다고 하여 2-3-4 트리이다

A 를 가지고 있는 노드는 2개의 자식을 갖는다

A B 를 가지고 있는 노드는 3개의 자식을 갖는다

A B C 를 가지고 있는 노드는 4개의 자식을 갖는다

Red Black 트리는?

2-3-4 트리를 이진트리로 나타낸 것

그림에서 2노드 인 경우 A 를 검정색 A 노드로 표현

3노드 인 경우 B 를 빨강으로 내리거나 A 를 빨강으로 내려 표현

4노드의 경우 B 를 제외한 양쪽을 빨강으로 내려 표현

Red-Black 트리에서는 이렇게 자식으로 내리지만 2-3-4 트리에서는 하나의 노드로써 결합의 의미를 갖는다

2-3-4 트리를 보면 B-Tree 의 형태 임을 알 수 있다( 동작도 동일하다 )

즉 B-Tree 를 이진 트리 형태로 바꾼것!!!


이진트리와 동일하게 부모노드의 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다

Root 에서 Leaf 로 가는 경로의 검정노드의 수는 모두 같다 => B-Tree 에서 빨강이 자식으로 확장된 형태이므로

원래 B 트리는 모든 자식의 레벨이 같다, 그래서 확장된 빨강 노드를 제외하면 루트에서 자식까지 가는 검정노드의 수는 갖게 된다


색변환 (color flip)

상향 색변환 : 빨강을 위로 올림 => 검정색의 자식의 두개의 빨강 노드일경우 부모를 빨강으로 바꾸고 두 자식을 검정색으로 바꾸는 것

하향 색변환 : 위에 있는 빨강을 자식을 빨강으로 바꾸는 것 -> 부모는 검정이 된다 (상향 색변환과 반대)

회전 : 이진트리의 규칙을 깨지 않고 트리를 재구성 하는 방법(우회전, 좌회전) => 좌우의 트리 높이를 맞추는 방향으로 회전함=>AVL Tree 의 기본 동작

이렇게 분할 하는 이유는 자료를 삽입하기 위함 ( 트리의 균형을 깨지 않고 )

(노드안에 자료가 3개면 => 4노드)

위 그림이 상향식 변환 ( 위의 그림에서 녹색 부분이 B-Tree 의 설명 아래 있는 것이 RB-Tree )

루트는 원래 검정이라 빨간색으로 자식을 내리건 안내리건 간에 Root 는 검정색이된다

루트가 검정색


pivot 은 회전의 축이 된다

회전하면서 자식들의 위치는 이진트리의 부모의 왼쪽은 작고 오른쪽은 큰 순서를 유지하기 위한 순서대로 구성해준다


- 트리에서는 노트의 끝을 노드로 표현하지 않고 0 로 표현 할 수 있다

- RedBlack 을 표현하기 우해 bool red; 로 표현 한다

- RB 트리도 기본적으로 중복을 허용하지 않는다( list 등으로 노드에서 중복을 허용하는 구조로 만들 순 있다)

[RB-Tree 검색]

검색 알고리즘은 이진 트리와 동일하다( 키 값으로 비교하여 왼쪽, 또는 오른쪽으로 이동 )


[RB-Tree 삽입]

single rotation, double rotation 으로 이루어진다

구조는 이진트리와 동일하기 대문에 노드 순서 규칙은 동일

균형을 맞추기 위해 색변환 -> 노드 분할, 결합등을 하게 된다

=> 이때 빨간노드가 연속되는 상황이 벌어질 수 있는데 이때의 균형을 맞추기 위해 Rotation 을 한다

=> 자료를 삽입할때 부모가 빨간노드이면 Rotation 을 한번 한 후 삽입 한다

right rotation, left rotation => single rotation

right rotation 한다음 left rotation , left rotation 한다음 right rotation => double rotation

[Single rotation]

1. 상향색 조정을 했을때 빨간 노드가 연달아 나타나게 되는 상황이 발생되면

2. 회전을 하면서 노드의 색깔이 변경되고, 그럼으로서 노드의 균형을 맞춘다

회전시키기 위해선 t, p, gp(부모의 선조), ggp 의 4개가 있어야 한다

그림상 B-Tree 부분 에서(각 이미지의 아래에 그려진 트리) 노드안의 자료가 3개일때 분할하는 모습을 볼 수 있다(이것이 rotation 의 회전과 동일)


[double rotation]

left-right rotation 그림중에서 1번 을 보면 single rotation 에서와는 달리 두개 연달아 나오는 레드 노드 위로의 선이 반대인 것을 볼 수 있는데

이때는 두번 회전으로 노드를 정리해줘야 한다 => double rotation

1.상향 색조정을 아래에서 한번 하게 되면 레드 노드가 연달아 나오게 된다

2.Right-left rotation 에서 보면 C 를 pivot(중심)으로 해서 한번 회전 하면 선이 펴지게 된다 => 색변환 일어나지 않는다

3. 그다음 C 가 회전 되어진다 => single rotation 처럼 회전 => 색변환이 일어난다


[키값에 의한 회전]

왼쪽 상단 그림을 보면 G 를 키 값으로 주고 E 에서 G 쪽으로 향하는 방향으로 회전을 시켜주고

3번째 그림에서는 E 값을 키 값으로 놓고 E 에서 C 의 방향으로 회전을 하게 된다

pivot, child, gchild 는 아직 정해지지 않은 각 노드 포인터

*회전 호출시 pivot 을 정하고 넘겨준다

gchild 를 키값으로 하여 gchild 에서 child 의 방향으로 회전

회전의 방향 = 키값(노드안의 데이터)

회전의 위치 = pivot( pivot 의 왼쪽 또는 오른쪽 노드에 의해서 child 가 결정된다 )

child 와 키 값에 의해서 gchild 가 결정되면서 회전하게 된다

pivot 과 키값(gchild)의 비교에 의해서 child 가 가르킬 노드를 정해준다

child 와 gchild 의 위치관계를 pivot 과 키값에 의해 따져서 회전시켜준다

if (key > child->data || key == child->data)

Rotate left

else

rotate right

// key == child->data 일때도 오른쪽인 이유는 나중에 내부노드 삭제를 할때 루트보다 바로 큰 노드와 바꿔치기 하여 루트를 삭제 하기 위한

처리와 맞춰주기 위함 즉 삭제시 루트에서 오른쪽으로 한번간 후 왼쪽으로 계속가서 루트보다 바로 큰 노드를 찾기 위한 오른쪽 탐색을

하는 처리와 맞춰주기 위함이다

끝난 후 변견된 트리의 pivot 의 자식을 설정해 주어야 하는데

gchild 가 상단으로 올라감으로 gchild 를 pivot 의 자식으로 주어야 한다

그런데 왼쪽으로 줄것인지 오른쪽으로 줄것인지를 결정하기 위하여

key 와 pivot->data 의 비교로 위치를 결정한다


[insert ]

삽입시 자식노드 둘다 레드이면 칼라상향조정

칼라 조정후 부모가 레드면 회전

회전하려고 할때 노드 연결이 단방향이 아니고 꺽여 있으다면 double rotation

t,p,gp,ggp 의 관계를 살펴본다

if( p->red ){

if( value > gp-data != value > p->data )

rotation(value, gp);

t= rotation(value,ggp);

t->Red=true;

}

마지막 하단에 노드를 삽입할때도 그때의 부모가 레드면 로테이션( or double rotation) 후 삽입

회전이 다 된후 노드가 맞는 위치에 삽입된다

그래서 좌우 트리가 두배 이하로 유지가 된다


[delete]

C++ 알고리즘 참고

delete 에서 color demotion 이 나온다, 왜냐하면 삭제시 노드가 아에 없어지면 자식을 갖지 못하는 상화이 벌어 질 수 있으므로

쉽게 위해 하기 위해서는 B-Tree 로 전 후를 만들어 본 다음 만든 트리를 Red-Black 트리로 변행해 본다음

바뀐것들으 알아보는 것


[Red-Black 트리 분석]

트리의 높이

black height => black 노드로 이루어진 레벨의 개수

둘다 black 노드의 높이는 2 이다 , black height

black height 는 2 인데 개수는 왼쪽이 3개, 오른쪽이 15개

N+1 = 노드개수(3)+1 은

s^B <= N+1 <= 4^B (B = black height)

왼쪽은 H(Height) = B(Black Height) = 2

오른쪽은 H(Height) = 2B(Black height) = 4

O(logN) 의 성능을 보인다 => 성능이 좋다

반응형
반응형

시스템들이 내부적으로 사용하는 검색 구조( 데이타베이스, 오라클 등등 => 인덱스 검색 구조이다)

외부검색에 적절한 형태 => 하드디스크 Tap 등 외부 장치의 검색에 잘 사용됨

내부검색 => 램 같은 내부적인 부분

이진트리 문제점 : 좌우 균형이 맞지 않으면 비효율적이다

트리의 성능은 트리의 높이에 있다

그래서 트리의 높이를 낮춰주면 성능이 올라갈 수 있다

그래서 트리의 좌우 균형을 맞춰 주는 것이 중요하다

균형트리 : 삽입 삭제시 필요하면 스스로 균형을 유지하는 트리

AVL, 2-3(-4), Red-Black Tree-BTree....

-삽입은 split (분할) 동작 으로 삽입


Balanced Tree : 스스로 균형을 유지하는 트리

A 를 찾기 위해서 균형이 안맞으면 느릴 수 있다

균형이 안맞으면 링크드 리스트처럼 검색성능을 보인다

위 그림은 트리를 회전함으로써 이진트리의 규칙을 유지하면서 트리의 높이를 낮추는 방법을 보여준다

RB Tree & B Tree 의 방법에 AVL Tree 가 포함된다


하나의 노드에 여러개의 노드가 들어올 수 있다

M 차 => 한 노드에 자료가 가장 많이 들어간 수의 차수를 말한다

이 그림에서 M = 5차 > v,w,x,y,z

B - Tree 규칙.1

1. 노드의 자료수가 N 이라면 , 그 노드의 자식의 수는 N+1 이어야 한다 => left, right 가 있어야 하므로

자료수 = (노드 안에 있는 자료의 개수)

2. 각 노드의 자료는 정렬된 상태여야 한다 --> 방향으로

3. 노드의 자료 D_k 의 왼쪽 서브트리는 D_k 보다 작은 값들이고

D_k 의 오른쪽 서브트리는 D_k 보다 큰 값들이어야한다

( 이진트리에서 부모보다 왼쪽은 작은 트리, 오른쪽은 부모보다 큰 트리를 말한다 )

ex) 그림에서 C의 왼쪽은 C 보다 작은 A,B 이고, D,E 는 C 보다는 큰지만 F 보다는 작은 자료이다

B - Tree 규칙.2

1. Root 노도는 적어도 2개 이상의 자식을 가져야 한다.

2. Root 노드를 제외한 모든 노드는 적어도 floor(M/2) [<= 내림] 개의 자료를 가지고 있어야 한다.

( 위 그림에서는 노드들이 모두 적어도 2개 이상의 자료를 가지고 있다

3. 외부 노드(leaf node) 로 가는 경로의 길이는 모두 같다

4. 입력자료는 중복될 수 없다.( list 등을 같이 쓰면 중복을 허용 할 수도 있다 )


B-Tree 구조

시작을 나타내는 노드가 있는데 헤드에 대한 포인트 노드만 사용하고 끝은 0 로 처리 해서 만든다

끝을 NULL 로 처리 하는 것이 가능

[노드 안의 글자가 '키' 를 의미한다]

B-Tree 검색

루트에서부터 노드의 자료들과 찾을 값을 비교하여 노드가 찾을 것보다 작으면 왼쪽 크면 오른쪽으로 이동하면서 찾아간다

-노드내에서는 순차검색, 전체적으로는 트리검색


B-Tree 삽입

1.자료는 항상 leaf 노드에 추가된다 (leaf 노드의 선택은 삽입될 키의 하향 탐색에 의해 결정)

2. 추가될 leaf 노드에 여유가 있다면 그냥 삽입

3. 추가될 leaf 노드에 여유가 없다면 '분할' 하기

4. 삽입할 때 같은 키 값이 있으면 안됨으로 해당 노드에 삽입하기 전에 같은 값이 있는지 find 해봐야 한다

[루트노드 분할]

위 그림은 왼쪽은 Root(뿌리) 노드일경우에 가능한 경우이다

H 를 넣으려고 할때 노드를 3개로 분할 한 후 H 를 넣는 모습

Root 노드이기 때문에 floor(M/2) 와 관계 없이 G 가 하나로 존재 가능하다 G 가 루트가 되는 것

[일반노드 분할]

위 그림의 오른쪽이 일반노드에 대한 분할인데

만약 A B C D E 노드를 C 를 중심으로 분할 한다면 C 를 부모노드로 올려주고 C 를 기준으로

A B 를 왼쪽 D E 를 C 의 오른쪽 노드로 배치시켜서 분할 한다

(M 이 홀수 인 경우로 가정 =>

현재 차수 M = 5 로 가정 하였으므로 5/2=2 2개씩 나누어야 반씩 나눠 짐으로 왼쪽 두개,

오른쪽 두개 로 나눈다 3번째가 부모로 올라가는 형태 )

이때 부모로 올려야 하는 문제가 있는데 그것은 부모가 꽉찬 노드 일경우에 발생한다

이때는 부모를 분할 한 후 그다음 원래 분할 하려고 했던 노드를 분할 한다

분할 => split

* 삽입할때 현재 중간 노드들이 풀이면 M(차수) 만큼 풀이면 분할을 하고 그 위치에서 다시 삽입할 위치를 찾아간다 => 미리 분할 해 준다

- 마지막 leaf 노드까지 가서 마지막 leaf 노드가 풀이면 분할 후 삽입한다


[ 외부노드(leaf node) B-Tree 삭제]

삭제하고자 하는 자료가 있는 노드에 자료를 삭제 후 자료수가 M/2 이상이 되도록 보장해야 함

루트를 제외한 모든 노드는 M/2 보다 자료수가 많아야 한다, 이것이 보장 되어야 B-Tree 이다

이것의 해결 방법이 형제에게서 빌리기 VS 형제와 결합하기 이다

1. 빌리기 : 형제가 M/2 보다 맣은 자료를 가지고 있다면 빌려온다

2. 결합하기 : 형제에게서 빌릴 수 없다면=>M/2 보다 작다면 합친다

[형제에게서 빌리기] - Borrow key => 회전

왼쪽 그림은 B 를 삭제 하려고 하는데 A 하나 밖에 자료가 안남게 된다

그래서 D 를 빌려 올려고 하지만 D 를 A 노드 쪽으로 가져오면 부모인 C 와 순서(왼쪽이 작은쪽) 이 맞지 안으므로

D(형제) 를 부모 에게 주고 C 를 A 노드 쪽으로 주게 되면 => [자료를 돌리는 식]

B 를 삭제 할 수 있게 된다( 오타 : 그림상에서 D K 는 D G K 이다 )

이렇게 B Tree 의 규칙을 어기지 않고도 Balance 조정이 가능하다

[형제와 결합하기] - BindNode => 중간이 되는 부모 자료와 같이 결합하기

오른쪽 그림은 결합하기인데

B 를 삭제하기위해서 보면 A 가 있는 노드의 자료가 하나만 남기 때문에 그냥 지워선 안되고

D를 빌려오자니 D 와 함께 있는 E 가 하나만 남게 되어 빌려오는 상황도 여의치 안다

그래서 이때는 결합하기로 가야한다

먼저 A B 와 D E 중간에 위치한 부모의 C 를 아래로 내려서 그림과 같이 A B C D E 로 합친다 그 후 B 를 제거


[ 내부노드(leaf node가 아닌 ) B-Tree 삭제]

1.

i 를 삭제 하려고 할때 I 를 제거 하면 i 를 삭제하고 재 구성할 수 없으므로 대채하는 것으로 가야한다 => 키 순서상 재구성이 힘들다

이진트리와 동일하게 i 보다 바로 작은값 또는 i 보다 바로 큰 값으로 대채한 후 대채한 값을 삭제 하면 된다

Right Subtree 중 가장 작은 값인 J 로 i 대신 대채한 후 j 를 다시 삭제 하러 가면 된다

이때 j 를 삭제하기 위해 내려갈때 삭제시 M/2 이하인 노드는 형제에게서 빌리든지, 결합을 해야 한다

=> 삭제를 할때 부족한 노드가 있으면 안됨으로 balance 를 유지하기 위해

2. bindNode 를 할때 오른쪽 노드를 왼쪽으로 결합 하면 오른쪽 노드는 없어지게 되고 부모노드에 있는 자료중 하나가 아래려 내려 오게

되는데 이때 부모가 root 이고 부모의 자료 개수가 0 개가 된다면 합쳐진 왼쪽 노드를 부모노드로 해주면 된다

3. swap 루트에서 오른쪽으로 한번 이둥후 왼쪽으로 계속이동하면 I 보다 바로 큰 값을 찾을 수 있다

그 후 대채할 키를 다시 루트에서부터 삭제하는과정을 거치면 된다


이진트리의 경우 레벨(높이) 는 (log_2 N)+1 이하 이다 이때 밑이 2 인 것은 이진트리에서 자식은 2개씩 나갈수 있기 때문

B-Tree 의 경우 자식은 최소 M/2 개 이상이어야 함으로 밑이 M/2 이다

삽입/삭제/검색 성능 complexity 를 말할때는 굳이 밑을 쓰진 않는다 O(logN) 으로 성능이 좋다

-이진트리의 경우 평균 시간 복잡도가 nlogn 이며 최악의 경우 n 의 시간 복잡도를 갖는다

이를 보안할 것이 AVL-Tree, Red-Black Tree , B-Tree , Splay Tree 등이 있다

-최악의 경우가 없다

-차수가 높을 경우 노드내에서 순차검색대신 이분검색을 사용 하는 것도 속도를 높일 수 있는 방법이다

-모든 leaf 가 같은 레벨에 위치한다


tip : AVL Tree = leaf node 의 차이를 2 이하로 구성하는 트리 삽입시 이를 위반하면 자동 재구성한다

splay tree = 가장 최근에 사용된(삽입 삭제 검색) 노드를 루트로 항상 유지하는 트리이다

스케줄 알고리즘 등에서 LRU(Least Recently Used => 페이지교체 알고리즘) 같은 알고리즘을 구현하는데 적합

반응형
반응형

이진트리 형태로 구성

왼쪽노드는 키가 0 오른쪽 노드는 키가 1

서브트리는 루트의 왼쪽 하위는 0 오른쪽은 1 => 이진검색트리 특성과 유사하다

-각 트리의 레벨의 수치에 대한 비트수치를 적용

-왼쪽부터 오른쪽으로 비트가 증가하는 형태

Degenerated case = 한쪽으로 트리가 쏠리는 현상

같은 키를 넣으면 허용 않함

검색할때 최 하위 비트부터 동일한 비트인쪽으로찾아 검색해간다

즉 비트가 검색키이다

노드 삭제는 이진검색트리와 동일하게 삭제

삽입은 레벨에 따른 비트 검사를 통해 leaf 로 이동하여 leaf 에 추가한다

하위비트부터 살펴봐서 비트가 0이면 왼쪽으로 그다음 비트가 또 0 이면 다시 왼쪽으로 그다음 비트가 1 이면 오른쪽으로 이동


분기노드 = 네모 점 데이터는 없다

비트에 따라서 좌우를 판단하는 것은 동일하다

그래서 자료의 입력 순서와는 무관하다

키의중복은 허용되지 않는다( 중복을 허용하려면 링크드리스트를 이용 )

트리의 높이는 log_2(8) + 1 = 4, [8 leaf 노드 수]

자료는 2^M 개 입력될 수 있다, [m 은 키의 비트 개수 = 3]

trie : 키 비교를 한번만 한다 => 키비교가 복잡할때 사용되면 유용


삽입은 이전 값과 차이나는 비트까지만 분기를 하면서 노드를 하단에 위치하게 한다

차이가 나는 비트의 노드가 들어올때 분기 노드를 만들면서 노드는 가장 하위에 유지되도록 한다

C++ 알고리즘 참고


트리의 높이만큼 비교, 검색 하기 때문에 O(logN) 의 성능을 가진다

성능이 좋다

Radix Tree => 모든 노드가 정보노드

Radix Trie => 정보노드는 leaf 에, 내부(중간)노드는 분기노드

반응형
반응형




key 를 통해서 원하는 레코드를 가져온다

알고리즘 성능은 삽입,검색,삭제를 다 따져야 판단할 수 있다

array 는 무순서로 처음부터 끝까지 비교해가면서 찾아내는 방법

bin 은 자료가 들어올때 재 정렬 한다 => 재 정렬할때 삽입삭제는 느리지만 검색은 그만큼 빠르다

검색 알고리즘은 검색이 관건

- 이분검색의 경우 삽입할때 정렬해야 하기때문에 O(N) 삭제는 자식을 땡겨와야 하기 때문에 O(N)

검색은 좋은 성능인 lonN 을 보인다

내분검색의 검색은 loglogN 으로 성능이 좀 더 좋지만 실제 어느것이 빠를지는 해봐야 안다

결론적으로 순차검색 array, list 는 O(N) 으로 시간이 오래 걸린다 => 적은 자료집합에서는 사용할만지만

많아질경우 이분,내분으로 접근한다

반응형
반응형

Space Complexity = 필요한 메모리

stability = 정렬되기 이전의 동일한 데이터끼리의 순서를 정렬 후에도 유지하고 있는가?


선택정렬 : 최소값을 찾아서 제일 앞으로

삽입정렬 : 앞쪽에 데이터를 넣으면서 정렬을 시킨다 그래서 정렬된 =>이미 정렬된 부분에 이 값이 어디에 들어갈 것인가

버블정렬 : 인접한 값을 비교 교환

쉘 : 자료가 역순으로 정렬되어있어 속도가 많이 떨어지는 삽입정렬의 단점을 보완한 정렬 기법

추가 메모리 공간 소요가 없으면서도 정렬중에서도 속도가 빠르다

퀵소트 : 의 평균성능은 NlogN 이지만 최악의 경우 N^2 로 간다 => 추가 메모리를 비교적 필요로 하는 상황이 벌어진다

힙소트 : 최대값이 루트에 있다 , 추가 메모리를 필요하지 않는다 , => 힙소트 자체로 정렬 할 경우 NlogN 중에서는 비교적 조금 느린 성능을 보인다

특성을 잘 활용하는 것이 중요

병합정렬 : 순차적인 접근방식이라 순차적 접근방식에서 사용될만 한 방식=> stability 가 유지 되면서 추가 메모리가 필요 없다

Radix(기수) 들과 Distrubtion(분포수세기) 은 양의정수만을 또는 이진수를 정렬 할 수 있는 정렬 => 속도가 빠르다

반응형
반응형

http://blog.naver.com/kareons777/70075825158


// 렌더링 프레임수 계산
static DWORD FPS_Frames=0;
static float FPS_Num, FPS_LastTime=0;

if(FPS_Frames == 0) FPS_LastTime = (float)timeGetTime()/1000.0f;

float FPS_Time = (float)timeGetTime()/1000.0f;

if(FPS_Time - FPS_LastTime < 1.0f)
{ 
FPS_Frames++;
}
else
{
FPS_Num = FPS_Frames/((FPS_Time-FPS_LastTime));
FPS_Frames = 0;
FPS_LastTime = FPS_Time;
//FPS_Num 출력
}
timeGetTime()함수는 winmm.lib를 링크해야 합니다. 또한 #include <mmsystem.h> 해줘야 하고요.
이걸 함수로 뽑던지 그냥 랜더 함수에 넣어 주던지 하면 됩니다.

[출처] fps 계산법|작성자 쑤기


반응형
반응형

http://blog.naver.com/pluulove84/100058770623



다차원검색트리

 

KD-트리

- 이진검색트리를 확장한 것으로 k개(k≥2)의 필드로 이루어지는 키를 사용

- 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다

 

 

KD-트리 삽입

 

 

A(50, 50) → B(10, 70) → C(80, 85) → D(25, 20) → E(40, 85) → F(70, 85) → G(10, 60)

 

1. A(50, 50)이 루트 자리를 차지

2. B(10, 70)는 x값 10이 루트의 x값 50보다 작으므로 왼쪽 자식이 된다

3. C(80, 85)는 x값 80이 루트의 x값 50보다 크므로 오른쪽 자식이 된다

4. D(25, 20)는 먼저 x값 25가 루트의 x값 50보다 작으므로 루트의 왼쪽으로 가서 B(10, 70)를 만난다

    y값 20이 B의 y값 70보다 작으므로 B의 왼쪽 자식이 된다

5. E(40, 85)는 x값 40의 루트의 x값 50보다 작고, y보다 85가 B의 y값 70보다 크므로 B의 오른쪽 자식이 된다

6. F(70, 85)는 x값 70이 루트의 x값 50보다 크고, y값 85가 C의 y값 85와 같으므로 B의 오른쪽 자식이 되었다.

7. G(10, 60)는 x값 10이 루트의 x값 50보다 작고, y값 60이 B의 y값 70보다 작고,

    x값 10이 D의 x값 25보다 작으므로 D의 왼쪽 자식이 된다.

 

 

KD-트리 삭제

 

 

KD-트리 삭제

1. 자식이 없는 경우

 : 노드만 제거

2. 자식이 하나뿐인 경우

 : 자식이 둘인 경우와 같이 해결

 : 왼쪽 자식만 있는경우, 왼쪽 서브트리 중 노드 r에서의 분기에 사용한 필드 값이 가장 큰 노드를 찾아서 이동

3. 자식이 둘인 경우

 : 오른족 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드를 찾아서 이동

 

 

KDB-트리

 

 

KDB-트리의 노드의 종류

1. 영역 노드 : 복수 개의(영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드이다.

2. 키 노드 : 복수개의(키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드이다.

 

각 차원에서 범위가 주어지고 영역은 이들을 모두 만족하는 공간을 말한다.

 

KDB-트리의 키 검색

 : 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려가면 된다.

 

KDB-트리의 키 삽입

1. 삽입할 키가 속하는 리프 노드를 찾는다.

2. 해당 리프 노드가 키를 더 수용할 수 있는 공간이 있으면 (키, 페이지 번호) 쌍을 삽입하고 끝난다

3. 리프 노드가 키를 더이상 수용할 수 없을 경우, 형제 노드와 재분배할 수 있으면 재분배하고 작업은 끝난다.

4. 재분배가 불가능하면 리프 노드를 분할하여 두개로 만든다.

   → 이에 따라 부모 노드에 있던 한 영역이 두개로 나누어지므로(영역, 페이지 번호) 쌍이 하나 늘어난다.

   → 부모 노드가(영역, 페이지 번호)를 하나 더 수용할 공간이 있으면 작업은 끝이다.

   → 만일 부모 노드가 이것을 수용할 수 없으면 부모 노드를 분할 한다.

반응형
반응형

http://yeols.com/80075364360



기수 정렬(Radix Sort)

 

  • 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나.

  • 특수 정렬 알고리즘
    • 비교 정렬
      • 두 원소를 비교하는 정렬의 하한선은 Ω(nlogn)

        최악의 경우 정렬 시간이 θ(nlogn)보다 더 빠를 수는 없는가? "

    • 그러나 원소들이 특수한 성질을 만족하면 O(n)정렬도 가능하다.
      • 기수 정렬
        - 원소들이 모두 k 이하의 자리 수를 가졌을 때 (k: 상수)

  • 기수 정렬의 개념
    • 입력이 모두 K 이하의 자리 수를 가진 특수한 경우에(자연수가 아닌 제한된 종류를 가진 알파벳 등도 해당) 사용할 수 있는 방법


    • θ(n)시간이 소요되는 알고리즘

  • 기수 정렬 수행 과정 #1
    • 원소들의 일의 자리부터 비교 후 정렬, 다음은 십의 자리를 비교 후 정렬 ...

 

  • 기수 정렬의 수행 과정 #2
    • 정렬되지 않은[69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 기수 정렬 방법으로 정렬하는 과정을 살펴보자.
      • 키 값이 두 자리 십진수 이므로, 10개의 버킷을 사용하여 기수 정렬을 두 번 반복한다.

1. 초기 상태 : 큐(여러 개의 원소들이 일정한 순서로 나열된 자료 구조이며, 스택과는 달리 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있도록 되어 있음)를 사용하여 0부터 9까지 10개의 버킷을 만든다.

 



2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [1단계]

- 정렬할 원소의 일의 자리 값에 따라서 순서대로 버킷에 분배 -

 

 

2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [2단계]

- 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

 

 

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [1단계]

 - 정렬할 원소의 십의 자리 값에 따라서 순서대로 버킷에 분배 -

 

 

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [2단계]

 - 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

 

  • 기수 정렬 알고리즘 분석
    • 메모리 사용공간
      • 원소 n개에 대해서 n개의 메모리 공간 사용
      • 기수 r 에 따라 버킷 공간이 추가로 필요

    • 연산 시간
      • 연산 시간은 정렬할 원소의 수 n 과 키 값의 자릿수 d 와 버킷의 수를 결정하는 기수 r 에 따라 달라진다.
        - 정렬할 원소 n 개를 r 개의 버킷에 분배하는 작업 : (n+r)
        - 이 작업을 자릿수 d 만큼 반복

      • 수행할 전체 작업 : d(n+r)
      • 시간 복잡도 : O(d(n+r))

반응형
반응형

분포수세기 알고리즘

기수정렬 알고리즘

직접기수정렬 알고리리즘(분포수 세기가 활용) 등이 있다

이것은 이준수 정렬 알고리즘에 사용 될 수 도 있다

C++ 알고리즘 강의에 있음 참고

-기수 정렬은 비교 구문이 없이 정렬 된다

일반적으로 직접기수 정렬이 좋다


반응형

+ Recent posts