Positive living

동적계획으로 구현을 위해서는 동적계획 부터 알고 넘어가야겠다. 동적 계획이란...
알고리즘 구현방법 중의 하나로 문제를 해결함에 있어서 기존에 계산된 결과가 있다면 그것을 사용하여 수행 시간을 단축 시키는 방법이다.
그럼 이 동적계획법을 사용하여 TSP를 구현함에 있어서의 기존에 구해진 재귀관계식 부터 살펴보자..맨땅에 헤딩 할 순 없으니깐;;;;;;ㅋ

TSP란 Traveling Salesman Problem으로 외판원 문제로 많이 알려져있다.
wiki백과를 찾아보면
외판원 문제(Traveling salesperson problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.
라고 어렵게 적혀있다ㅡ_ㅡ;
간단히 적어보면 그래프로 설명하면 되는데 아래와 같은 그래프가 있을때 각각의 정점을 있는 간선에는 가중치가 주어져 있다. 이 그래프에서 정점 v1에서 모든 정점을 거쳐 v1으로 다시 돌아 오기까지거치 간선들의 가중치가 최소가 되도록 하는 경로를 구하는 문제다. 이렇게 적고보니 별거 아닌거 같기도ㅋ

이번 네트워크 프로그래밍 과제로 선정된 snmp ! 그것도 snmp manager만들기!;;;
이때 까진 ftp 잘 해나가다가 왜 갑자기 바꾸냔 말이다 ㅡ_ㅡ+ 자료도 없는걸..ㅋ
.
.
SNMP란 Simple Network Management Protocol의 약자로 해석 그대로 간단한 네트워크 관리 프로토콜이다. 이렇게 듣고는 잘 이해가 안간다. 그래서 이놈을 자세히 일단 이놈은  TCP/IP의 응용계층 프로토콜로 디자인 되었고, 전송계층의 프로토콜로는 UDP를 사용한다. 이점이 좀 중요한듯!
아래 그림을 보면(ppt에서 훔쳐 왔음ㅋㅋ) snmp의 구성을 알수가 있다.

알고리즘 과제로 0-1배낭채우기와 Fractional 배낭채우기를 구현..
일단 두 문제에 대해서 간단히 짚고 넘어 가자면 0-1배낭채우기란 배낭에 넣을 아이템을 쪼갤 수 없다. 반면 Fractional 배낭채우기란 배낭에 넣을 아이템을 쪼갤 수 있다. 이 두가지의 차이를 빼면 이후에 조건은 배낭의 아이템을 넣어 최대의 이익을 얻는 문제다.
0-1배낭채우기는 동적계획법을 이용해서 구현했고, Fractional 배낭채우기는 Greedy알고리즘을 이용해서 구현 했다. 그리고 두 알고리즘의 비교를 위해 각각의 알고리즘의 수행 속도를 결과에 포함 시켰다.
아래 실행화면...

invalid-file

WM_CTLCOLORSTATIC - static control 색상을 변경할 때 사용
WM_CTLCOLORBTN      - button control 색상을 변경할 때 사용
WM_CTLCOLOREDIT     - editbox control 색상을 변경할 때 사용

사용예..

HBRUSH    hBrush_Control;

LRESULT WINAPI MsgProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
       switch(msg)
       {
        case WM_CREATE:
                 hBrush_Contorl = CreateSolidBrush(RGB(255, 255, 255));   //흰색 브러시 생성.
                   ...
                 return 0;
        case WM_CTLCOLORSTATIC:
                 SetBKColor((HDC)wParam, RGB(255, 255, 255);
                 return (LRESULT)hBrush_Control;
        }
}

대충 이런 식으로 사용한다.
lParam으로 특정 컨트롤의 색상만 변경도 가능하다.
if((HWND)lParam == hWnd_static01)
{
      //컨트롤에 대한 색상처리...
}

버튼같은경우 안먹던데ㅡ_ㅡ. 그리고 처음 브러쉬를 생성할때 색상이랑 SetBkColor함수에 넣어줄 t색상이랑 맞춰주는게 나을꺼 같다. static control의 경우 글자 주위의 배경색만 바뀌는거 같다.

현재 실행중인 process 확인
~]$ps -aux | grep 검색키워드
이렇게 하면 검색 키워드와 부분 매칭되는 모든 process를 뱉어 준다.

process를 kill할때는 위에서 확인한 pid를 이용해서
~]$kill pid
pid에는 위에서 확인한 프로세스 id를 적어주면 된다.
참고로 백그라운드로 실행중인 프로세스는
~]$jobs
로 확인해서
~]$kill %pid
로 죽여주면 된다!

현재 window api에서 제공되는 가장 정밀한 측정을 할 수 있다. 하지만 그만큼 부하가 크다. 그리고 하드웨어 적으로도 지원이 되어야한다.
일반적으로 시간을 측정할때 쓰는 함수임  timeGetTime()이나 GetTickCount()같은 경우 ms(millisecond)까지의 정확도를 보여준다. 하지만 아래의 두함수 QueryPerformanceFrequency와 QueryPerformanceCounter()를 이용하게 되면 us(microsecond)까지의 측정이 가능하다.

QueryPerformanceFrequecy 함수를 보면
BOOL QueryPerformanceFrequency(  LARGE_INTEGER *lpFrequency   );
parameter로 받은값에 현재 컴퓨터의 초당 tick수를 뱉어낸다. 자신의 컴퓨터하드웨어가 고해상도 타이머를 지원하지 않을겨우에는 false를 반환한다.

QueryPerformanceCounter함수는
BOOL QueryPerformanceCounter( LARGE_INTEGER *lpPerformanceCount);
parameter로 받은값에다가 컴퓨터가 부팅후 지나간tick수를 반한해준다.

그래서 이두함수를 이용하게 되면

LARGE_INTEGER start, end, count;

QueryPerformanceFrequency(&count);
QueryPerformanceCounter(&start);
//수행 시간을 측정할 작업..
QueryPerformanceCounter(&end);

passtime = end.QuadPart - start.QuadPart  / count.QuadPart

passtime * 1000(ms)
passtime * 1000000(us)

하지만 정밀한 측정을 하기에 무조건 좋은것은 아니다. 일부 메인보드 칩센에서 시간이 건너 뛴다거나 하드웨어적인 지원 유무등 문제가 있기때문에 유연한 코드가 필요할듯 하다.

학교 프로젝트 주제로 네트워크 패킷캡쳐 프로그램을 구현하기 winpcap에 대해 알아 보게 됐다!
.
.
.
일단 WinPcap란 무엇인가....!?
www.winpcap.org <- 여기에 가보면 잘 설명이 되어있다 영어로...
일반적으로 네트웍카드에는 항상 패킷이 오고가고 있다! 하지만 그걸 NIC(network interface card)에서는 들어오는 패킷이 나에게 오는것이 맞는가를 확인하고 맞다면 받아들여서 그에맞는 application으로 보내주고, 아니라면 즉각 폐기해 버린다.