LimeCoding

이전 포스팅에서 완전 이진 탐색 트리에 대해 설명했지만 이 포스팅을 통해 들어온 사람들을 위해 다시 설명한 후 AVL트리를 설명하겠다. 완전 이진 탐색 트리(Complete Binary Search Tree) 이진 탐색 트리는 자료를 탐색하는데 최적화된 트리이다. 하지만 자료가 오름차순이나 내림차순과 같은 순서대로 입력되면 트리가 한쪽으로만 만들어지는 형태가 된다. 이는 연결 리스트와 다를 바 없는 형태로 이진 탐색 트리의 장점인 빠른 검색 속도를 이용하지 못한다. 이를 해결하기 위해 나온 것이 완전 이진 탐색 트리이다. 완전 이진 탐색 트리(Complete binary search tree)는 완전 이진 트리의 성질을 가지는 이진 탐색 트리이다. 완전 이진 탐색 트리는 편향된 이진 탐색 트리와는 다르게..

이진 탐색 트리란?(What is a Binary search tree?) 이진 탐색 트리(Binary Search Tree, BST)는 이진 트리에서 자료의 탐색, 삽입, 삭제를 효율적으로 하기 위해 만들어진 트리이다. 연결 리스트의 경우 삽입, 삭제시 O(1)의 시간 복잡도를 가진다. 그러나 자료를 탐색하는 경우 O(n)의 시간 복잡도를 가진다. 반면 이진 탐색 트리의 경우 트리의 높이를 h라고 했을 때 O(h)의 시간 복잡도를 가진다.(노드의 개수를 n이라고 하면 O(Log n)의 시간 복잡도를 가짐) 다음은 이진 탐색 트리의 정의이다. 정의 이진 탐색 트리는 공백이 가능한 이진 트리로서, 공백이 아닐 경우 다음의 조건들을 만족한다. 모든 노드는 이진 탐색 트리내에서 유일한 키를 갖는다. 임의의 노..

일반 트리는 차수가 불규칙하기 때문에 자료를 처리할 때 이진 트리에 비해 비효율적인 면이 있다. 그렇기 때문에 일반 트리를 이진 트리로 변환해야 할 때가 있다. 일반 트리를 이진 트리로 변환하는 방법은 다음과 같다. 먼저 각 부모 노드당 2개의 노드만 가지도록 부모 노드의 왼쪽 자식과 오른쪽 형제를 연결한다. 다음 적절한 각도로 트리를 회전시킨다.(대부분 45도로 회전하라고 한다.) 회전한 트리를 적절하게 재배치를 하면 이진 트리가 된다.

요즘 일기말고 다른 글을 못 쓰고 있다. 공부한 내용을 올려야 되는데 공부하는 것부터가 시간이 많이 걸려서 올릴 시간이 없다. 이제 개강한지 4주차. 4주후면 시험이다. 공부도 해야되는데 아직 블로그에 올리지 못한 내용이 너무 많다. 학교 공부에다 과제까지 있는데 거기다 책도 읽어야되고 개인공부에 블로그 포스팅까지 할 건 많은데 시간은 없다. 놀고 싶은데 놀면 노는대로 괴롭고 안 놀면 안 노는대로 괴롭다. 그냥 미치겠다. 일단 일주일에 한번이라도 올리려는 노력을 해야겠다.

아주 좋아! 의지가 있으니 게임도 안하게 되고 공부도 다시 조금씩 시작하고 있다. 다만 문제가 있다면 트위치와 유튜브를 다시 보려고 한다. 그래서 아예 휴대폰을 눈에 안보이는 곳에 두고 컴퓨터는 어쩔수 없이 켜야되니까 트위치를 최대한 보지 않는게 상책이다. 솔직히 볼것도 없긴 하다. 단지 공부는 하기 싫으니까 보려고 하는 거다. 그래서 차라리 트위치가 보고 싶으면 책을 읽기로 했다. 여유시간에 보는건 좋지만 공부하는 시간까지 침범하면 안되니까 차라리 공부시간에 공부 안한거면 책읽는 편이 더 났다. 3월이 거의 끝나가는데 목표한 바를 못이룬것 같다. 아쉽다.

오늘은 책을 빌려야 할 때가 와서 도서관에 갔다왔다. 저번에 동대문 도서관에서 모든 책을 가져 왔는데 이번에는 딱 1권이 없어서 2개의 도서관을 이용해야 한다. 책을 사면 좋지만 한권에 3~4만원이나 하는데다가 막상 집에 책을 두면 많이 안본다. 차라리 도서관에서 빌리면 반납할때라도 책을 보니까 오히려 이게 더 좋은 것 같다. 돈도 교통비만 들이면 되서 운동할 겸 도서관 갔다와도 좋다. 하튼 강서도서관에 갔다왔는데 내가 예전에 찾던 책이 있었다. 혹시나 하는 마음에 "자본주의 동물농장"을 찾아보니 있었다. 전에는 강서도서관을 몰라서 책을 사려고 했는데 절판이라서 구하기 어렵다는 말을 들었다. 한창 조지오웰의 동물농장과 1984를 읽고 공산주의 비판에 관심이 많았는데 자본주의 비판하는 책은 없어서 찾던 중..

오늘은 갑자기 내 서랍 속에 있던 재미있는 물건이 생각나서 꺼내 보았다. 예전에 "나의 이름은" 이라는 영화를 인상깊게 봤다. 영화에서는 무스비라는 매듭이 사람과 사람을 이어주는 역할을 하는데 이게 뭔가 부적같이 가지고 있으면 좋은 일이 일어날 것 같아서 가지고 싶었다. 그래서 집에 가자마자 매듭을 사려고 했는데 집에서도 만들 수 있다는 얘기를 듣고 다음날 재료를 사다가 만든 적이 있었다. 평생 손재주 없다고 생각했는데 이런 걸 만들 생각을 한다는 게 사람이 하고 싶으면 어떤 이유도 필요가 없어진다는 걸 느꼈다. 매듭을 만들면서 나도 멋진 일이 일어났으면 좋겠다라는 생각으로 실을 엮었다. 다 완성하고 난 후 봤을 때 조금 삐뚤어진 부분이 신경이 쓰였지만 내가 만든 첫 작품치고는 괜찮았다. 그렇게 잠깐 팔..

오늘은 게임을 안하는데 성공했다. 그렇다고해서 뭔가 의미있는 일을 한 것도 없다. 게임 안하면 유튜브 유튜브 재미없으면 게임. 아마도 시간을 이렇게 쓴 사람중 성공한 사람은 아무도 없었을 것이다. 그러면서 매일 길을 모르겠다고 지랄을 하니 한심하기 짝이 없다. 최소한 노력이라도 해보고 그런 소리를 하던가. 내 생각에는 시작하기 전에 잡생각이 많으니까 선뜻 시작하기가 힘들다. 이젠 뭐 할때 무지성으로 해야겠다. 그냥 무식하게 시작하고나서 필요한 것이 생기면 천천히 모아나가는 방식으로 해야겠다. 그리고 일기를 쓰는 이유가 하루하루 반성하라고 쓰는 건데 그냥 글만 쓰고 반성은 안한다. 오늘 자기전에 내 일기를 한번 읽어봐야겠다.

오늘은 게임 자체를 끊는 걸로 이번달 목표를 바꿔야겠다. 너무 심한 것 같다. 차라리 게임을 하고 싶으면 체스나 바둑, 마작같이 머리쓰는 게임이라도 하는게 좋을 것 같다. 스팀도 지웠다. 차마 탈퇴하기에는 너무 돈을 많이 써서 못하겠다. 오늘부터 게임 끝! 절대 접속 안한다. 스팀 절대로 다시 안깔아

오늘 참 부끄러운 일이 있었다. 나는 항상 나보다 지식이 없는 사람을 경시하며 지식이 많은 사람은 경외시하는 경우가 많다. 대놓고 무시하지는 않지만 나보다 지식이 없다고 생각하면 먼저 의심하는 경우가 많다. 내가 대학을 다니면서 알았던 사람 중에 나를 무시했던 사람이 있었고 나는 무시를 당한 적이 있었다. 그때는 상대에게 나는 네가 생각하는 것보다 많이 안다는 걸 알려주었다. 상대도 그걸 인정했다. 그런 내가 지식으로 한 사람의 인격을 판별하는 짓을 했다. 이번에 그 사람과 같이 게임을 하면서 여러가지 이야기를 들었다. 일부러 통계 얘기하고 경제가 어쩌고 사회가 어쩌고 하는 것을 들을 때 솔직히 보기 안좋아보였다. 어떤 문제에 대해 토론을 한다기 보다는 마치 자기 지식을 뽐내는 듯한 느낌이 들었다. 현학..