Simple in Complex with Simple

1. 개요

 BST 알고리즘은 쉬움.

 부모 노드를 기준으로 좌측엔 부모 노드보다 작은 데이터, 우측엔 부모 노드보다 큰 데이터 삽입. (반드시 만족해야 함)

 가장 오른쪽 노드의 데이터가 최대 크기.

 가장 왼쪽 노드의 데이터가 최소 크기. 

 이진 탐색 트리를 중위 순행하면 정렬 리스트를 생성할 수 있음. (작은->중간->큰 순으로 운행)

 BST는 삽입, 삭제, 데이터 검색, 최소 데이터 검색, 최대 데이터 검색 5가지 기본 연산 존재.

 모든 검색은 O(n)에 움직임.

 왜냐하면 BST의 좌,우측 트리 높이 차이는 0~n까지 있을 수 있기 때문에 O(n)이 된다.

 이를 균형 맞추기 위해 나타난 트리가 Balanced BST이다. 대표적으로 AVL Tree가 있다.

 AVL Tree는 좌,우측 트리 높이 차이가 1이하이다. 즉, 최대 높이가 BST보다 반으로 줄기에 검색 시간 O(logn).

 BST에 응용 가능한 수 많은 알고리즘들이 존재.

 기억해야 할 것

 삭제 알고리즘

 (1) Leaf 노드 (자식 노드가 없는 경우) 삭제할 때

 (2) Half 노드 (자식 노드가 하나만 있는 경우) 삭제할 때

 (3) Full 노드 (자식 노드가 두 개 있을 경우) 삭제할 때

 경우를 잘 생각하고 처리해야 한다. 이게 BST의 전부.

2. 문제

 데이터 10, 100, 500 범위 안에서 랜덤으로 데이터를 입력받고 이를 BST에 삽입했다 삭제하는 알고리즘 작성하시오.

3. 출력

3-1) 구조체 및 함수 선언

3-2) 메인

3-3) BST 삽입 알고리즘

3-4) BST 삭제 알고리즘

3-5) 검색, 최소, 최대 구하기 알고리즘

3-6) 데이터 크기 10,100,500에 따른 출력 (데이터는 범위 안에서 랜덤 삽입함)

4. 정리

 이번 BST는 정말 하루만에 뚝딱 올리고 싶었지만 예기치 않은 문제로 인해서 일주일이나 걸려버렸다.

 왜냐하면 원래 내가 알고있는 방식으로 풀었다면 바로 올릴 수 있었겠지만 그에 따른 코드양이 너무 많았다.

 그래서 기존에 배운 방식이 아닌 스승님이 제시해 준 이 방식으로 풀어보고 싶었다. 하지만 스승님은 역시나

 완성된 코드가 아닌 슈도 코드만 올려놓으셨고 이거 분석하고 코드량을 대폭 줄이기 위해 연구하느라 시간이

 오래 걸렸다. 그 와중에 리켜전에 대해 새로운 느낌을 잡았으니 만족한다. 이해가 되지 않던 것들을 하나씩

 부서나갈 때마다 성장하는게 느껴진다. 좋다.

 기억해야 할 것.

 내가 알던 낡은 방법은 삭제 노드를 찾으면 바로 그에 따른 처리를 한다.

 새로운 방법은 삭제 노드를 찾으면 데이터 갱신만 하고 다시 중복된 갱신 데이터를 삭제하도록 한다. (속도도 괜찮다.)

1. 개요

요즘들어 알고리즘을 작성하면서 어떻게하면 코드를 좀 더 줄일 수 있는지 생각하다보니 알고리즘 작성을 못하고 있다.

기존의 내가 배웠던 방법으로 풀어내면 금방이겠지만, 이런식으로는 도저히 정말 사용할 수 있는 수준의 성능이 안나온다.

왜 리커젼을 쓰는지 왜 다이나믹 프로그래밍을 사용하는지 알아내야한다.

그렇게 몇 일을 고민하다가 불쑥 내가 착각하고 있는 게 무엇인지 알아냈다.

내게 있어 리커젼이란 무척이나 어려운 것이었다.

오래 전, 프로그래밍을 포기했을 때 정말 이해가 가지 않았던 원리이기 때문에 이것을 이해하려면 뭐 엄청난 생각의 방법이나

논리가 필요한 줄 알았다. 그런데 아니었다.

그리고 다시 프로그래밍을 시작하면서 리커젼을 작성해봤다. 하지만 이미 연습해본 것이나 작성할 수 있을 뿐, 정말 새로운 것

에 대해서 리커젼을 작성할 자신이 없었다. 뭐랄까 계속 한 곳으로 파고들어가는 그 과정이 머릿속에서 뚜렷하게 안 그려진다

고 해야할까. 그러다 한 책에서 만난 리커젼의 토대. 저번에 올렸던 포스팅에서 나타난 리커젼의 기본 뼈대.

 if ( 종료 조건 )

return 종료 값

 else if ( 또 다른 종료 조건 )

return 또 다른 종료 값

 else

return ( 몇 가지 작업 ) and then ( 재귀 호출 )

모든 리커젼은 이 형태에서 출발한다라는 것.

그것을 알았을 때, 뭔가 조금 더 머릿속에서 리커젼에 대한 개념이 잡힐듯 말듯 했지만 뚜렷하게 구상되지는 않았다.

근데 이번에 음 꿈 속에서 리커젼때문에 고민하는 내 모습이 보였는데... 음

결국 리커젼도 반복의 일종이었다.

뭐 거창한 개요에 비하면 참 간단한 사실인데, 내가 정말 제대로 알게된 것은 

반복문이 단지 변수 하나를 단순히 Index 삼아 움직이는 코드라면, 

리커젼도 단지 똑같은 반복이다. 다만 그 Index가 변경을 위해서 기존의 함수가 저장되는 것.

아니아니 이 말도 어렵다. 

그러니까 리커젼도 결국은 출발지에서 어떤 목적지를 향해가는 선형 반복이라는 것이다.

단지 그 선형 반복을 위해 메모리 오버헤드가 크다는 것? 뿐이라는 것이다.

아직도 뭐 완벽히 이것이 이렇고 저것이 저렇다 말은 못하겠지만, 결국 정말로 알게된 것은 이렇다.

머릿속에 트라우마처럼 이것은 어렵다, 어려워서 풀기가 어렵다 한 문제들을 풀어내기 위해 필요한 방법은

어렵고, 거창한 방법론이 아니라 (내 수준의 문제에서는) 단순한 관념으로 풀 수 있다는 것이다.

내 블로그 제목처럼 뭔가 단순한게 모여서 복잡한 것을 이루고 결국 그것도 단순한 형태의 한 뼈대이다.

그러니 최선을 다해 궁리하고 풀어보자. 

(사진 펌) 사진 및 출처에 관한 사항은 연락주시면 바로 삭제하겠습니다.

내가 부른 - 이 밤이 지나기 전에

진짜 녹음해서 듣는 내 목소리는 언제나 이상하다.

그래도 스스로 제일 들어줄 만하게 나온거 같아서 훗날 추억할 겸 이곳에 올린다. (물론 엄청 웃기지만)

오늘 하루 몸이 쳐졌다.

침대에서 움직이고 싶지 않았고 일어나기가 싫다.

나태해져버린 생각과 몸.

하지만 시간은 언제나 기다려주지 않고 흐른다.

억지로 달래 다시 공부하러 왔다.

좋다.

역시 뭔가 하고 있으니 소소한 행복이 느껴진다.

어제는 정말 오랜만에 친구들과 잔디밭에 누어서

놀았다.

그렇게 따사로운 햇살 받으면서 그늘에 누어 얘기하는 게

너무 오랜만이라 정말 좋았다.

유럽여행 기념품으로 받은 오르골의 손잡이를 돌리면

오르골의 톡톡 튀는 부분이 부딪히는 느낌이 손가락으로 전해진다.

그러면서 동시에 내 머리속에도 옛 추억이 하나씩 톡톡 튀어오른다.

물론 아주 잠깐 잠깐의 스치는 사념에 불과하지만

그 느낌이 좋다.

나중에 오르골을 많이 모아서 여러개를 연결해서 뭔가 거대하면서 

풍부한 소리를 가진 오르골을 하나 만들어보고 싶다.

요즘들어 별로 생각이없다.

너무 복잡하게 살았나보다.

생각이 없는게 좋다.

예전에는 항상 몸에서 흐르던 활기가

요즘들어 다시 흐르고 있는게 느껴진다.

너무 늙게 살았다.

젊게 살걸.

이 느낌을 오래도록 잃어버리고 싶지 않다.

뭔가를 해도 다 될 것 같은 느낌.

아직 20대다.

끝에가서 조금씩 사그라드는 20대가 아니라

끝에서 오히려 더 활활 타오르는 그런 20대를 보내자.

언제나 삶을 비추는 별빛처럼.