'[아는게 힘이다]'에 해당되는 글 72건

리눅스를 개발한 리누스 토발스(Linus Torvalds)의 TED 강연을 보았다. 괴짜로도 유명한 그가 여러 차례 자신이 people person이 아니라고 이야기하는 것이 인상적이다. 그는 리눅스뿐만 아니라 분산 소스 코드 버전 관리 시스템인 git을 개발한 것으로도 유명하다. git을 비롯해 그가 개발한 모든 프로젝트는 자신의 필요에 의한 것이라고 한다.

아래는 강연 막바지에 good taste를 가진 사람과 일을 하고 싶어 한다는 이야기를 하면서 예로 든 단일 연결 리스트(Singly Linked List)의 특정 노드 삭제 코드이다. 물론 이것보다 훨씬 크고 복잡한 수준의 코드나 설계에 대한 good taste를 지녀야 한다고 한다.

// not very good taste approach
remove_list_entry(entry) {
    prev = NULL;
    walk = head;
    
    while (walk != entry) {
        prev = walk;
        wal = walk->next;
    }

    if (!prev)
        head = entry->next;
    else
        prev->next = entry->next;
}

// better taste
remove_list_entry(entry) {
    indirect = &head;
    
    while((*indirect) != entry)
        indirect = &(*indirect)->next;
        
    *indirect = entry->next;
}

주어진 연결 리스트에서 일부분을 뒤집는 문제를 생각해보자. 연결 리스트에 [1, 2, 3, 4, 5]라는 값이 들어있고 2번째부터 4번째 사이를 뒤집는다고 하면, [1, 4, 3, 2, 5]가 된다. 연결 리스트 전체 뒤집기 문제보다 조금 더 생각할 거리가 있다.

전체 뒤집기와 다른 점은 뒤집기 경계에 있는 노드 정보를 기억해야 한다는 점이다. 뒤집기 부분 바로 직전 노드를 A라고 하고, 뒤집기 부분이 시작되는 노드를 B라고 하자. 그리고 뒤집기 부분이 끝나는 노드를 C라고 하자. 그러면 다음과 같이 처리해야 한다. 물론, 뒤집기 부분을 뒤집는 방법은 연결 리스트 전체 뒤집기와 같은 방법으로 처리해야 한다.

A.next = C
B.next = C.next

[1, 2, 3, 4, 5]의 예로 돌아가 보자. 뒤집기 부분은 [2, 3, 4]이다.  현재 노드가 가리키는 다음 노드가 현재 노드를 가리켰던 이전 노드가 되도록 하면 된다. (1) A노드는 1이므로 C노드인 4를 가리켜야 한다. (2) B노드는 2이므로 C노드의 next 노드인 5를 가리켜야 한다.

Before: 1[A] -> 2[B] -> 3 -> 4[C] -> 5
After: 1[A] -> 4[C] -> 3 -> 2[B] -> 5

개념은 위와 같다. 한 가지 주의해야 할 점은 뒤집기 부분이 첫 노드부터면 A노드가 실제로 존재하지 않고 head가 직접 C를 가리키게 해야 한다. 따라서 head가 C를 직접 가리키거나 A.next가 C가 되게 해야 한다. 이때 인자로 넘어온 head 값을 변경하기 위해서 포인터의 포인터를 사용해야 한다.

void reverseBetween(ListNode** head, int m, int n) {
	ListNode* cur = *head, *prev = *head, *start = NULL, **end = head;

	for (int i = 1; i < m; i++) {
		end = (ListNode**)&(cur->next);
		prev = cur;
		cur = cur->next;
	}
	start = cur;

	for (int i = m; i <= n; i++) {
		ListNode* nextnode = cur->next;
		cur->next = prev;
		prev = cur;
		cur = nextnode;		
	}
	start->next = cur;
	*end = prev;
}

풀기도 쉽지 않았는데, 설명하기는 더 어렵다.

정수 배열 N이 주어졌을 때 두 원소의 합이 특정한 값(T)이 되는 것을 찾는 방법에 대해 생각해보자. 예를 들면, N={-3, -5, 2, -2, 1}이고 T=-4라고 하자.

1. 모든 경우를 따져보는 방법 - O(N^2)
2. 해시 테이블을 사용하여 한 번만 읽으면서 찾는 방법 - O(N) (해시 테이블이 O(1)일 때)
3. 배열을 가리키는 2개의 인덱스(혹은 포인터)를 사용하는 방법 - O(N)

이 글에서는 3번에 대해서 생각해보자. 먼저 정렬하면 N={-5, -3, -2, 1, 2}가 된다. 두 개의 인덱스(low, high)를 사용한다. low는 첫 번째 원소, high는 마지막 원소를 가리키는 인덱스를 저장한다. 각 인덱스가 가리키는 원소의 합(S)을 구해본다. 목푯값인 T와 비교하여 T<S이면 high 값을 감소시킨다. 원소의 합이 목표치보다 크기 때문에 합(S)을 줄여야 하기 때문이다. 마찬가지로, T>S이면 low 값을 증가시킨다. 원소의 합이 목표치보다 작으므로 합(S)을 키워야 하기 때문이다. 이러한 과정을 low<high를 만족하게 하는 동안 수행한다.

위의 예로 값을 구하는 과정을 살펴보면 아래와 같다.

N[low] N[high] S   

----------------------------------

-5     2       -3  (T<S, high--)

-5     1       -4  (T=S)

조금 더 문제를 확장해서 두 원소의 합이 T에 가장 가까운 경우를 찾는다고 해보자. 이 경우에도 비슷한 방식으로 하는데, S와 T의 차의 절댓값이 최소가 되는 정보를 유지해야 한다. 절댓값이라는 개념이 들어가는데도 위와 같은 식으로 하는 게 처음에는 잘 이해가 안 되는데 결국 S가 T에 가까워지는 방향으로 가려면 T>S일 떄는 low++, T<S일 때는 high--을 해야 한다.

펜(UPenn)에서 인터뷰와 네트워킹에 대한 설명회(discussion)를 외국인 학생을 대상으로 열었다. 비록 학생은 아니지만, 내용이 도움될 것 같기도 하고 집에서 길만 건너면 있는 건물에서 열려서 소림이가 신청해주고 내가 대신 갔다.

엄청나게 새로운 것을 알게 된 것은 없지만, 인터뷰나 네트워킹에 도움이 될 실용적인 내용을 대단히 상세하게 알려줬다. 학부를 다닐 때는 취직은 너희가 알아서 능력껏 하라는 분위기였고, 대학원을 다닐 때는 내가 부지런하지 못해서 이런 프로그램의 도움을 받지 못했던 것이 아쉽다.

아래는 오늘 내용을 간단하게 정리한 파일이다. 대답하려면 충분히 미리 생각해보고 준비해야 할 질문이 많다.

interview_networking.pdf

구글 코드 잼 연습 문제를 오랜만에 풀어보았다. 사실 작년 12월 초에 풀다가 잘 안 풀려서 2달 정도 손을 놓았다가 다시 풀었다. 알고 보면 굉장히 간단한 문제인데, 접근을 엉뚱하게 해서 풀이만 복잡해지고 제대로 된 결과를 구할 수 없었다.

• 문제 보기

문제를 간단하게 서술해보자. 서로 함께 있으면 문제를 일으키는 쌍에 대한 정보를 준다. 과연 문제가 없이 사람끼리 모이도록 전체 사람들을 두 그룹으로 나누는 것이 가능한가?

접근 방법은 다음과 같다. 각 사람을 vertex로 하고, 서로 문제를 일으키는 사람 간에 edge가 존재하는 그래프를 생각한다. 그리고 각 vertex를 둘 중 하나의 색으로 칠하는데, edge로 이어진 두 vertex는 서로 다른 색이어야 한다.

처음에는 모든 vertex에 색이 없다. 칠해지지 않은 한 vertex를 선택하고, 그 vertex를 시작으로 BFS를 통해 연결된 vertex를 조사한다. 이때 이 vertex는 1) 색이 없는 상태 2) 연결될 수 없는 같은 색이 있는 상태 3) 연결될 수 있는 다른 색이 있는 상태 중 하나이다. 1)의 경우에는 다른 색을 칠하고 그것과 연결된 vertex들을 조사하게 한다. 2)의 경우 두 그룹으로 나눌 수 없다는 결론을 낸다. 3)의 경우 이 vertex에 대한 조사는 중단한다. (이미 이것과 연결된 vertex에 대한 조사는 끝났기 때문) 

BFS 과정에서 찾아지는 vertex가 없으면, 칠해지지 않고 남아 있는 vertex로 앞의 작업을 반복한다. 문제없이 모든 vertex를 칠할 수 있으면 두 그룹으로 나눌 수 있다.

• 풀이 보기

"성형 수술이 개성을 말살시킨다"라는 표현을 하고 싶을 때, '개성'을 표현하는 단어로는 individuality나 uniqueness, '말살'을 표현하는 단어로는 destroy 정도가 적절한 것 같다.

Plastic surgery destroys the individuality (or uniqueness) and character in each person's face.

다음은 아래 밑줄에 들어간 단어는 무엇인가를 찾는 것이다. 보기는 instinct/instinctual/instinctually였다.

It would be an ___________ panicked move with no forethought or malice.

일단 수업 시간에는 instinctually라고 했는데, 나는 instinctual이 답이 될 수 있지 않으냐는 의문을 제기했다. 이유로는 instinctual이 panicked의 앞에 있기는 하지만, move를 서술하는 형용사가 오는 것으로 보는 것이 옳다고 생각해서였다. 일단 원어민 선생님(TESOL 학생)이 instinctually라고 했고, instinctually가 의미상으로 panicked를 수식하는 것으로 봐야 한다고 했다.

물론 big red roses와 같이 두 개 이상의 형용사가 붙는 경우도 있는데, 이렇게 여러 형용사가 명사를 수식하는 경우에는 일반적으로 콤마(,)를 사용한다고 한다. 집에 와서 구글에 그 문장을 쳐보니 instinctual이 답이다. 아무래도 instinctual move와 panicked move에서와같이 둘 다 move를 수식하는 것으로 보는 것이 옳은 것 같다.

다음으로 minimum과 minimal에 대한 구분 문제가 있었는데, minimum은 명사라서 뒤에 명사가 오지 못한다고 하던데, minimum value와 같은 단어를 그동안 많이 봐왔기 때문에 이상했다. the minimum value와 같이 관사를 말이 된다고 하는데 정확한 설명이 부족했다. 좀 더 생각해보고 다시 정리해봐야겠다.

회사에서도 가끔 영어로 뭔가를 쓰다가, 이유를 쓸 때 as, since, because 중에 무엇을 써야 하는지 고민이 되는 경우가 있다. 초보 단계에서 영작하면 대부분을 because로 쓰는데, 영어로 된 문장들을 접하다 보면 as나 since가 굉장히 많이 쓰인다는 사실을 알게 된다. 그래서 한동안 because는 구리고, as나 since를 써야 모양새가 난다고 잘못 생각하기도 했다. 이참에 이러한 접속사를 간단하게 정리해 보도록 하겠다. 생각보다 간단하다.

[as와 since]

as는 since와 같다고 할 수 있다. 이 두 가지는 이유가 이미 널리 알려진 당연한 사실이거나 듣는 사람이 알고 있는 사실이라서 이유를 설명한 종속절보다는 그래서 어찌했다는 주절 부분이 강조된다. 

- As it's raining, I'll bring an umbrella.
- Since I haven't worked out, I am getting unhealthy.

참고로, 이 두 가지는 formal한 접속사라 일반 회화에서는 so를 활용한다.

- It's raining, so I'll bring an umbrella.
- I haven't worked out, so I am getting unhealthy.

[because]

이유가 전달하려는 정보의 핵심인 경우에 because를 사용한다. 

- I won't go to work tomorrow because the office is still under construction.

내일 회사에 가지 않는다고 말하려는데, 듣는 사람이 그 이유를 모르고 있는 경우이다. 이렇게 듣는 사람이 알지 못하는 정보를 알려주려는 경우에는 이유가 중요한 정보이므로 because가 된다. 아래 문장과 비교해보자.

- I won't go to work tomorrow since tomorrow is a holiday.

이 경우에는 쉬는 날에는 일하러 가지 않는 것이 당연한 편이므로 as/since가 적절하다.

[for]

for는 어떤 내용을 이야기하고 이유를 덧붙이는 정도로 사용한다. 이유를 나타내는 for는 문장 첫머리에 오지 않는다. 역시 formal해서 흔히 문어체에 사용한다.

- I decided to have lunch - for I was hungry.

[결론]

문맥에 따라 as/since를 쓰느냐 because를 쓰느냐를 결정한다.

7월 1일 자로 구글 리더 서비스가 종료된다[1]. 올해 초에 공지했는데도 막상 일주일 앞으로 다가오니 아쉬움이 남는다. 구독 피드를 백업해서 다른 서비스[2]로 이주하는 방법을 안내해주는 글은 많은데 정작 콘텐츠 백업 방법을 이야기해주는 경우는 별로 없었다. 구독하던 블로그 사이트가 중단되어 현재는 피드가 유효하지 않더라도 구글 리더 서버에는 기존 콘텐츠가 남아 있다. 이 글은 이 콘텐츠를 백업하는 방법에 대해서 다룬다.^[각주:1]

1. 구독 피드 정보 얻기

구글에 로그인한 상태로 http://www.google.com/reader/api/0/subscription/list에 접속하여 구독 피드 정보가 담긴 XML을 얻을 수 있다. 이 XML에서 원하는 사이트의 피드 주소를 얻어야 한다. 아래는 http://blog.sbnet21.com/rss가 피드 주소가 된다.

<object>
	<string name="id">feed/http://blog.sbnet21.com/rss</string>
	<string name="title">한순보 - ★조나단봉네 블로그★</string>
	<list name="categories">
...

2. 콘텐츠 얻어오기

위에서 얻은 피드 주소를 가지고 구글 서버에 저장된 콘텐츠를 가져오기 위해서는 아래 주소에 접속한다. 파라메터로 쓰인 n=100은 최대 100개를 가져오라는 의미이다. 한 번에 허용하는 최대 글(entry)의 개수, 즉 n의 최대값은 1000이다. (그 이상의 숫자는 의미가 없음)

# http://www.google.com/reader/atom/feed/[피드URL]?n=[받을 글의 개수]
http://www.google.com/reader/atom/feed/http://blog.sbnet21.com/rss?n=100

3. n이 넘는 개수의 콘텐츠 얻어오기

그렇다면 위에서 명시한 n을 넘는 개수의 글은 어떻게 가져올까? 그러한 글이 있으면 데이터 XML 상단에 <gr:continuation> 엘리먼트가 존재한다.

<gr:continuation>CMOM85vq07MC</gr:continuation>

이 엘리먼트의 값을 요청 페이지에 c의 값으로 파라메터에 추가하면 된다.

# http://www.google.com/reader/atom/feed/[피드URL]?n=100
http://www.google.com/reader/atom/feed/http://blog.sbnet21.com/rss?n=100&c=CMOM85vq07MC

4. 정리

일반적으로 블로그가 현재도 안정적으로 운영되고 있다면 굳이 리더 서버에 남겨진 콘텐츠를 수고스럽게 백업할 필요가 없다. 하지만 해당 블로그가 폐쇄되었다든지 해서 자료를 백업할 필요가 있는 경우 유용하다. 백업할 경우에는 위의 n을 1000으로 하고, <gr:continuation> 엘리먼트가 있는 경우 추가로 백업을 받으면 된다. 혹시 현재 XML에 몇 건의 데이터가 있는지 알아보려면 '<entry'가 몇 번 나오는지 브라우저의 검색 기능을 사용해보면 된다.

[1] http://googlereader.blogspot.kr/2013/03/powering-down-google-reader.html
[2] http://www.feedly.com

회사에서 간단한 UDP 소켓 프로그래밍을 할 일이 생겼다. 입사 후 1년 8개월 정도 되었는데 기껏해야 데모를 위한 웹 페이지를 만드는 정도였다. 지난달에 안드로이드 앱이 필요해 인터넷을 뒤지며 오랜만에 Java에 손을 적셨고, 이번에 이 프로그램을 짜면서 VC++에 발을 담갔다. 그런데 몇 가지 아주 기초적인 실수로 시간을 허비해서 적어본다.

struct data {
	int a;
	int b;
};
struct data d;
char msg[32];	// buffer

//////////////////////////////////////////////////////
// ... (this part is omitted) ...
// receive data from the network to the msg variable
//////////////////////////////////////////////////////

strcpy(&d, message);

네트워크로 받은 값이 d에 제대로 복사되지 않는다.^[각주:1] strcpy는 한 byte씩 복사하다가 값이 0이면 문자열의 끝이라고 생각하고 더는 값을 복사하지 않는다. 물론, strncpy를 해도 같다. 따라서 아래와 같이 memcpy를 이용해야 한다.

memcpy(&d, message, sizeof(d));

기초적인 내용인데 몇십 분을 헤맸다. 너무 오랜만에 C로 코딩해서 감이 없다.

다음은 샘플 소스에 있던 msg, strlen(msg) 부분을 보고 생각 없이 copy&paste를 해서 발생한 일이다.

send(sock, (char*)&d, strlen((char*)&d), 0);

위와 같이 하면 8bytes를 보내는 것이 아니라 d를 문자열로 봐서 8bytes 미만이 될 수도 있다. 내 경우엔 1byte가 됐다. 결국, 첫 번째 오류와 같다.

send(sock, (char*)&d, sizeof(d), 0);

이걸로 서버 프로그램이 잘못된 것이 아니냐며 관계자를 불렀다. '나는 프로그래머다'서 누가 말했듯, 자신에게 잘못이 없는지 생각하기보다 다른 사람이 잘못했을 것이라고 믿어버린 경우다. 나의 사소한 실수에 스스로 오그라들고 말았다.

프로그래밍도 감각을 잃으면 정말 사소한 곳에서 오류를 만들고 시간을 허비하게 된다. 틈틈이 프로그래밍을 게을리 말아야 겠다.