티스토리 툴바


opencv를 이용하여 MFC로 캠 2개를 돌리는 프로그램을 구현중이었습니다.
캡쳐 이미지를 계속해서 화면에 뿌리기 위해서 캠 수만큼의 스레드를 돌리도록 설계를 하였습니다.

간편하게 MFC에서 스레드를 돌리는 방법으로는, worker thread를 이용하는 것입니다.
worker thread는, AfxBeginThread API와 전역 함수(혹은 클래스 정적 함수)를 이용하는 것인데,
전역 함수를 쓰다보니 자연스레 전역 변수를 사용하게 되버리고,
java에 익숙한 MFC 초짜인 저로썬 왠지 맘에 들지 않더군요.-_-;;

그래서
변수들은 인스턴스가 들고 다녀야지!! 객체지향스럽게!!
란 생각으로 눈을 돌린 쪽은 user interface thread 입니다.

user interface thread는 CWinThread를 상속받아서 사용하는 것으로,
thread 내부에 변수나 사용자 정의 함수등을 추가할 수 있으며,
MESSAGE 처리를 지원한다는 장점이 있더군요!!

이를 사용하기 위해선 MFC 의 매크로 함수를 여기 저기 적어줘야합니다.
구글링을 해보면 사용법들이 쭉쭉 나오는데 대충만 정리해보자면,

1. class 선언부에(헤더파일) 
DECLARE_DYNCREATE(클래스명)

2. class 구현부에(cpp파일)
IMPLEMENT_DYNCREATE(클래스명, CWinThread)

을 써주는것부터 시작되어

virtual int Run();
virtual BOOL InitInstance();
virtual int ExitInstance();

등을 가상함수로 오버라이딩 해야 한다더군요.

(InitInstance : 스레드 시작시 호출. 초기화 개념. return TRUE 를 해줘야 스레드가 시작된다.
 ExitInstance : 스레드 종료시 호출. return의 의미 아직 찾아보지 않았다.
 Run : 스레드 시작부. 필수는 아님. 이유는? CWinThread 에는 이미 Run이 구현되어 있기 때문)

스레드를 돌리는 방법은

CWinThread *변수 = AfxBeginThread(RUNTIME_CLASS(클래스명));
으로 실행하거나
클래스명 *변수 = new CamPlayer();
변수->CreateThread();
로 실행할 수 있습니다.

갠적으로, 아래것이 더 좋더군요.
이유인 즉슨, 포인터 타입이 CWinThread가 아닌, 내가 만든 클래스의 포인터이기 때문에
직접 추가한 함수나 변수를 손쉽게 호출 및 접근할 수 있기 때문이죠.
(둘의 차이가 어떻게 나는지 더 나는지는 찾아보지 않았습니다)

이제 여기서부터 대대적인 삽질이 시작됩니다.

기왕 CWinThread로 가는것, MESSAGE를 적극 활용해보기 위하여 아래와 같이 정의하였습니다.

// ..h
#define WM_INIT_CAM (WM_USER+1)
#define WM_START_CAM (WM_USER+2)
#define WM_END_CAM (WM_USER+3)

// ..cpp
BEGIN_MESSAGE_MAP(CamPlayer, CWinThread)
//{{AFX_MSG_MAP(CMyWinThread)
ON_THREAD_MESSAGE(WM_INIT_CAM, OnInitCam)
ON_THREAD_MESSAGE(WM_START_CAM, OnStartCam)
ON_THREAD_MESSAGE(WM_END_CAM, OnEndCam)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

// ..h 의 class 선언부
DECLARE_MESSAGE_MAP()
afx_msg void OnInitCam(WPARAM wParam, LPARAM lParam);
afx_msg void OnStartCam(WPARAM wParam, LPARAM lParam);
afx_msg void OnEndCam(WPARAM wParam, LPARAM lParam);

그리고 다열로그에서 열심히 메시지를 날렸죠.
player1->PostThreadMessage(WM_END_CAM, NULL, NULL);

그런데, thread 가 메시지를 못받더군요. 왜? 왜?
처음 써보는거니, 잘못썼나 싶어서 별 짓을 다 해봤습니다. 안됩니다.
계속해서 삽질했습니다. 계속 안됩니다.

결국 알아냈습니다;;
이유는, Run 을 오버라이딩했기 때문;;;
Run을 지우니 비로소 메시지를 받기 시작합니다.
바로 CWinThread의 Run() 함수가 메시지를 처리하고 있었던 것이지요.
오버라이딩한 Run 내부에 CWinThread::Run() 을 추가해주니 잘 됩니다.

한번 Run함수를 MSDN 에서 찾아보았습니다.(여기)

Run acquires and dispatches Windows messages until the application receives a WM_QUIT message. If the thread's message queue currently contains no messages, Run calls OnIdle to perform idle-time processing. Incoming messages go to the PreTranslateMessage member function for special processing and then to the Windows function TranslateMessage for standard keyboard translation. Finally, the DispatchMessageWindows function is called.

Run is rarely overridden, but you can override it to implement special behavior.

This member function is used only in user-interface threads.


대충 요악해보면, WM_QUIT 메시지를 받기 전까지 잘 돌고, 메시지 없으면 OnIdle 수행한다는 말인데 허걱!!

허걱.....
Run is rarely overridden

이런 낭패가;;;;;
많은 웹상의 설명이나 예제들이 run을 구현하라고 되있더군요.
(사실 run을 구현할라믄, 그냥 편하게 worker thread를 쓰면 되는 겁니다.)
심지어 영어로 저 문장을 써놓고 "Run은 거의 오버라이드 한다" 라고 오역되있는 것도 보았습니다 -_-;;
역시, 웹상의 자료를 무조건 신뢰하면 안된다는걸 뼈저리게 느꼈습니다.


<< 결론 >>
user interface thread를 이용하여 thread message 기반 스레드를 작성시에는 Run을 오버라이드 하면 안된다. (걍 전역 함수 만들어서 worker thread로 돌리는게 편하다 -_-;;)

MFC 초짜의 Thread 삽질기 끝.
저작자 표시

' > 삽질기' 카테고리의 다른 글

MFC의 CWinThread 이용시의 MESSAGE 처리  (0) 2009/10/09
Posted by abekdh

:: 규칙 ::
>>  밤입니다. 램프가 있어야 다리를 건널수 있습니다.
>>  가족들은 각각 다리를 건너는데 시간이 다릅니다.
      [1-sec]   [3-sec]   [6-sec]   [8-sec]    [12-sec]
>> 다리는 오직 한명 또는 두명만 건널수 있습니다.
>>  두명이 건널때는 느린사람의 속도에 맞춰서 건너게 됩니다.
>>  램프가 30초 밖에 남지 않았습니다.

문제해결 첫번째 이군요.
정확히 기억나지는 않지만, 이 문제를 푼지는 꽤 오래됐습니다.

이 문제를 해결하는 포인트는 아래와 같습니다.
(먼저 풀어보실 분들을 위해 숨겨놓습니다)

더보기



갑자기 동기가 이 문제를 보내주더군요.
이미 풀어봤던거라 그냥 슥 지나갔는데,
누군가 '이 문제 최적화 답이 29초야?' 라고 묻더군요.
물론, 저의 답도 29초짜리 였습니다.

최적화 답을 찾아보자는 생각에 낼름 Optimal Solution을 찾아보았습니다.


<< 사고 과정 >>

앞서의 포스트에서도 말했지만, 컴퓨터와 인간의 풀이법은 다를 수 있습니다.
위에 제가 손으로 푼 사고 방식을 적었지만,
컴퓨터가 답을 낼 수 있도록 하기 위해서 다른 방법을 생각해보았습니다.
제가 선택한 방법은, 상태 노드를 정의하고 search tree를 만들며 성공 여부를 판단하는 것입니다.

나무 좌/우측에 누구 누구가 있는지, 현재 램프는 어디있는지, 현재 남아있는 시간은 몇초인지
등의 현재 상태를 노드에 저장하고,
현재 상태에서 이전 가능한 상태가 있는지 판단하여
상태 노드와 노드간의 관계를 이용하여 search tree를 만들어가며 모든 상태를 뒤지며
문제가 해결된 상태인지, 즉 모든 사람이 왼쪽에 있는지를 판단하는 것입니다.

간단히 말하면, 사람을 차례로 왔다 갔다 해보며 모든 상태를 뒤지는 것입니다.

보통 search tree를 만들고 탐색하는 과정은 exponential 한 time complexity를 가집니다.
따라서 input이 아주 적은 경우가 아니라면 heap overflow나 time limit exeed가 생기기 쉽상입니다만,
이게 어디에 submit할 문제도 아니고 하니, 그냥 시도해 보았습니다.

사람은 5명으로 얼마 없다고 생각하였지만, 5명 가운데 1~2명이 이동이 가능하므로,
각각의 상태에서 뻗을 수 있는 경우의 수는
5C1 + 5C2 = 15 가지 였습니다.

즉, O(x^15) 의 공간복잡도를 가질 수 있다는 것이지요...
하지만, 각각의 상태 노드가 램프의 남은 시간을 가져가며 0에서 끊어준다면,
어짜피 최대 depth가 많아봐야 10 을 못갈 것이기 때문에, 충분한 가능성을 가지고
코딩을 하였습니다.

그리고 결론적으로, 총 893의 노드를 탐색하고 답을 찾아내었습니다.

<< 소스 코드 >>
  


<< 결과 >>

최적화의 답은 29초였으며, 총 8개의 답이 나왔습니다.
결과적으로, 컴퓨터를 이용하지 않고 찾은 답과 같은 방식으로 시간을 줄인 답이
순서가 바껴서 8개가 나왔습니다.

find ans : 1 6 go LEFT 1 go RIGHT 1 3 go LEFT 3 go RIGHT 8 12 go LEFT 1 go RIGHT 1 3 go LEFT
TIME REMAIN : 1

find ans : 1 6 go LEFT 1 go RIGHT 1 3 go LEFT 1 go RIGHT 8 12 go LEFT 3 go RIGHT 1 3 go LEFT
TIME REMAIN : 1

find ans : 1 3 go LEFT 3 go RIGHT 8 12 go LEFT 1 go RIGHT 1 6 go LEFT 1 go RIGHT 1 3 go LEFT
TIME REMAIN : 1

find ans : 1 3 go LEFT 3 go RIGHT 8 12 go LEFT 1 go RIGHT 1 3 go LEFT 1 go RIGHT 1 6 go LEFT
TIME REMAIN : 1

find ans : 1 3 go LEFT 1 go RIGHT 8 12 go LEFT 3 go RIGHT 1 6 go LEFT 1 go RIGHT 1 3 go LEFT
TIME REMAIN : 1

find ans : 1 3 go LEFT 1 go RIGHT 8 12 go LEFT 3 go RIGHT 1 3 go LEFT 1 go RIGHT 1 6 go LEFT
TIME REMAIN : 1

find ans : 1 3 go LEFT 1 go RIGHT 1 6 go LEFT 3 go RIGHT 8 12 go LEFT 1 go RIGHT 1 3 go LEFT
TIME REMAIN : 1

find ans : 1 3 go LEFT 1 go RIGHT 1 6 go LEFT 1 go RIGHT 8 12 go LEFT 3 go RIGHT 1 3 go LEFT
TIME REMAIN : 1


이번 문제는 STL의 stack을 사용하여 DFS(Depth First Search)를 하여 해결하였습니다.
원래는 DFS는 optimal solution을 얻지 못하지만, 애초에 모든 solution을 찾는게 목적이었기에
가능한 모든 node를 뒤졌으므로 결과적으로는 optimal solution을 찾았습니다.
(사실 BFS를 하지 않고 DFS를 선택한 이유는, 첨엔 backtracking으로 해결하려 했기 때문입니다. :)


' > 문제해결' 카테고리의 다른 글

퀴즈 - 외나무 다리 건너기  (2) 2009/09/11
문제 해결  (0) 2009/09/11
Posted by abekdh

문제 해결

업/문제해결 2009/09/11 18:37
학부시절 가장 재미있게 들은 과목이 뭐냐고 묻는다면,
전 '문제 해결' 과목을 꼽고 싶습니다.

과목 명만 들어서는 어떤 수업인지 감이 잘 오지 않을 것입니다.
간단히 얘기하면, '현실의 문제들을 컴퓨터를 이용하여 해결'해보는 과목입니다.

그렇다면 '어떤 문제들을 다루는 것인가요?' 라고 물어볼 수 있겠지만,
바로 컴퓨터로 해결할 수 있는 문제를 찾는 것,
그래서 해결하고자 하는 문제를 정의하는 것 부터가 문제해결의 시작입니다.

현실에서 사람들의 생각 만으로는 풀기 힘든 문제들을 찾아내고,
이 문제를 컴퓨터로 처리할 수 있는 형태로 잘 모델링 한 후,
적절한 알고리즘을 선택하여 해답을 내는 것.
이것이 문제해결 과목에서 주로 다루던 내용이었습니다.

주된 강의 내용은 다양한 알고리즘 해설이였고,
과제로서 uva online judge의 문제를 풀어보는 것으로 진행된 수업이였죠.

강의를 통해 느낀것은, '컴퓨터와 인간의 사고 방식은 다르다' 였습니다.
사람한테 쉬운 것이 컴퓨터에겐 어려울 수 있으며,
반대로 컴퓨터에게 쉬운 것이 인간에겐 어려울 수도 있습니다.
중요한 것은, 컴퓨터의 연산과정을 잘 이해하여
이녀석을 어떻게 써먹을 수 있을지 충분히 파악하는 것이지요.

비록 수업은 끝났지만, 이바닥(?)에서 밥을 벌어먹고 있는 한,
계속해서 많은 문제들을 컴퓨터를 통해 해결해 나가야겠지요.

이 카테고리에서는, 이러한 문제들을 해결해 나가는 이야기를 해볼까 합니다.

' > 문제해결' 카테고리의 다른 글

퀴즈 - 외나무 다리 건너기  (2) 2009/09/11
문제 해결  (0) 2009/09/11
Posted by abekdh