[Data Structure] 스레드 이진 트리

 스레드 이진 트리라는 것은 무척이나 생소한 개념이다. 허나 이 개념이 등장한 이유는 아주 심플하다. 여태 우리가 배웠던 순회라는 것은 모두 Stack를 사용했기 때문에 효율적이지 않다. 그 노드 수가 많아질 수록 시간이 오래 걸리기 때문이다.
 이러한 점을 해결하고자 나온 개념이 바로 스레드(Thread), 실이다. 하나의 노드를 순회하고 나서 순회 타입에 맞는 다음 노드를 연결시켜놓은 것을 스레드라고 한다. 그래서 이러한 트리를 Thread Binary Tree라고도 부른다.
 여기서는 간단히 개념만을 살펴보기 위해서 중위 순회시 적용된 스레드의 코드만을 볼 것이다. 중위 순회에서는 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리 순서로 순회를 하게 된다. 왼쪽 노드는 부모를 가리키면 되고 오른쪽 노드는 부모의 부모 노드를 가리키면 된다. 이 말이 어려울 수도 있는데 그냥 코드를 보면서 찬찬히 생각해보면 아주 쉽다.

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
    int is_thread;
} TreeNode;

// Node의 중위 후속자를 반환하는 함수이다. 이때
// 중위 후속자란 중위 순회를 할 때 해당 노드의 다음 노드(후속자)를 의미한다.
TreeNode* find_succesor(TreeNode *p){
    // q는 p의 오른쪽 포인터.
    TreeNode *q = (TreeNode*) p->right;
    // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 변환
    if (q == NULL || p->is_thread == TRUE) {
        // 오른쪽 포인터가 null일 경우는 완전히 모든 순회가 끝났을 때
        return q;
    }
    while (q->left != NULL) {
        q = (TreeNode*) q->left;
    }
    return q;
}

void thread_inorder(TreeNode *t){
    TreeNode *q;
    q=t;
    
    // 중위 순회이기 때문에 가장 먼저 맨 왼쪽 단말 노드로 향한다.
    while (q->left != NULL) q = (TreeNode*) q->left;
    
    do {
        printf("%c ",q->data);
        q = find_succesor(q); // 중위 순회시 다음 노드를 찾아 준다.
    } while (q);
}

int main(){
    TreeNode n1 = {'A',NULL,NULL,TRUE}; // threaded
    TreeNode n2 = {'B',NULL,NULL,TRUE}; // threaded
    TreeNode n3 = {'C',&n1,&n2,FALSE};
    TreeNode n4 = {'D',NULL,NULL,TRUE}; // threaded
    TreeNode n5 = {'E',NULL,NULL,FALSE};
    TreeNode n6 = {'F',&n4,&n5,FALSE};
    TreeNode n7 = {'G',&n3,&n6,FALSE};
    TreeNode *exp = &n7;
    
    n1.right = &n3; // A -> C
    n2.right = &n7; // B -> G
    n4.right = &n6; // D -> F
    
    thread_inorder(exp);
    printf("\n");
    return 0;
}

친절하게도 주석도 달아놨다 :D

[Java] 객체 비교

Java에서 객체를 비교할 때에는 ‘==‘ 연산자를 써야할까, ‘equals’ 메서드를 써야할까?

결론부터 말하자면 객체비교시 ‘==‘ 연산자는 각 객체의 주소 값을 비교한다. 반면 ‘equals’ 메서드는 객체 내부의 멤버들을 비교해서 같은지를 판단해준다. 

(커스텀 객체의 경우에는 equals 메서드를 오버라이딩 해야함)

다음의 코드를 보면서 곰곰히 살펴보자.

public static void main(String[] args) {

String s1 = "Hello";

String s2 = "Hello";

String s3 = new String("Hello");

String s4 = new String("Hello");

if(s1==s2) print("s1==s2");

if(s1.equals(s2)) print(“s1.equals(s2)”);

if(s3==s4) print("s3==s4");

if(s3.equals(s4)) print(“s3.equal(s4)");

if(s1==s3) print("s1==s3");

if(s1.equals(s3)) print("s1.equals(s3)");

}

public static void print(String what){

System.out.println(what);

}

 우선 s1과 s2를 비교해보자.

if(s1==s2) print("s1==s2");

if(s1.equals(s2)) print(“s1.equals(s2)");

이때 s1과 s2는 객체가 아니라 primitive 한 String이다. 즉 상수와 같다. 그러므로 이러한 String에 대해서는 ‘==‘으로 비교하더라도 내용을 비교하는데 아무 문제가 없다. 또한 ‘equals’ 메서드도 문제 없이 출력된다.  

이번엔 s3와 s4를 비교해보자.

if(s3==s4) print("s3==s4");

if(s3.equals(s4)) print(“s3.equal(s4)");

s3와 s4는 new String을 통해 객체화 시켰다. 아까 ‘==‘는 주소값을 비교한다고 했다. 그런데 new를 통해 생성된 객체들은 모두 다른 주소값을 가진다. 그러니 아무리 내용이 같더라도 ‘==‘비교로는 객체 내용이 같은지 판단할 수가 없다. 그래서 s3==s4에서 걸리지 않는것이다. 다만 equals 메서드는 객체 내부의 멤버를 비교하기 때문에 s3.equals(s4)가 true가 된다.

[Data Structure] 이진 트리 노드 개수 세기 (Counting TreeNode)

 요즘 들어서 하는 일이 많아져서 조금씩 밖에 못하고 있다. 이정도는 금방하고 넘어가야 하는데 조금 게을러졌다. 여튼 잡설은 여기까지 하고 ..

 이번에 볼 내용은 이진 트리에서 노드의 개수를 세는 방법이다. 어차피 현재 재귀 형식을 사용하기 때문에 직관적이고 쉽다. 또한 두번째로 단말 노드를 세는 메서드가 추가되어 있다. 단말 노드는 알다시피 자식 노드가 없는 마지막 노드를 의미한다.

 코드를 보자.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 노드 개수 세는 메서드
int get_node_count(TreeNode *root){
    if (root == NULL) return 0;
    int result = 1;
    result += get_node_count((TreeNode*)root->left) + get_node_count((TreeNode*)root->right);
    return result;
} 

// 단말 노드 개수 세는 메서드
int get_leaf_count(TreeNode *root){
    int result = 0;
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL){
        return 1;
    }
    result += get_leaf_count((TreeNode*)root->left) + get_leaf_count((TreeNode*)root->right);
    return result;
} 

int main(){
    TreeNode n6 = {300,NULL,NULL};
    TreeNode n5 = {500,NULL,NULL};
    TreeNode n4 = {200,&n6 ,NULL};
    TreeNode n3 = {100,&n4 ,&n5 };
    TreeNode n2 = {50 ,NULL,NULL};
    TreeNode n1 = {0  ,&n2 ,&n3 };
    printf("전체 노드의 수 : %d\n",get_node_count(&n1));
    printf("자식 노드가 없는 노드의 수 : %d\n",get_leaf_count(&n1));
    return 0;
}

[Data Structure] Binary Tree를 이용한 디렉토리 용량 계산

 이번에도 아주 단순한 코드를 소개한다. 이진트리를 활용해서 디렉토리의 용량을 계산해보자. 사실 말이 안되는게 하위폴더는 최대 2개다. 왜냐하면 우리는 이진트리를 공부해야 하니까.

 폴더의 용량을 계산하기 위해서는 하위 폴더의 모든 용량이 이미 계산되고 자신의 용량까지 더해줘야한다. 그래서 후위(post order) 순회를 사용한다. 후위 순회 코드랑 아주 유사하다. 다만 재귀적으로 폴더의 용량을 리턴한다는 점만 다르다. 원리는 똑같으니 더 이상의 설명은 생략한다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int calc_direc_size(TreeNode *root){
    if (root->left == NULL && root->right == NULL)
        return root->data;
    int left = calc_direc_size((TreeNode*)root->left);
    int right = calc_direc_size((TreeNode*)root->right);
    return root->data + left + right;
}

int main(){
    TreeNode n5 = {500,NULL,NULL};
    TreeNode n4 = {200,NULL,NULL};
    TreeNode n3 = {100,&n4 ,&n5 };
    TreeNode n2 = {50 ,NULL,NULL};
    TreeNode n1 = {0  ,&n2 ,&n3 };
    
    printf("디렉토리의 크기 : %d\n",calc_direc_size(&n1));
    return 0;
}

[Data Structure] Tree를 이용한 수식 계산

 우리는 예전에 스택을 이용해서 중위(infix), 후위(postfix) 방식의 수식 계산을 다뤘었다. 이것을 트리를 이용해서 할 수도 있다. 트리를 preorder, inorder, postorder 방식으로 traversal 하는 것과 같다.

 여기서는 트리를 이용해 후위 방식으로 수식을 처리해 볼 것이다. 여기서 트리는 피연산자는 항상 단말노드에 존재하며 연산자는 비단말노드로 구성된다.

 이러한 수식 계산을 위해 트리를 구성한 후에 재귀를 이용해 탐색을 한다. 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하고 그 값을 가지고 계산을 해주는 식이다. 여기서 리턴값들이 0 인 것은 수식이기 때문이다.

 코드를 보도록 하자. 금방 이해가 갈 것이다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int evaluate(TreeNode *root){
    // 재귀 호출 방식을 사용한다
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;
    int op1 = evaluate((TreeNode*)root->left);
    int op2 = evaluate((TreeNode*)root->right);
    switch (root->data) {
        case '+':
            return op1+op2;
        case '-':
            return op1-op2;
        case '*':
            return op1*op2;
        case '/':
            return op1/op2;
    }
    return 0;
}

int main(){
    TreeNode n1 = {1,NULL,NULL};
    TreeNode n2 = {4,NULL,NULL};
    TreeNode n3 = {'*',&n1,&n2};
    TreeNode n4 = {16,NULL,NULL};
    TreeNode n5 = {25,NULL,NULL};
    TreeNode n6 = {'+',&n4,&n5};
    TreeNode n7 = {'+',&n3,&n6};
    TreeNode *exp = &n7;
    
    printf("%d\n",evaluate(exp));
    return 0;
}

[Data Structure] Level Order

 저번 포스트에 이어 Binary Tree 순회에 대해 이어나가도록 하자. 이번에 다룰 순회방법은 Level Order이다. Level은 이미 이야기했다시피 이진 트리에서 계층을 나타내는 숫자다. 그렇다면 레벨 순회란 무엇일까.

 레벨 순회란 말그대로 레벨 별로 순회를 한다는 의미다. Level 1은 Root 노드를 의미하고 Level 2는 그 다음 계층의 노드들을 의미한다. 이렇게 레벨 별로 노드를 탐색하는데 여기서 제일 왼쪽편에 있는 노드부터 차례대로 탐색하게 된다.

 이 순회는 'Queue'가 사용된다. 노드를 참조할 때 자식 노드가 존재하게 되면 그 노드들을 Queue에 넣는다. 그리고 다시 큐에서 꺼내었을 때 그 노드값을 참조하고 다시 그 노드의 자식들을 큐에 집어넣는다. 이렇게 되면 레벨 Ordering이 된다.

 말보다 코드가 백번 낫다. 코드를 보자.

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100

typedef int element;
typedef struct {
    element data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

typedef struct {
    TreeNode queue[MAX_QUEUE_SIZE];
    int front;
    int rear;
} QueueType;

void init(QueueType *q){
    q->front = q->rear = 0;
}

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

int is_empty(QueueType *q){
    return q->front == q->rear;
}

int is_full(QueueType *q){
    return (q->rear+1) % MAX_QUEUE_SIZE == q->front;
}

void enqueue(QueueType *q, TreeNode *item){
    if (is_full(q)) {
        error("q is full");
    }
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = *item;
}

TreeNode* dequeue(QueueType *q){
    if (is_empty(q)) {
        error("q is full");
    }
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return &q->queue[q->front];
}

TreeNode* peek(QueueType *q){
    if (is_empty(q)) {
        error("q is empty");
    }
    return &q->queue[q->front];
}

void level_order(TreeNode *root){
    QueueType q;
    init(&q);
    TreeNode *tmp;
    enqueue(&q,root);
    while (tmp != NULL) {
        tmp = dequeue(&q);
        printf("%d ",tmp->data);
        
        if(tmp->left != NULL) enqueue(&q, (TreeNode*) tmp->left);
        if(tmp->right != NULL) enqueue(&q, (TreeNode*) tmp->right);
    }
}

int main(){
    TreeNode n1 = {1, NULL, NULL};
    TreeNode n2 = {4, (struct TreeNode*)&n1, NULL};
    TreeNode n3 = {16, NULL, NULL};
    TreeNode n4 = {25, NULL, NULL};
    TreeNode n5 = {20, (struct TreeNode*)&n3, (struct TreeNode*)&n4};
    TreeNode n6 = {15, (struct TreeNode*)&n2, (struct TreeNode*)&n5};
    TreeNode *root = &n6;
    level_order(root);
    
    return 0;
}

별로 어려운건 없다

[영화] 변호인 리뷰 (스포 없음)

 [스포없음 :D] 요즘 한창 영화 때문에 인터넷이 난리다. 그 영화가 바로 '변호인'이다. 왜 이렇게 영화 하나 때문에 난리일까. 바로 '변호인'이 대한민국 정치 이슈중 가장 뜨거운 감자인 '故노무현 전 대통령'의 이야기를 다뤘기 때문이다. 그렇다, 이 영화의 주인공은 바로 '故노무현 전 대통령'이다.

 사실 내가 TV를 좋아하지 않아서 그런지 변호인이라는 영화에 대해서 아무것도 모른 상태로 영화를 보게 되었다. 그러나 본 지 얼마 되지 않아 뭔가 느낌이 이상했다. 바로 주인공인 '송우석'이 고졸 변호사였기 때문이다. 어디선가 많이 들어본 것 같지 않은가? 고졸 변호사. 게다가 영화 시작시 넌지시 던졌던 '실화를 바탕으로 한 영화'... 

 다만, 묘했던 건 포스터나 광고에서는 특별히 '故노무현 전 대통령'의 냄새가 나지 않았다는 점이다. 아무래도 영화사 측은 최대한 정치적인 요소에 대해 언급하는 것을 피하는 모양새다. 아무래도 영화가 정치적인 이유로만 언급되는 것이 부담스러웠겠지. 

(1980년대 초 부산을 배경으로 세무 변호사 송우석의 인생을 송두리째 바꾼 다섯 번의 공판에 대한 이야기를 소재로 하고 있다. 고 노 전 대통령이 인권 변호사로 활동했을 당시를 영화화한 것이다.)

 하지만 아니나 다를까 이 영화는 '인간 노무현'을 이야기로 담음과 동시에 스스로 뜨거운 감자가 되었다. 그 동안 몇가지 일들이 있었다.

1. 일베의 '별점 테러' 공격

[참고 : 변호인, 개봉 전부터 공방 치열... '일베 회원 결집']

 아시다시피 일베는 한국 내 극우파계열의 사람들이 찾는 사이트로 알려져 있다.(사실 이 말이 맞는지 확신할 수 없다.. 근본은 극우이지만 하는 꼴을 보면 자극적인 기삿거리를 찾는 불나방 같다.) 이 사람들이 결집을 해서 '변호인'의 평점을 내려깎은 것이다. 

 이건 우파로서 해야하는 일이 아니라 그냥 유치한 짓이다. 영화는 영화관에서 사람들에 의해 평가 받아야 하는 것이지 자신과 이념 색깔이 다른 영화라고 의도적이고 집단적으로 이러한 결과를 만들어놓는 것은 정말 비겁한 짓이다. 이 녀석들은 입에 걸레를 물었는지 말 하나하나 더러운 냄새가 난다.

2. '송강호 죽이기' 검색어 

 갑자기 '송강호 죽이기'라는 검색어가 모 검색포털의 상위 검색어로 등극했다. 해당 키워드로 검색을 해보면 얼추 그 내용이 짐작이 간다. '故노무현 전 대통령'역을 맡은 송강호씨에게 정부가 압력을 가하고 있다는 것이다. 

[참고 : 송강호 죽이기 시작?.. "차기작 섭외 끊겼다" 발언]

 위의 사이트는 쿠키일보에서 올라왔던 기사를 캡쳐떠서 올려놓은 게시물이다. 원래 기사는 현재 삭제된 상태로 접속이 불가하다. 그런데 이 부분은 사실 그 진실성이 의심된다. 기사 자체가 엉터리였기 때문에 기사가 삭제된 것일 수도 있으며 사실 송강호가 저런 말을 했다는 것도 의심스럽다. 왜냐하면 그는 이번 해에 가장 큰 대박을 터뜨린 영화의 주인공이 아닌가? 그의 티켓파워는 이정도로 무너질 것으로 보이지는 않는다.  또한 정말로 저런 말을 했다면 왜 쿠키일보에서만 이런 기사를 찾을 수 있을까. 여튼 이 주제는 온통 추측 뿐이라 사실을 알 수가 없다. 

3. 영화 '변호인'의 흥행

[참고 : 노무현 효과? '변호인'의 흥행돌풍, 그 이유는?]

일베의 별점 테러에도 불구하고 영화 변호인은 그 기세가 만만치 않다. 현재 '변호인'의 별점은 8점대로 회복되었으며 빠른 속도로 별점이 상승하고 있다.

네이버 영화 '변호인' 평점 8.26. 현재 시각 2013년 12워 23일 새벽 2시 26분

 혹자는 현재 '변호인'의 흥행 이유를 '故노무현 효과'에서 찾을 수도 있겠다. 물론 이러한 면도 입소문을 타는데 주요했을 것이라 예상은 든다. 다만 직접 영화관에서 본 입장에서 말하자면 ..

 이 영화 생각보다 정말 재밌다 :D 송강호 특유의 그 찰진 연기와 영화 자체의 탄탄한 시나리오 구성 덕분에 보는 내내 몰입을 했다. 특히나 영화 속에서 최대 악역으로 등장하는 차동영 경감과의 한판 신은 긴장의 연속이었다. 그 팽팽한 긴장감 속에 송우석의 외침은 감동을 이끌어낸다.

 이 리뷰를 그 외침과 영화와 관련된 실제 '故노무현 전 대통령'의 사진으로 끝을 내겠다.  (감독이 이런 사진을 바탕으로 촬영을 했구나 하는 사실을 영화를 보신 분들은 느낄 것이다:D)

 

"대한민국 주권은 국민에게 있고

모든 권력은 국민으로부터 나온다.

국가란 국민이다"