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가 변경을 위해서 기존의 함수가 저장되는 것.

아니아니 이 말도 어렵다. 

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

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

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

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

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

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

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