태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

리눅스를 개발한 리누스 토발스(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;
}


'[아는게 힘이다] > [강의/강좌]' 카테고리의 다른 글

A good taste in code (리누스 토발스)  (0) 2016.04.12
인터뷰와 네트워킹  (1) 2016.02.24

주어진 연결 리스트에서 일부분을 뒤집는 문제를 생각해보자. 연결 리스트에 [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

'[아는게 힘이다] > [강의/강좌]' 카테고리의 다른 글

A good taste in code (리누스 토발스)  (0) 2016.04.12
인터뷰와 네트워킹  (1) 2016.02.24
  1. 소림 2016.02.29 14:00 신고

    아주 일목요연하게 잘 정리해줘서 고마워요^^ 역시 자기님은 멋지네요!!

구글 코드 잼 연습 문제를 오랜만에 풀어보았다. 사실 작년 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

  1. 미리 말해두지만, 구글 서버가 해당 사이트의 모든 콘텐츠를 가지고 있다는 보장은 하지 못한다. 즉, 그 사이트의 1번 글을 가지고 있다는 보장을 하지 않는다는 말이다. [본문으로]
  1. 2013.12.09 23:37

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2014.01.06 23:20 신고

      늦었지만 답변드립니다.

      질문을 제가 제대로 이해했다면, 일반 RSS feed에서 10개 이상의 엔트리를 볼 수 있는 방법을 알고 싶으신 것 같은데요.

      기본적으로 RSS feed는 최신 X개의 글에 대한 정보를 제공하는 것이라서 RSS feed를 제공하는 측에서 그런 방법을 일부러 제공하는 것이 아니라면, 따로 방법이 없습니다.

      예를 들면, http://blog.xxx.com/feed가 RSS feed 주소라면, http://blog.xxx.com/feed?paged=2를 하면 다음 X개를 보여준다든지. 그렇지만 일반 블로그에서 저런 방법을 제공하지는 않는 것 같습니다.

      질문을 잘못 이해했다면, 다시 알려주세요. :)

회사에서 간단한 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);

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

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

  1. 운이 좋아 d 내부의 a, b 값이 아주 크다면 제대로 값이 복사될 수도 있겠다. [본문으로]

'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글

부분합(subsum) 문제 관련  (0) 2016.02.25
그래프 색칠하기  (0) 2016.02.15
[C] 몇 가지 코딩 실수  (2) 2012.05.14
[C++/ACM] 820 Internet Bandwidth  (0) 2010.05.16
[알고리즘] Interval Scheduling  (2) 2010.04.29
  1. broYobi 2012.05.15 23:29 신고

    난 오히려반대 였다
    이틀동안 서버쪽 모듈에내가잘못한거나 간과한거없는지 찾다가 결국 L7이 문제연다는거ㅋ
    그나저나 난요즘c가하고싶은데 그럴일이없네

마트에서 닭을 사려는데 with giblets와 without neck and giblets라는 두 종류가 있었다. giblet이라는 단어가 무슨 뜻인지는 모르겠고 대충 '내장'일 것이다라고 (주부 100단 소림 부인께서) 추측을 할 뿐이었다. 

문득 마트 내에 서적 코너에 영영 사전이 있었음을 깨닫고 한 걸음에 달려가서 뜻을 찾아 보았다. giblet(s)는 the gizzards, the liver, and the heart of a poultry란다. (단복수 및 관사는 정확히 기억이 나지 않는다.) 그래서 또 gizzard를 찾아봤더니 the second stomach of a bird란다. 

결국 giblet은 '(조류의)내장'이고, gizzard는 내장, 특히 조류의 '모래주머니'라고 한다. 즉, 
닭똥집
'닭똥집'이다. 

예전에는 손도 못대던 문제가 그래프 관련 문제였다. 하지만, 의외로 많은 문제들을 그래프로 풀 수 있고 재미있는 문제들도 많다. 그래서 요새는 어떤 문제가 주어지면 혹시나
그래프로
그래프로 풀 수 있는게 아닌가부터 생각한다. 이번 문제는 문제만 읽어봐도 Maximum flow 문제라는 것을 알고리즘을 공부해본 사람은 누구나 알 수 있는 문제이다. 

학부 알고리즘 수준에서 NPC를 제외하면 제일 까다로운 부분이 아닐까 생각된다. 기초적인 부분을 제외하고 이론적으로 따지고 들면 따라가기도 꽤 어렵다. 어쨌든, 이 문제는 기본적인 Max flow 알고리즘을 따라가면서 풀면 쉽게(?) 풀린다. 가장 쉬운 Ford-Fulkerson 방식이다.

간략히 알고리즘을 살펴보자.
출발 노드(s)에서 끝 노드(t)까지 flow를 보낼 수 있는 path p를 찾아서 그 p를 이루는 edge들의 residual capacity (해당 edge로 더 보낼 수 있는 flow의 최대 크기)중에서 가장 작은 c_min를 먼저 구한다. BFS 혹은 DFS를 사용하여 해당 p가 존재하는지를 알 수 있다. p의 각 edge의 flow를 c_min만큼 증가(augment)시켜준다. 이러한 작업을 계속 하다보면 더 이상 s에서 t로 flow를 보낼 수 있는 길이 없게 되는데, 그 때 s에서 나가는 flow들의 합, 혹은 t로 들어가는 flow들의 합을 구하면 그게 Max flow가 된다.

처음에 당당히 WA(Wrong answer)를 받아서 왜 그런가 생각을 해봤다. 
  1. 먼저, 마침표(.)를 안 찍은 것을 발견했다. 또 다시 WA. 
  2. 이번에는 뭔가 구현상에 문제가 있는 것이 아닌가 생각을 했다. 교과서(CLRS)에는 anti-parallel edge만 존재한다고 가정한다. 따라서, 두 노드 사이에 edge가 어느 방향으로 있는지가 꽤 중요하다. augment하려는 edge가 존재하면 c_min만큼 flow를 증가시키지만, 해당 edge가 존재하지 않으면 반대 방향으로 flow를 증가, 즉, 원래 방향으로는 flow를 감소시켜야 한다. 하지만, 이 문제에서는 항상 bi-directional한 edge가 존재하므로 이 부분을 고려하지 않아도 된다고 생각했다. 그래서 다른 사람이 짠 소스를 살펴봤더니 a->b가 c_min만큼 증가되면, b->a는 c_min만큼 감소시켰다. 나도 그렇게 바꾸고 다시 제출했다. 그런데 역시 WA. 
  3. 이번에는 문제를 다시 읽어봤다. 각 test case마다 newline이 있어야 한단다. 추가했더니 AC(accepted)
  4. 다시 2번에서 고쳤던 부분을 원래대로 돌렸다. 역시 AC. 문제는 1, 3번이었다. 2번을 적용하도 않아도 되는 것이 맞는지, 아니면 우연히 맞은 것인지는 좀 더 생각해 봐야 한다.

소스 열기

알고리즘 수업을 들으면 Greedy 알고리즘의 첫 번째 예로 살펴보는 것이 바로 이 interval scheduling 문제이다. 작업 목록과 각 작업을 수행할 수 있는 시간 구간이 주어진다. 그리고 최대 몇 가지 작업을 할 수 있는지를 알아내는 문제이다. 실제로 선택되는 작업들이 유일하지 않을 수도 있다. 쉬운 예를 들어보자.
  
T1: 1시-3시 청소
T2: 2시-4시 숙제
T3: 3시-5시 낮잠
T4: 4시-8시 운동
T5: 7시-9시 TV시청
T6: 8시-9시 옆집가기

위의 각각의 작업은 주어진 시간을 꽉 채워 사용해야하고 그 때에만 가능하다고 하자. 최대 다양한 작업을 하기 위해서는 1시-3시에는 청소(T1), 3시-5시에는 낮잠(T3)을 자고, 7시-9시에 TV를 보면(T5) 된다. 다른 방법(T2, T4, T6)도 하나 있지만 어쨌든, 최대 3가지 작업을 할 수 있다. 작업이 몇 개 안되면 대충 눈으로 비교해보면 쉽게 알 수 있지만 일이 100가지, 1000가지가 된다고 해보자. 쉽게 풀 수 없다. 

물론 컴퓨터를 이용하면 사람보다는 좀 더 빠르게 풀 수 있을 것이다. 일단, 무식하게 생각해서 각 작업이 결과에 포함하거나 않거나 하면 되고, 모든 경우의 수 중에서 시간이 중복되는 작업이 없는 경우의 목록의 개수가 가장 큰 경우를 찾으면 된다. 작업의 종류가 n가지라면 최대 2n가지 종류가 나온다. 대략 n=100만 되어도, log2100=30.1이므로 1030이 넘는 경우의 수가 나온다. 좀 많다. 좀 더 효과적인 방법을 고안해 내는 게 알고리즘을 연구 혹은 공부하는 사람들이 밥 먹고 하는 일이다. 그 사람들이 무엇을 발견(?)했는지 살펴보자.

일단, 가장 먼저 끝날 수 있는 작업을 선택한다. 이제 그 작업이 끝나는 시간 이후에 시작할 수 있는 작업들 중에서 가장 먼저 끝날 수 있는 작업을 택한다. 또 다시, 그 작업이 끝나는 시간 이후에 시작되는 작업 중에서 가장 빨리 끝날 수 있는 일을 택한다. 이런 식으로 택하다보면 가장 많은 작업을 택할 수 있게 된다. 프로그래밍을 하자면, 현재 시점에서 가장 빨리 끝날 수 있는 작업을 찾기 위해서는 현재 시점에서 실행 가능한 작업 목록에서 작업 시작 시간을 기준으로 정렬을 먼저 한 후 찾으면 효율적이다. 

Greedy 알고리즘은 현재 시점에서 최선의 선택을 한 것이 결과적으로 문제 전체의 최선의 선택이 된다는 것이다. 그 때 그때 Local optimal을 선택하면 결국 global optimal을 찾을 수 있다는 말이다.

다음 문제는 위 문제보다 조금 더 복잡해 보이는 문제이다. 각 작업에 가중치(weight)를 줘보자. 경제학 용어를 쓰자면 효용이라고 하면 되려나?

T1: 1시-3시 청소 - 10
T2: 2시-4시 숙제 - 50
T3: 3시-5시 낮잠 - 20
T4: 4시-8시 운동 - 20
T5: 7시-9시 TV시청 - 10
T6: 8시-9시 옆집가기 - 10

효용가치가 높은 작업 해야 하는 것이 당연하고, 주어진 시간 내에 최대 효용을 얻는 행동을 하는 것이 경제적인 인간이 마땅히 해야 할 일이다. 따라서 위 문제는 최대 효용을 얻기 위하여 어떠한 작업들을 해야 하는지에 대한 문제가 된다. 앞의 문제는 이 문제에서 모든 작업의 효용이 같다고 전제하면 동일한 문제가 된다. 그렇다면, 이 문제를 앞과 동일한 방법으로 풀 수 있을까? 안 된다. 일단 앞의 풀이처럼 T1, T3, T5를 선택하면 효용이 총 10+20+10=40이지만, T2, T4, T6을 선택하기만 해도 효용이 총 50+20+10=80이 된다. 후자를 택하는 것이 더 효율적이지만 앞의 알고리즘은 전자를 택하므로 항상 옳은 결과를 가져온다고 볼 수 없다. 

또 알고리즘을 연구하신 분들의 도움을 받자. 이번에는 greedy 알고리즘이 아니라, 또 하나의 유명한 문제 해결 기법인 dynamic programming (동적 프로그래밍)을 사용해보자. 이번에는 끝나는 시간으로 오름차순 정렬을 한다. 이 작업들을 각각 T[i]라고 하자. v[i]를 첫 번째 작업에서 부터 i번째 작업까지를 고려할 때 얻을 수 있는 최대 효용이라고 해보자. i번째 작업의 효용은 w[i]라고 하자. 

일단, v[1]은 w[1]이 된다. 이제 v[1]에서 v[i-1]이 올바른 값을 가지고 있다고 가정하자. 이제 v[i] 값은 어떤 값이 될지 생각해보자. v[i]는 (1) i번째 작업이 시작하는 시간보다 해당 작업의 끝나는 시간이 더 빠른 작업까지를 고려했을 때의 최대 효용에 w[i]를 더한 값과, (2) 그냥 i-1번째 작업까지를 고려했을 때의 최대 효용 중에 큰 값을 갖게 된다. 

왜 그렇게 될까? (1)을 살펴보자. i번째 작업의 효용 w[i]를 포함시키기 위해서는 i번째 작업과 이전의 어떤 작업도 중복되어서는 안 된다. i<j인 경우 v[i]<=v[j]가 늘 성립하므로, 그러한 값 중에 가장 큰 작업을 찾아 w[i]를 더하면 i번째 작업을 포함하는 최대의 효용이 나온다. (2)의 경우 i를 포함하지 않는 경우를 생각하는 것이다. 그렇다면 최대 효용은 i-1번째 작업까지를 고려한 경우가 된다. w[i]를 더하기 전의 (1)과 (2)는 같을 수도 있다. i를 첫 번째 작업부터 마지막 작업까지 구하면, v[n]이 바로 우리가 원하는 결과가 된다.

알고리즘은
  1. 어떤 알고리즘을 써야하는지 알기 어렵고,
  2. 그 알고리즘이 왜 옳은지 알기 어렵고,
  3. 새로운 알고리즘을 만드는 것은 더 어렵다.
남에게 설명하지 못하는 것은 이해하지 못한 것과 같다.
설명을 하려고 노력하면, 그만큼 나의 이해도도 높아지리라 믿는다.
블로그를 그런 용도로 써봐야 겠다. ㅎㅎ
  1. masknecr 2011.08.30 16:24 신고

    interval scheduling problem 설명하신 부분에서 오류가 있는것 같아 글 남깁니다.

    weight가 없을시에 optimal solution은

    가장 먼저 시작할 수 있는 작업이 아니라 '가장 먼저 끝낼 수 있는 작업(earliest f-value)'입니다.. 물론 첫번째 작업을 선택한 이후에는, 첫번째 작업시간과 겹치지 않는 작업들중에서 가장 먼저 끝낼 수 있는 작업을 선택합니다.

    가장 먼저 시작하는 작업이 가장 늦게 끝나는 경우를 생각해보시길..

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2011.09.01 16:48 신고

      네, 지적 감사합니다. 수정했습니다.

      바로 시작할 수 있는 작업을 하는 것은 optimal solution이 아닌 예였던 것 같은데 잘못 써 놓았네요.

      읽는 분이 계신 만큼 앞으로 더 주의해서 써야겠습니다.^^;

문제) 주어진 문자열 배열에서 세번째로 긴 문자열 출력하라.

지난 번 폰 인터뷰에 나왔던 문제이고, 이전 포스팅인 '배열에서 두번째로 작은 수를 구하기'와 거의 유사하다. 다만, string class를 좀 제대로(?) 사용해보고자 다시 해봤다.

소스 보기

문제) 문자열 A가 주어지고, 그것보다 짧은 문자열로 구성된 배열 T가 주어진다. 배열 T에 들어있는 각 문자열이 A의 부분 문자열인지를 검사한다.

물론, C++에서 제공하는 string 클래스의 find 함수를 사용하면 하고 말 것도 없다. 여기에서는 좀 더 효율적이라고 생각되는 방법을 디자인해보는 것이 목표이다. 

예를 들어 A가 'apple'이라는 문자열이라고 하자. 이제, T의 임의의 문자열 t가 'apple', 'pple', 'ple', 'le', 'e'의 prefix인지 확인하면 된다. t의 첫 글자가 'a', 'p', 'l', 'e' 중의 하나가 아니라면 더 이상 비교해 볼 필요도 없다. 만일 t의 첫 글자가 'p'이면, 두 번째 글자가 'p' 혹은 'l'인지를 확인한다. A 문자열을 가지고 다음과 같은 N-ary Tree를 그리면 된다. 나의 그래프 표현 방식이 이해가 될지는 모르겠다. 왼쪽에서 오른쪽으로 보면 된다.

A+a-p-p-l-e
 +p-p-l-e
 | +l-e
 +l-e
 +e

이진 검색 트리(Binary Search Tree)는 나름 구현하기 쉽지만, N-ary tree는 구현해 본적이 없다. 자식 노드가 여러 개인 것을 어떻게 표현해야 할까 싶다. 노드의 자식 노드에 대한 포인터를 연결 리스트(Linked List) 혹은 배열로 구현해도 될 것 같다. 이번에는 C++에서 제공하는 vector를 사용해보기로 했다. 

그런데, 문제가 생겼다. 구조체 내에 vector를 선언하고 계속 데이터를 push_back을 하다 보니 메모리 위치가 중복되는지 segmentation fault가 난다. 해당 node 구조체를 malloc으로 선언할 때 그 구조체 크기보다 훨씬 크게 선언해주면 segmentation fault가 나지 않는다. 문제는 알겠지만, 해결책은 아직 구하지 못했다. 문제가 되는 라인은 32번째 라인이다.

아직 C도 아닌 것이 C++도 아닌 오묘한 코드이다.

소스 열기

문제) 전화기의 몇몇 번호에는 알파벳이 할당되어 있다. 전화 번호가 주어지면 가능한 알파벳 조합을 모두 출력하라. 단, 0, 1번에는 알파벳이 할당되어 있지 않고, 2~8번에 각 3개씩 알파벳이 할당되어 있다고 하자. 단 Q, Z는 할당되어 있지 않다.

일종의 순열 출력 문제라고 할 수 있다. 예를 들어 번호가 123번이면 1AD, 1AE, 1AF, 1BD, 1BE, 1BF, 1CD, 1CE, 1CF와 같이 9가지가 나온다. 기본적으로 재귀(recursion)를 사용하는 것이 생각하기 쉽다. 여기에서는 재귀 이외에도 반복(iteration)을 사용하는 것도 생각해보자.

더보기


나도 반드시 맞춤법이나 용례를 올바르게 사용한다고 할 수 없고, 인터넷에서 사용하는 언어의 특성을 이해하지 못하는 바도 아니지만 너무 심한 예가 있어 소개한다. 아래는 디시갤의 모 미드 게시판에서 퍼온 문장이다. 디시갤의 특성상 '띄워 쓰기 무시'라든지 '과도한 축약형 사용' 등은 너그러이 이해하고 넘어가자. 

A) 이번시즌근데 저번시즌보단 낮지않나요?-_- 

곧이곧대로 해석하면 이 문장의 뜻이 뭘까? 수학식으로 표시하면 이해하기 쉬운데, '이번시즌 < 저번시즌'이라는 말이다. 이제 위 문장에 바로 이어지는 다음 문장을 보자. 신기하게도
앞선
앞선 문장의 주장을 부정한다. 

B) 저번시즌 초반에만 재밌고 후반갈수록 지루하던데-_-

결국 '낮지'가 아니라 '낫지'라고 써야 A는 옳은 문장이 된다. '낫다'와 '낮다'를 잘못 사용하는 것은 의미를 완전히 반대로 만들기 때문에 반드시 주의해야한다. 사실 ‘낮다’를 두 가지를 단순 비교하는 단어로 사용하는 것 자체도 무리가 있다. ‘수준이 낮다’ 정도로 비교 대상을 명확하게 해줄 필요가 있다.

나는 네이버 댓글을 자주 본다. 기사를 보지 않고 댓글만 보는 경우도 있다. 기사가 지적하지 못한 문제점들을 댓글에서 발견하는 경우도 많고, 공들여 쓴 댓글은 기자(?)들이 쓴 원문보다 더 좋은 내용을 담고 있기도 하기 때문이다. 하지만 수많은 네이버 찌질이 댓글을 보면, '낳다'라는 말을 '낫다' 대신 사용하는 오류를 범한다. 뭐 이런 식이다.

C) 지뚫킥에서 세경신이 낳냐? 황정남이 낳냐?

낳기는 뭐를 낳나? '낳다'라는 말은 주로 아기를 '낳다'라든지 결과를 '낳다'와 같은 경우에 사용하는 단어이다. 물론 키보드에서 'ㅅ'과 'ㅎ'의 위치가 가깝기 때문에 오타일 가능성도 있지만, 대개 이런 사람들의 글에서 이러한 오류는 무수히 반복된다. 

'낳다'가 나온 김에, 나조차 헷갈리게 만드는 말이 있는데, '놓다'라는 말이다. 물건을 어디에 '놓다'로 많이 사용된다. 

D) 아기 놓고 잘 살아야지.

TV에서도 너무 많이 나오기에 이게 표준어인가 싶었다. "아기를 '낳고' 잘 살아야지"라고 생각했는데 너무 많은 사람들이 이런 말을 사용했다. 사실 '아기 놓다'는 경상도 방언이라고 한다. 사투리의 고유 가치를 생각해도 TV등에서 무분별하게 '놓다'라는 말을 사용하는 것은 문제가 있다. 댓글에도 재미가 아닌 이상 사투리로 댓글을 다는 사람은 별로 없는 것으로 안다. 즉, '놓다'가 사투리라는 사실을 알지 못하고 잘못 사용하는 것이다. 적어도 '표준어'가 뭔지는 제대로 알고 사용해야 한다는 점에서 반드시 시정해야 할 사항이다.

예전에도 블로그에 언급했던 '다르다'와 '틀리다'를 또 언급하고 싶다. '다르다'는 '같지 않다'이고, '틀리다'는 '옳지 않다'이다. 우리나라 사람들은 TV에서도 아나운서를 제외하고는 모두 '틀리다'라고 말한다. 물론 자막으로 '다르다'라고 지적하는 경우도 간간이 있다. 나도 내가 이 단어들을 잘못 사용한다는 사실을 지적받기 전까지는 모두 '틀리다'라고 사용했기 때문에, 지금 잘못 사용하는 사람들을 비난할 입장은 되지 못한다. 하지만, 제발 이제부터라도 제대로 알고 사용하자. 

개인적으로 이 오류는, 우리나라 사람들이 다른 사람과의 '차이점' 혹은 '다양성'을 옳지 않음으로 인식하는 경향이 있어 보여 더 싫다. '그는 나와 달라'이지, '그는 나와 틀려'가 아니다. 그 사람이 나와 같지 않은 것이지, 그 사람이 옳지 않은 것은 아니라는 말이다.

여담으로, 블로그에 한글 워드나 MS 워드 수준의 맞춤법 검사/교정 기능을 넣어주면 좋겠다는 생각이 든다. 나는 대부분 블로그에 글을 올리기 전에 한글에서 맞춤법 검사를 한다. 물론, 영어는 MS 워드를 사용한다. 완벽하지는 않겠지만 적어도 내가 쓴 글에서 명백한 오류를 많이 발견해준다. 맞춤법 검사도 안하고 기사를 올리는 인터넷 기자(?)들을 볼 때, 이것이 최소한의 예의라고 생각한다.
Given
two
two strings, s1 and s2, write a program to check if s1 is a rotation of s2. But you can use strstr() only once. (abcdef = cdefab)

간단해 보이는데 방법이 잘 떠오르지 않았다. 침대에 엎드려서 생각해낸 방법으로 열심히 코딩을 한 후 답안을 확인해보니 2줄이면 끝난다. 

내가 사용한 방법은 s1의 맨 끝단어(s1[n])와 맨 앞단어(s1[0])를 붙여서 이 문자열(t)이 s2에 존재하는 위치를 먼저 구한다. t가 s2에 존재하면 t가 존재하는 위치 뒷부분, s2의 맨 앞에서 t가 존재하는 부분 직전까지의 문자열이 각각 s1에 존재하는지를 적절하게 체크한다. 다만, t가 s2에 존재하지 않는 경우 중에 s1=s2인 경우가 있으니까 주의하여 체크한다. 

 s[0]{ A }{ B }s[n] -> { B }s[n]s[0]{ A }

정답에서 사용한 방법은 s1+s1인 문자열을 만들고, s2가 그 안에 존재(strstr)하면 된다. 간단하다. 결과적으로는 s1을 순환하는 문자열로 생각한다는 점은 비슷했는데 내가 쓴 방법은 아주 지저분하고, 정답은 깔끔하다. 문제는 인터뷰를 할 때 나처럼 푼다면 짧은 시간 내에 오류 없이 소스를 완성 시키지 못할 것이 분명하기 때문에 정답과 같은 접근이 반드시 필요하다. 아흥!

소스보기

Write a program to extract the longest repeated substring in a given string.

주어진 문자열에서 반복되는 가장 긴 문자열을 추출하자. 문자열의 길이를 n이라고 했을 때 가장 무식한 방법은 모든 가능한 문자열을 다 구해서 반복되는 문자열을 찾고 긴 문자열을 출력하면 된다. 비교 대상인 두 문자열의 시작점을 i, j라고하고 문자열의 길이를 k라고 하고, 비교할 수 있고 문자열을 비교하는 것 또한 k만큼 필요하므로 대략 O(n^4)이 나온다. 어쨌든, 좋지 않다.

이 문제에 접근하기 위해서 사용되는 것이 suffix array라는 것이다. 문자열에서의 각 시작점들의 인덱스를 값(element)으로 가지는 배열을 말한다. 말로 써놓으면 이해하기 어렵고 간단하게 예를 들면 'banana'라는 문자열이 있을 때 'banana'는 0번 인덱스부터 시작한 것이고, 'anana'는 1번 인덱스부터 시작한 것이다. 또한 'na'의 경우 4번 인덱스부터 시작한 것이다. 이러한 0, 1, 4 등의 값을 가지는 배열을 suffix array라고 한다.

a[] = {"banana", "anana", "nana", "ana", "na", "a"}

위와 같은 식으로 값을 가리키는 셈인데, 이것을 정렬하면

a[] = {"a", "ana", "anana", "banana", "na", "nana"}

와 같은 꼴이 된다. 이제 앞뒤 문자열만 비교하면 순서대로 몇 개의 문자가 일치하는지 쉽게 구할 수 있다. 이 경우 "ana"와 "anana"에서 3자리 문자열 "ana"가 가장 긴 반복되는 문자열이 된다. 이제 시간 복잡도는 O(n*nlogn)이 된다. n은 문자열 비교에서, nlogn은 정렬에서 온 수치이다.

소스 코드 상에서는 compare 함수에서 *(char**)a 를 사용하는 부분이 까다로왔다. 포인터에 대해서 좀 알게 되었나 싶었더니 여전히 잘 모르는 것 같다. 좀 더 알아봐야겠다. Programming Pearls에서 보고 감탄했는데, 알고랭이 좀 했다하는 애들은 중학생들도 아는 알고리즘이라는 것을 알고 나니 부끄럽다. -_-;

소스열기


  1. broYobi 2010.03.06 21:56 신고

    clever 하네

  2. 아로운 2014.08.28 12:18 신고

    블로그를 참고하면서 공부하고 있는 1인입니다.
    좋은 컨텐츠를 제공해 주셔서 감사를 드립니다, 많은 도움이 되고 있어요.
    (char*)대신 *(char**)을 쓰는 이유를 알 수 있을까요?
    실제로 코딩해봤는데 strcmp에서 정렬이 안되더군요.

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2015.11.18 04:18 신고

      답변이 너무 늦었지만, 훗날을 위해 답변 달아봅니다.

      buf 배열은 대상 문자열(e.g., banana)을 담고 있고, sa 배열은 대상 문자열의 각 문자를 가리키는 포인터를 담고 있습니다. 예를 들면, sa[2]는 첫번째 "n"의 주소를 갖고 있습니다. 따라서 buf는 char* 타입이고, sa는 char** 타입입니다.

      *(char**)을 살펴보면 일단 (char**)는 const void* 타입을 캐스팅한 것인데, a가 sa의 원소(element)를 가리키는 포인터가 되어야 하므로, sa의 타입인 char**로 캐스팅합니다.

      앞에 있는 *는 역참조(dereferencing)를 하기 위한 것인데, 우리가 비교하려는 대상은 sa 배열의 값 자체가 아니라 그것이 참조하고 있는 문자열 자체이므로 *를 사용해서 비교되는 대상이 buf 배열에 있는 문자열의 일부가 되도록 하기 위해서입니다.

      비교 대상은 sa의 각 원소가 가리키고 있는 문자열인데, 정렬되어야 하는 값은 sa의 각 원소입니다.

  3. Favicon of http://hexists.tistory.com BlogIcon hexists 2014.12.03 17:16 신고

    정리해주신 글 보고 잘 이해했습니다. 감사합니다.

  4. 2015.10.16 12:20 신고

    문자열 끊는 법을 몰랐는데, 이 글로 알게되었네요 감사합니다.

  5. 공부 2017.08.21 00:56 신고

    공부중인 학생인데요, O(n*nlogn)이 아니라, O(nlogn+n) 아닌가여?
    따로 도니까...

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2017.08.21 03:37 신고

      본문에서 '문자열 비교에서 n'이라고 한 것은 sorting 내에서 2개의 문자열 간 비교를 말한 것입니다. sorting 후 인접 문자열 간의 비교가 아닙니다. 본문 문장에 오해의 소지가 조금 있었을 수도 있겠는데, 원래 의도는 이렇습니다.

      보통 sorting의 예에서는 element 개수가 dominant하고 각 element간의 비교는 O(1)입니다. (e.g., 문자열의 길이가 상수) 그런데 이 문제에서는 element 개수가 문자열의 길이와 같기 때문에 아래와 같이 계산해야 합니다.

      element 개수를 n이라 할 때 우리가 사용한 sorting에서 비교 횟수는 O(nlogn)라고 합시다.

      이 문제에서는 두 element를 비교하는 compare 함수도 O(n)가 됩니다.

      따라서 이 sorting에서 문자(char) 비교 횟수는 총 O(n*nlogn)이 됩니다.

      감사합니다.

1에서 10,000까지 정수 중에서 무작위 100개를 뽑아내어 출력하자. 

수학 문제 같은 접근이 맘에 들지 않는다면 실용적인 예로 바꿔 보자. 

음악 사이트에서 10,000개의 곡이 존재하는데 랜덤하게 100개의 곡을 뽑아 랜덤 듣기 서비스를 제공한다고 해보자. 물론 각 곡은 고유 인덱스를 가지며 반드시 1에서 10,000까지만의 연속된 정수라고 할 수도 없다. 예를 들면 34,483번 등의 곡도 존재할 수 있다. 어떻게 할 것인가? 

실제로 예전에 회사에 다닐 때 마주친 문제이다. 당시 회사에서는 음악 사이트 리뉴얼 중이었고, 랜덤 재생 버튼을 누르면 엄청나게 오랜 시간을 잡아 먹는 현상이 있었다. 코드를 보지는 않았지만, 모회사의 개발자 구하기 글의 첫번째 함수 비슷하게 구현하지 않았었을까 생각된다. 당시 이 소스를 작업하던 분이 배열 섞는데 시간이 너무 오래 걸린다고 좋은 방법을 알아봐 달라고 해서 배열을 섞는 함수를 찾아서 알려줬던 기억이 난다.[각주:1] 어쨌든, 이 문제를 접했을 때 이러한 접근이 당연했고 가장 적합한 처리 방법이었다.

요즘 테크니컬 면접을 준비하고, 알고리즘 수업도 듣다보니까 문제를 바라보는 관점이 조금 Y군처럼 바뀌었다. 이 문제를 접하자마자 어떻게 풀까 고민을 시작했고, 방법을 알아내었다.[각주:2] 이후 이 문제가 나왔던 위의 모회사의 개발자 구하기 글을 마져 읽어 내려가다 충격을 먹었다. 당연히 이렇게 푸는 설명이 있을 줄 알았는데, PHP상에서 배열을 섞어주는 shuffle 함수를 사용하는 것이 정답(?)으로 나와 있어서였다.

그냥, 책 제목으로 있는 '생각하는 프로그래머'와 '실용주의[각주:3] 프로그래머'라는 말이 떠올랐다. 흔히 학교에 있으면 '생각하는 프로그래머'가 되려고 노력하고, 회사에 있으면 '실용주의 프로그래머'가 되야할 것만 같다. 물론, 둘 다 잘해야 하지만 이 예를 보면 조금 아이러니한 느낌이 든다. 이상한 생각인가? ㅎㅎ 

뭔가 글을 잘 쓰지 못하는 게 티가 팍팍 나는
포스팅이다
포스팅이다. 
뭐, 결론은 한 가지 문제에 대한 두가지 접근 방식이 존재한다는 말이다. ^^;
  1. 시간은 기억은 미화시킨다. 과정이 정확하지는 않을 수 있다. [본문으로]
  2. 배열에 대상이 되는 수(1~10000)을 넣고, 랜덤 함수로 0~1 사이의 실수 값을 구해서 10000을 곱하여 나온 값을 index하는 값을 추출한다. 배열의 마지막 인자(e.g, 10000)를 그 index 값에 넣고 이제 다음 랜덤값에는 9999를 곱한다. 이런식으로... [본문으로]
  3. 책의 실제 내용과 관계없이 '실용주의'라는 단어의 의미만 가져다 썼음. [본문으로]
  1. broYobi 2010.03.05 08:17 신고

    자연스레... 실용주의적으로 되던데.. ㅋㅋ
    뭐.. 모든 일은 혼자 다 할 수 없으니껭..ㅋ

테크니컬 면접 문제의 단골인 연결 리스트(Linked List). 그 중에서도 가장 많이 나온다는 뒤집기 문제이다. 

기본적인 연결 리스트를 구현 할 줄 알아야 겠다. C/C++을 이용한다고 할 때, struct 혹은 class로 먼저 node를 정의한다. 필요한 기본 함수로는 insert, delete, print(
traverse
traverse) 정도가 되겠다. delete는 뒤집기에는 필요하지 않으므로 생략한다. 

C/C++로 구현하기 위해서는 포인터에 대해서 알아야 한다. 새 노드를 head가 가리키는 첫 노드로 삽입하는 insert를 구현하기 위해서는 포인터의 포인터(A pointer that points to a pointer)를 인자로 넘겨야 head가 가리키는 노드를 새 노드로 변경할 수 있다는 점에 주의해야 한다. 

리스트를 뒤집는 reverse 함수를 구현할 때에도 잘못 생각하면 무한 루프에 빠지게 되는데 주의해야 한다. 이전 노드, 현재 노드, 다음 노드를 테이블로 그려보고 적절히 값이 어떻게 바뀌어야 할지 생각해보면 할 수 있다.

그런데, 종이만 주고 이걸 구현하라고 하면 쉽게 완성하지는 못할 것 같다. 포인터가 아직 완전히 익숙하지 않아서 부분부분 오류를 낼 것 같다. 조금 더 다양한 것을 구현해보는 연습을 해야겠다. 

소스 보기

  1. broYobi 2010.03.01 23:12 신고

    요즘 재미있는게 많이 포스팅 되네..ㅋ

    (쓸데없이)reverse를 recursion으로 만들고 싶지 않나?? ㅎㅎ

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.03.02 04:43 신고

      recursion으로 만들자면, 구 연결 리스트에서 head 노드를 계속 떼어서 새로운 연결 리스트의 head 노드로 넣으면 되나? [NIL, 1->2->3->4], [1, 2->3->4], [1<-2, 3->4] 좀 이상하네. 어떻게 하면 되겠노?

  2. broYobi 2010.03.02 14:26 신고

    이건 어때?

    Node* reverse(Node *node){
    Node *newHead;
    if(node==NULL)
    return NULL;
    if(node->next == NULL)
    newHead=node;
    return node;
    }

    newHead = reverse(node->next);
    node->next->next = node;
    node->next = NULL;
    return newHead;
    }

    메인함수에서
    reverse(&head)를 head = reverse(head)로 바꾸고..

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.03.04 17:50 신고

      {가 하나 빠진듯. if (node == NULL || node->next == NULL) return node;로 앞부분을 다 뭉뚱그려도 될 듯. 어쨌든, 잘 했네. recursive가 좀 더 직관적이긴 하네.

  3. 서여빈 2011.07.19 10:43 신고

    우연히 보고서 한마디 적어봐요 ㅋ
    위의 방법도 있겠지만 이런 방법도 있겠네요~
    기존 연결리스트 A가 있고 다른 헤드 역할을하는 B라는 포인터가 있을때 A 연결리스트를 루프를 돌면서 선택되는 모든 노드를 무조건 B포인터의 다음 위치에 두는거죠. 그럼 B연결리스트는 A연결리스트의 역순으로 생성이 되고 마지막에 헤드값만 바꿔버리면 끝!

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2011.07.22 07:35 신고

      결국 new linked list를 하나 만드는데 (with a new head - B)
      원래 list에서 순서대로 traverse하면서
      B에다 insert_after_headnode를 계속한다는 거군요.

      의견 감사합니다.

학부 1학년 때 컴퓨터 개론 시간에 C를 배웠던 것 같다. 당시 전혀 학과 공부를 신경쓰지 않던 나는 수업을 통해 배우는 게 별로 없었다. 아직도 C조차 제대로 모르는 이유는 여기에서 기인한다. 어쨌든, 그 때 마지막 과제던가? 퀵 정렬을 C로 짜오라는 과제가 있었던 것 같다. 당시에 퀵 정렬이라하면 최고 수준의 프로그래밍 실력이 있어야 할 수 있다고 생각했다. 마치, 1학년 당시 '학점이 3.0을 넘는 사람은 인간이 아니다'라고 믿었던 것처럼 어이없는 믿음이였지만 말이다. 재귀(recursion)가 들어가면 일단 머리가 돌아가지 않았다. 

 퀵 정렬의 기본 개념을 보면, 주어진 수 중에 임의의 값(pivot)을 기준으로 그 값보다 작은 값과 큰 값으로 나눈 후 이 pivot 값을 가운데 놓은 후, 두 부분을 각각 다시 퀵 정렬한다. 머지 정렬(merge sort)와 비슷한데, 머지 정렬은 단수히 두 분으로 계속 나누다가 합쳐질 때 양쪽에서 작은 값들 부터 뽑아 내어 정렬한다. A={1,3,4}와 B={2,5,9}가 있으면 A,B,A,A,B,B 순으로 앞의 수를 뽑아 {1,2,3,4,5,9}로 만들어 준다. 둘 다 평균 O(nlgn)의 시간 복잡도를 가진다. T(n)=T(n/2)+O(n)을 풀어서 나오는 듯.
#include <iostream>

using namespace std;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void quicksort(int *arr, int s, int e) {
	int p = s;

	if (s >= e) return;	

	for (int i = s; i < e; i++) {
		if (arr[e] >= arr[i]) {
			swap(arr[i], arr[p]);
			p++;
		}
	}
	swap(arr[p], arr[e]);

	quicksort(arr, s, p-1);
	quicksort(arr, p+1, e);	
}

int main() {
	int arr[] = {8,1,3,7,4,15,9,11};
	int arr2[] = {9,4,1,3,24124,12412,412,412, 3,1};

	quicksort(arr, 0, 7);

	for (int i = 0; i < 8; i++)
		cout << arr[i] << " ";
	cout << endl;

	quicksort(arr2, 0, 9);

	for (int i = 0; i < 10; i++)
		cout << arr2[i] << " ";
	cout << endl;
}
학부 1학년으로 돌아가면 즐겁게 다시 공부할 수 있을 것 같다. ㅎㅎ
  1. broYobi 2010.02.22 18:05 신고

    merge는 메모리를 많이 먹어용..

  2. Favicon of http://zzun.net BlogIcon zzun 2010.02.25 20:19 신고

    늦지 않았다 ㅋㅋ

이번 문제에서는 32bits 정수 n과 m이 주어지고 n의 인덱스 i, j가 주어진다. n의 i번째에서 j번째 사이의 bit들을 m의 bit들로 바꾸는 것이다. 예를 들어 n=11010이고 m=11인데, i=2이고 j=3이면 1[11]10이 된다. 물론 인덱스는 0에서 부터 시작하고 2^0을 나타내는 bit 위치가 index=0이다. (이런게 least significant bit인가?) 참고로 j>=i이다.

대략 알고렝이(알고리즘)를 보면 (a) n에서 m이 들어갈 위치를 0으로 만들어주고 (1[00]10), (b) m을 해당 위치만큼 좌측으로 shift해주고 ([11]00), 두 값을 or 연산 해주면 된다. 전자 (a)의 경우는 0이 되어야 할 자리에 1만 있는 값 ([11]00)을 만들고, 이를 모든 binary값으로 모든 자리가 1인 (~0) 값과 xor 연산을 해주고 (111~~11[00]11), 이를 다시 n 값과 and 연산을 하면 원하는 값이 나온다. (1[00]10).
#include <iostream>

using namespace std;

int insertMiddle(int n, int m, int i, int j) {
	int n1 = (((1 << (j - i + 1)) - 1) << i);
	int n2 = (n & (~0 ^ n1));
	int n3 = n2 | (m << i);
	
	return n3;	
}

int main() {
	cout << insertMiddle(26, 3, 2, 3) << endl;
	cout << insertMiddle(1024, 21, 2, 6) << endl;
}
원리도 간단하고 소스도 간단한데, 원리를 파악하고도 단지 이 3줄의 핵심 코드를 짜는데 (물론 한 줄로도 되겠지만) 1시간이 넘게 걸렸다. 예제 binary 값을 십진수로 바꿔서 함수의 인자로 넣는데 그 십진수를 잘못 계산해서 삽질하는 등등. 이 정도는 5분이면 짜내야 하는 것 아닌가 싶은데 정말 머리에 방법이 떠오르더라도 그걸 코드 한 줄로 옮기는 데 오류가 너무 많다.

정말 이런 쪽으로 머리가 나쁜 것 같단 생각이 든다. 예전부터 recursion이 머리로 이해가 안되고, dynamic programming이 이해가 안되던게 이런 쪽으로 머리가 너무너무 나빠서 그런가보다. 뭐, 다른 분야에 재능이 있을지도 모르겠지만, 내가 잘 해야하는/했으면 부분에서 이렇게 고생하며 자학(?)하게 되니 참 난감하다.
  1. broYobi 2010.02.22 17:00 신고

    그래도 넌 잘하는 거다.

이번에는 string에서 반복되지 않는 첫번째 문자를 찾아본다. 예를 들면 "appropriate"에서 o를 선택하면 되는 것이다. 문자열의 길이를 n이라고 하면 O(n)인데 실제로는 n을 최대 두번 읽는다. 더 좋은 방법은 없을까?
#include <iostream>

using namespace std;

char firstchar(string str) {
	char ch[128];
	char tmp;
	
	for (int i = 0; i < 128; i++)
		ch[i] = 0;
	
	int len = str.length();
	
	for (int i = 0; i < len; i++) {
		tmp = str.at(i);
		ch[tmp]++;
	}
	
	for (int i = 0; i < len; i++) {
		tmp = str.at(i);
		if (ch[tmp] == 1)
			return tmp;
	}
	return NULL;
}

main() {
	string str[] = {"Niceee", "babbyddas",
		"Gorooeadsjfabdfmadslfdlfa", "a", "aabb"};
	
	for (int i = 0; i < 5; i++)
		cout << firstchar(str[i]) << endl;
}
  1. Favicon of http://zzun.net BlogIcon zzun 2010.02.19 16:25 신고

    반복되지 않는 문자를 간단히 solo 라고 하면,

    루프를 한 번만 돌면서...
    1. 지금현재까지의 first solo
    2. 해당 solo가 탈락(중복)되었을 때의 next solo(배열)

    위 두 가지 정보를 유지/갱신하면서 돌면 될 것 같은데
    얼추 생각해봐도 코드가 매우 복잡할듯;

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.02.19 17:24 신고

      abacac의 경우 순서대로 a ab b bc bc a가 되어 a가 답이 되어야 하는데, 결국 이 solo 리스트에 현재 index의 문자가 있는지 매번 확인을 해야하니까 worst case가 O(n)이 되고, 전체는 O(n^2)이 되지 않나? 결국 걍 2n하는게 O(n)라서 더 나을 듯 한데. BST나 heap으로는 안될 것 같고.

      잘 모르겠다.

  2. broYobi 2010.02.22 18:03 신고

    이론적인 것만 고려한다면

    피보나치 힙을 (넣을 때, O(1), 뺄 때 O(log(n)) 사용하면 가능할 것 같네..

    하지만 실제로는 별 이익이 없네용....

  3. 2016.04.07 04:21

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.07 12:06 신고

      aba가 입력이면 b가 출력돼야 하는데 올려주신 코드에서는 nonchar가 나오게 됩니다. :)

      제 코드에서... 만약 주어진 문자열(str)이 엄청나게 길고 문자의 종류(위에서는 128개로 가정)가 적다면, 문자열은 한 번 읽고 특정 문자열의 등장 여부를 담은 배열(ch) 값을 한 번 search하는 것으로 바꾸는 식으로 위 코드를 개선할 수 있습니다.

      6년 전에 쓴 글인데 공부에 도움이 되었다니 기쁘네요. 덕분에 저도 다시 한 번 살펴봤습니다.

    • 2016.04.07 13:10

      비밀댓글입니다

  4. 2016.04.07 23:54

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.08 11:30 신고

      음.. aba에 대해서는 올바른 답인 b를 출력하는데, abbe를 넣으면 a가 아닌 e라는 오답을 출력하네요.

  5. 2016.04.08 23:11

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.09 04:20 신고

      이번에는 abcdedcba를 넣으면 e가 나와야 하는데, nonchar가 나옵니다.

      이 문제를 if문으로 처리하는 접근은 좋지 않습니다. 몇 가지 입력에는 유효한 답을 내겠지만, 입력 문자열이 길어지면 반례가 반드시 존재할 수밖에 없습니다. 왜냐하면, 답이 될 수 있는 후보를 다 기억하고 있어야 하는데, 이를 기억하려면 메모리 공간이 최악의 경우 O(n)이 필요하다는 이야기이고, 한두 변수만 추가해서는 해결할 수 없습니다.

      제가 본문에 제시하고 댓글에서 개선한 counting 접근이 유효한 솔루션이라고 생각합니다. (다른 더 나은 방법이 있을지는 모르겠지만...)

  6. 2016.04.09 04:37

    비밀댓글입니다

  7. 코리온 2016.10.11 15:40 신고

    비밀댓글 좀 그러네요 ^^

    좋은 내용 잘 보고갑니다.

이번에는 16진수(hexadecimal)를 10진수로 변환해주는 함수를 보자. 아래 코드와 같이 구현하면 처리가 되는데, 값이 너무 커지면 값이 보장되지 않는다. int는 4bytes이고 32bits이다. 16진수로는 4bytes가 한 문자(0,1, ...., A)의 값을 가지므로 총 8자리의 16진수까지만 (unsigned) int로 변환이 가능하다.
#include <iostream>

using namespace std;

unsigned int htoi(string hex) {
	int len = hex.length();
	unsigned int val = 0;
	
	for (int i = 0; i < len; i++) {
		val <<= 4;
		char tmp1 = hex.at(i);
		int tmp2;
		
		if (tmp1 >= 'A')
			tmp2 = tmp1 - 'A' + 10;
		else
			tmp2 = tmp1 - '0';
		
		val += tmp2;
	}
	
	return val;
}

main() {
	cout << htoi("0") << endl;
	cout << htoi("3") << endl;
	cout << htoi("AB") << endl;
	cout << htoi("A3") << endl;
	cout << htoi("11") << endl;
	cout << htoi("AB13") << endl;
}
뭔가 좀 더 깔끔하게는 할 수 없을까? 또한, 16진수의 음수 표현은 어떻게 되는가?
주어진 integer array에서 두번째로 작은 수(second smallest)를 구하여 보자. 일단 n개의 원소를 가진 정렬되지 않은 배열에서 가장 작은 값을 찾기 위해서는 n개 모두를 한 번은 살펴보아야 한다. O(n). 단순 무식한 방법으로 n개를 모두 살펴보면서 가장 큰 수를 찾아 제거하고, 다시 한 번 n-1를 찾아서 가장 큰 수를 출력하면 된다. 전체를 정렬하고 찾으려면 O(nlgn)이 들기 때문에 오히려 더 비효율적이다. (comparison based sort - 비교 기반 정렬)

배열의 원소가 적어도 2개 이상이라는 전제 하에, 아래 소스는 모든 원소를 두 번 읽지는 않고 한 번만 읽고 두번째로 작은 원소를 출력한다. 다만, 두번째로 작은 수가 아니라 임의의 i번째의 경우 이 방법은 사용할 수 없다. 이럴 경우에는 randomized selection을 써야 O(n)에 가능하다.
#include <iostream>

using namespace std;

main() {
	int a[] = {3, 1, 10, 34, 5, 3};
	int len = sizeof(a)/sizeof(int);
	
	for (int i = 1; i < len; i++) {
		if (a[i] <= a[0]) {
			a[1] = a[0];
			a[0] = a[i];
		} else if (a[i] < a[1]) {
			a[1] = a[i];
		}
	}
	
	cout << a[1] << endl;
}
그런데, 뭔가 더 좋은 방법이 있지 않을까?
  1. Favicon of http://zzun.net BlogIcon zzun 2010.02.19 16:03 신고

    이거 i=2 부터 아니고 i=1 부터 해야하지 않나?; {2, 1, 100, 100, 100} 일때 1이 출력될 것 같은데..

  2. Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.02.19 16:56 신고

    그러게, 너무 index 하나라도 줄이려는 생각이 앞서다보니 헛짓거리를 했네. Thanks.

C++
대략 학부 1~2학년 시절에 고민했어야할 이야기인 것 같다만, 간단한 프로그램을 짜다가 문제에 봉착했다. 결과값으로 29945를 기대했지만, 실제로 값은 29944가 나왔다. 실수값 연산은 가끔 이런 일이 일어난다.

double v = 299.45;
cout << (int)(v*100.0) << endl;

0.05 단위의 값들(299.40, 299.45 등등)을 처리하다보니 제대로 값이 나오는 것도 있고, 안 나오는 것도 있다. 결국 이래저래 찾아본 결과 아래와 같은 해결책을 제시한다.

cout << (int)(v*100.0+0.5) << endl;

대략 값이 곱셈 후  29944.99999999...가 되어 int로 casting을 하면 버림 처리되어 29944가 된다. 이를 보정해주기 위해 0.5를 더한 후 casting 해준다. 다른 코드들을 보면 0.1을 더한 것도 있고 마음대로인 듯 하다. 문제는, 어떤 c++ 컴파일러에서는 그냥 29945로 나온다는 사실이다. 저렇게 처리를 해주면 문제가 될 것은 없겠다만 뭔가 개운치 못하다.
시애틀에 CS로도 유명한 워싱턴 대학교(University of Washington)가 있는데 흔히 '유덥'이라고 불린다. 나는 그동안 이 말을 많이 보았음에도 불구하고 왜 '유덥'이라고 부르는지 이유를 몰랐다. 그러다 오늘 수업시간에 우연히 이유를 알게 되었다. 교수님이 'WWW'를 '덥덥덥'이라고 읽은 것이다. W(더블유)를 '덥'이라고 줄여 읽는 것[각주:1]이고 결국 '유덥'은 'UW'를 읽은 것에 불과한 것이다. 유딩 수준에서 재사회화를 거치고 있는 것 같다.
  1. 위키피디아 참고 http://ko.wikipedia.org/wiki/W [본문으로]
  1. Favicon of http://zzun.net BlogIcon zzun 2009.10.07 09:50 신고

    바람직하네 ㅋㅋ

영어에서 장소, 방법, 시간을 나타내는 부사구의 순서가 이것대로 된다고 해서 '장방시'라고 외운다. 오늘 교수님이 안 오셔서 수업을 안했는데, 아래는 집에 가기 직전에 두 미국인이 나눈 대화중에 나온 말이다.
He is usually here on time.  (그는 대개 여기에 제시간에 온다.)
here는 장소이고 on time은 시간이니 정확하게 맞다. 내가 영어를 해야한다면 이런 것들을 머리속으로 생각해서 장소를 먼저 말하고 시간을 나중에 말해야지 계산을 하거나 아예 무시를 할 것이다. 미국 애들이 이렇게 말하는 것은 보고 듣고 말한 습관 때문이겠지? 짧고 간단한 문장이었지만 의미 있는(?) 말이었다. 
  1. 소림 2009.10.07 09:29 신고

    내가 writing 선생님한테 이 부분에 대해서 물었었을때, 꼭 그런건 아니라고 하셨어ㅡ.ㅡ;;

  2. 조나단봉 2012.04.18 17:39 신고

    진짜 이해안가게 작성했네;; ㅉ

TRB(Terminated Reliable Broadcast)는 하나의 값을 여러 곳으로 보내 동일하게 저장해 두기 위한 방법이라고 볼 수 있다. 한편, consensus는 여럿이 값을 제안하고 일치 과정을 통해 동일한 값을 가지도록 하는 방법이다. 시험을 보기 위해 외워야 해서 네가지 property를 써본다. 

TRB (Terminated Reliable Broadcast) 
Validity: If the sender is correct and it broadcasts a message m, then all correct processes eventually deliver m
Agreement: If a correct process delivers a message m, then all correct processes eventually deliver m
Integrity: Every correct process delivers at most one message, and if it delivers m(!=SF), then some process must have broadcast m
Termination: Every correct process eventually delivers some message. 

Consensus
Validity: If all processes that propose a value propose v, then all correct processes eventually decide v.
Agreement: If a correct process decides v, then all correct processes eventually decide v.
Integrity: Every correct process decides at most one value, and if it decides v, then some process must have proposed v.
Termination: Every correct process eventually decides some value.

'[아는게 힘이다]' 카테고리의 다른 글

[English] 유덥  (2) 2009.10.07
[English] 장방시  (4) 2009.10.07
[CS] Four properties for TRB and Consensus  (0) 2009.05.13
[CS] Lamport's register  (0) 2009.05.03
[English] Three 9's는 무슨 말일까?  (0) 2009.04.06
  1. Safe Register: If a read does not overlap with a write, then the read returns the result of the latest completed write.
  2. Regular Register: Safe + overlapping read. It returns either overlapping write or the latest completed write.
  3. Atomic Register: Totally ordered.

어떤 register가 있고 여러 프로세스가 이 register에 read/write를 concurrent하게 할 수 있다고 하자. Concurrent의 개념은 한 프로세스가 이 register에 값을 read 또는 write하는 사이에 다른 프로세스도 역시 read 또는 write할 수 있다는 의미이다. 문제가 되는 것은 프로세스 A가 write를 하는 중간에 프로세스 B가 이 값을 읽으려고 하면 어떤 값이 read 될 것인가이다. Safe register는 일단, 이런 read와 write 사이 overlap 상황이 없을 때에 가장 최근에 write가 완료된 값을 리턴하는 것을 보장해주는 register이다. Regular register는 safe register가 보장해주는 것을 보장하는 것과 동시에 overlap상황이 있는 경우 최근에 완료된 write 혹은 현재 write하고 있는 값 둘 중에 하나를 리턴해준다는 것이다. Atomic register의 경우 어떤 totally ordered된 실행 순서가 존재하고 어떠한 read 요청에 대해서도 이 순서를 보장해주는 것이다. 

예를 들어, register x에 대해 5라는 값을 쓰는 것을 write(x, 5)라고 하자. write(x, 5)가 존재하고 이후에 write(x, 6)이 존재한다고 하자. write(x, 6)을 하는 중간에 A가 read(x)를 하고, 잠시 후 역시 write(x, 6)이 진행되는 중간에 B가 read(x)를 했다고 하자. 이 경우 Safe register는 어떠한 값을 리턴할 것인지에 대해 아무것도 보장하지 못한다. Regular register의 경우 완료된 값인 5 혹은 overlap되고 있는 값인 6 중에 하나를 리턴한다. Regular register의 경우 A는 6을, B는 5를 리턴 받는 경우가 발생할 수도 있다. 그러나, Atomic register의 경우 A가 6을 리턴한 경우 반드시 B도 6을 리턴하는 것을 보장한다. write(x, 6)이 완료되는 시점이 반드시 존재하고 write(x, 5)의 값이 리턴되는 시기와 write(x, 6)이 리턴되는 시기가 바뀌는 시점이 존재한다. 따라서 A, B는 각각 (5, 5), (5, 6), (6, 6)을 받을 수는 있지만 (6, 5)를 받을 수는 없다. 
Atomic Register

Atomic Register

별로 중요한 것은 아닌데 심심해서 적어본다. (잘못 설명했을 수도...) 그나저나, 영어에서 If A, then B. 즉, propositional logic에서의 A->B는 참 받아들이기 어렵다. A가 참이면 B도 참인데, A가 거짓이면 B는 뭐든 상관없다라는 것. 나는 '상관없다'라는 것이 잘 와닿지 않는다. -_-;

+ Recent posts