Desperate Undergraduate!Desperate Undergraduate!

Merge Sort는 Divide and Conquer Approach의 일종으로 크게 3단계로 실행 된다.(2-Way Merge Sort 기준)

1. 리스트를 이등분 한다.(Divide)
2. 이등분된 리스트 두개를 정렬한다.(Conquer)
3. 이등분된 리스트를 병합하여 하나의 리스트로 만든다.(Combie)

다음은 Merge Sort를 C언어로 구현한 것이다.

(소스 생략)

(예제 생략)

Divide and Conquer Approach를 보면 Binary Search와 2-Way Merge Sort와 같이 세 개가 아닌 두 개를 사용하는 경우가 많다. 왜 두개를 사용하는가?

K-Way Merge Sort를 예로 들어 보면 K값을 3으로 할 수도 있고 2로 할 수도 있다. 2-Way Merge Sort와 3-Way Merge Sort의 시간복잡도(Time Complexity)를 생각해 보아야 한다. Divide and Conquer Approach의 경우 T(n) = Divide + Conquer + Combie 시간을 생각해 보아야 한다.

K = 2 인 경우, T(n) = 0 + T(n/2) + T(n/2) + n/2 + n/2 - 1

K = 3 인 경우, T(n) = 0 + T(n/3) + T(n/3) + T(n/3) + n/3 + n/3 + n/3 - 1

결국 입력 원소의 개수가 크다면 K 값이 큰 것이 되부름(Recursion)을 적게 하여 유리하다. 또한 병렬 처리를 할 경우 K 값이 큰 것이 좋다. 하지만 3-Way Merge Sort는 병합 과정이 복잡하기 때문에 메모리의 Activation Record를 낭비해서라도 2-Way Merge Sort를 사용한다.

예를 들어 생각해 보면, "1, 2, 3, 4, 5, 6, 7, 8, 9"에서 9를 찾는다고 가정해 보자. 각 Step 마다 n/2 만큼 감소하게 된다. 수식으로 표현해보면 Worst Case의 Time Complexity는 w(n) = w(2/n) + 1 이 된다. 이것은 w(n) = w(2/2^2) + 2 가 되고 다음은 w(n) = w(2/2^3) + 3 형태가 된다. n을 2^x 로 놓으면 w(n/2^x) + x 에서 w(n) = w(2^x/2^x) + logn 이 된다. w(2^x / 2^x)는 1이 되고 결국 1 + logn 이 된다. 그래서 System Stack Deapth는 1 + logn 이 된다.

C언어 펀더멘탈- 견고한 프로그램을 위한 기본 원리오늘 시험을 마치고 잠시 서점을 들렸다. 문득 예전에 EBS 다큐멘터리 "동과 서"를 본 것이 기억이 났다. 분명 오래전 다큐멘터리라서 책으로 출판되었을 것이라 생각하고 찾아보았다. 역시나 책으로 출판이 되었다. 정말 이 다큐멘터리를 볼 때 지적 충격을 감출 수 없었다. 그 전까지만 하더라도 동양과 서양의 문화가 다르기 때문에 언어도 다를 것이라 막연하게 생각하였다. 가령 우리가 쓰는 우편 체계나 이름 체계에서 볼 수 있다. 유교권 국가의 경우 개인보다는 집단을 우선시 한다. 특히 한국의 경우 징병제가 있기 때문에 사회가 아무리 서구화되어도 이러한 집단주의를 숨길 수 없다. 우편 체계에서의 주소를 보다. 우리는 지극히 내가 속한 곳 집단에서 부터 나에게 찾아온다. 서울특별시에서 동작구로 다시 동작구에서 흑석동으로 그리고 흑석동에서 번지로 그리고 그 번지에 내가 있다. 반면 서양의 주소 체계는 나로부터 밖으로 나간다. 흑석동, 동작구, 서울, 대한민국순으로 나아간다. 어쩌면 당연하다. 내가 존재해야지 세계가 존재하는 것 아닌가? 물론 이 물음 자체도 철학적으로 따지고 들면 복잡할 것이다. 내가 존재하지 않아도 세상은 움직이니 존재한다고 할 수 있지만. 우리의 이름도 대표적인 예다. 난 김씨 가문의 아무개이다. 하지만 서양은 다르다. 이름이 먼저 오고 성이 오게 되어있다. 내가 있고 그 다음 내 가문이 있다. 참으로 재미있다. 아무튼 이 책은 대학생이라면 꼭 읽어보라고 추천해주고 싶다.

오프라인 강연을 찾아 듣는 것이 취미이지만 요즘은 학기 중이라서 그렇게 하기가 힘들다. 그래도 다행인 것이 요즘은 미디어의 발달로 집안에서 좋은 강의를 들을 수 있다. 오늘은 TV 특강 "장자, 사랑과 소통의 지혜"를 보았다. 그런데 내가 착각한 것이 있다. TV 특강과 EBS 평생대학이 같은 것 인줄 알았다. 검색을 하여 확인해 보니 KBS에서 방영하는 것이였다. 아무튼 강신주 선생님의 이야기를 들으면서 참 재미있었다. 장자는 33편으로 구성되어 있고 각각 내편, 외편, 잡편으로 구성되어 있다. 각 편에서 여러가지 에피소드들이 있는데 그 중에서 오늘은 송나라 상인에 관한 에피소드를 다루면서 장자에 대해 생각해 볼 수 있는 기회를 가졌다. 장자는 삼현 중 하나이다. 동양철학을 공부하는 사람은 꼭 공부하여야 하는 책이다. 그래서 더욱더 의미 깊은 강의였다.

초보자가 보기에는 적합하지 않은 것 같기도 하고 적합하기도 한 것 같다. 어느 정도 C++에 대해 견고하게 학습하였다면 이 책을 읽는데 문제가 없을 것이다. 일단 초보일때는 두꺼운 책을 읽는 것이 중요하다고 생각된다. 왜냐하면 자세한 설명을 읽어야 이해가 되기때문이다. 이 책의 경우 얇지만 끝부분에 데이터베이스와 네트워크를 다룬다. 맛보기라고 해야 될지는 모르겠지만 결국 윈도우 프로그래밍은 방대하기 때문에 책으로는 해결할 수 없다. 다만 우리가 책을 통해 배울 내용은 접근 방법등의 방법론이다. 나머지는 내 스스로 해야 될 부분이다.

도서관에서 검색을 해 보니 구판은 한권있는데 신판은 없었다. 이상하게 우리학교 도서관에는 MFC 관련 서적이 없다. 작년에도 5권 정도 나 혼자 MFC 서적을 신청하였다. MFC 프로그래밍이 재미있지 않는 것인가?

시중에는 동영상 병합 프로그램이 많다. 그 중에서 이 제품이 제일 괜찮은 것 같다. 먼저 설치하지 않고 ZIP 압축 파일을 압축 해제하면 곧바로 실행할 수 있다. 또한 가볍다. 먼저 병합하려는 동영상을 Open file 또는 Open directory를 통해 읽어온다. 그러면 좌측 리스트에 우리가 선택한 동영상이 삽입되는 것을 알 수 있다. 병합 순서에 따라 맞출 수 있고 정렬기능을 이용하여 이름순으로 정렬할 수 있다. 병합하려는 파일을 합치기 위해서는 Join files를 통해 병합을 하면 되는데 이 때 주의하여야 할 것이 있다. 일단 경고 메시지 박스가 나타나는데 이 박스가 내 주의 사항을 설명해 주고 있다. 메시지 박스와 함께 콘솔창이 뜨고 파일을 체크한 뒤 병합을 수행한다. 그리고 시간이 지나면 파일을 다른이름으로 저장하라는 다이어로그가 나타난다. 만약 콘솔창이 나타나 있다면 끝날 때 까지 기다려야 한다. 콘솔 창의 작업 결과가 join.asf 파일로 C:\에 생성된다. 마지막으로 다름이름을 통해 이 파일(join.asf)을 다른 이름으로 저장한다.

피보나치 수열에서 알고리즘의 접근은 Sequential Approach와 Divide and Conquer Approach가 있었다. 이 방법에서 Divide and Conquer Approach가 Sequential Approach 보다 효과적이지 못하다는 것을 배웠다. 그러면 우리는 이 문제에 대해 일반화 시킬 수 있을까? 그것이 첫 번째 숙제이다.

My Solution)
두 가지 접근 방법이 있다고 가정하자. 하나는 Sequential Approach이고 다른 하나는 Divide and Conquer Approach이다. 우리의 목표는 집합에서 원소를 찾는 문제와 피보나치 수열 문제를 통해 일반화된 요약을 도출하는 것이다.

집합 : 유한 원소를 다룬다.
피보나치 수열 : 재귀 형태로 미지수 x에 따라 값이 변화한다.

Domain이 지정되어 있다면 Divide and Conquer Approach가 Sequential Approach보다 효율적이고, Domain이 지정되어 있지 않다면 Sequential Approach가 Divide and Conquer Approach보다 효율적이다.

Instructor's Solution)
하위 문제가 Overlapping이 많이 발생하는 경우, 분할 정복 접근보다는 순차접근이 효과적이다.

결과 : B

시장경제 역사의 교훈 (1)

컴퓨터공학부 4학년 김진욱

우리가 대학에서 배우는 것은 인간에 대해 공부를 한다. 공학 역시 마찬가지다. 그럼 공학이란 무엇인가? 인간을 기계로 모델링한 것이 공학이다. 이처럼 우리는 가깝게는 인간에 대해 공부하고 크게는 인간이 사는 사회에 대해 공부한다. 인간이 사는 사회를 모델링한 것이 컴퓨터 네트워크이다. 이러한 네트워크는 과학적이고 시스템적이고 논리적으로 동작하는 체계를 갖추고 있다. 그러면 인간이 사는 사회에도 체계가 있을 것이다. 그것은 자본주의이고 자세히 들어가면 시장경제가 있다. 그러면 우리는 자본주의가 뭔지 경제가 무엇인지 시장경제가 무엇인지 공부해 보아야 할 의무가 있다.

금일 수업의 첫 주제는 "역사로 본 국가의 경쟁력"이다. 즉 시장경제의 중요성을 역사적으로 살펴보는 시간 이였다. 소위 우리가 말하는 잘 사는 국가, 수치로 표현한다면 일인당소득이 높은 국가들은 대부분 서구 국가들이다. 이러한 서구 국가들은 어떻게 잘 살게 되었는가? 라는 질문에 답을 찾기 위해 역사를 살펴보기로 했다. 수업 시간에 김승욱 선생님께서 보여주신 다양한 역사적 자료(영화 300, 노예매매, 정화제독의 보선, 산업혁명)를 보면 서구 사회가 잘 살게 된 것은 정말 기적이라고 표현할 수 있었다. 결국 서구 사회가 잘 살게 된 것은 당연한 결과도 아니고 제3세계의 식민지 착취도 아니고 전쟁도 아니다. 바로 시장경제제도의 창출 때문이다.

강의를 듣는 내내 흥미진진하였다. 우리가 보고 있는 것이 정말 객관적으로 올바르게 보고 있는 것인지 다시 한 번 생각해 보게 되었다. 특히 서구 사회가 잘 살게 된 것은 식민지 착취라고 생각하였는데 여러 반론을 들어보면서 많이 알아야 진실이 보인다는 생각을 하였다. 앞으로의 강의를 통해 잘못된 생각은 바로 잡고 시장경제에 대해 탐구해 보아야겠다.