Hoguz

어느덧 벌서 5장, 총 8장까지인데 어느덧 중반을 향하고 있다.

탐색트리는 앞서 했던 트리의 자료구조의 일종이다.

트리 + 이진 탐색을 접목 시킨 구조라 볼 수 있다.

1. 이진탐색(binary Search)

탐색을 하는 방법이다.

기존의 선형구조의 경우 원하는 원소를 찾기 위해선 순차로 검색해야했고

이럴 경우 O(n)의 시간이 소요,

그렇기에 이걸 반씩 나눠 찾자 라는 개념.

즉 1-10까지 있을때 10을 찾기 위해선 10번 해야할껄

5 - 7 - 9 - 10 이런식으로 단축해서 찾을 수 있다.

2. 이진탐색트리

이진탐색의 방법을 트리로 적용 시켜서 만든것.

단순 연결리스트의 중간의 레퍼런스 연결을 바꾸고,

이걸 반복하고.. 말로는 설명하기어렵다.

이진탐색트리의 경우

노드 기준 왼쪽노드 들은 해당 노드보다 작아야 하고 오른쪽은 커야한다.

50

   80

 10 90

위 트리는 10 때문에 안된다. 50보다는 커야하기 때문.

3. 코드

3.1 탐색연산

기본 컨셉은 찾는값(k)과 루트 비교 -> k가 루트보다 크면 오른쪽으로

k가 루트보다 작으면 왼쪽으로,

이 방법을 재귀로 계속...

# self는 클래스 안에 만든 함수라 들어가있다.

def get(self, k):

 return self.get_item(self.root, k)

def get_item(self, n, k):

if n == None: # 루트에 아무것도 없다면 -> 찾는게 없다

return None

if n.key > k : # 찾는값이 작으니 왼쪽으로

return self.get_item(n.left, k)

elif n.key < k: # 찾는값이 크니 오른쪽으로

return self.get_item(n.right, k)

else:

return n.value

어려운 코드는 아니다.

3.2 삽입연산

탐색연산과 유사하지만 return이 다르다.

여기서 상당히 해맸는데, 재귀함수를 사용하는 이유와 결과를 잘 이해해야 한다.

재귀함수는 결국 큰 것을 작은 부분으로 나누어 이해하기 위함이라는 사실을 인지하고 들어가자

def put(self, key, value):

self.root = self.put_item(self.root, key, value)

# 위에 코드와 비교하면 얘는 return을 안하고 self.root, 즉 루트값을 받게끔 되어있다.

def put_item(self,n, key, value):

if n == None:

return Node(key, value) # 결국 아무것도 없는 곳 까지 갔을때 node를 삽입한다. 근데 여기서 끝이 아니다. 이 return 값이 위로 쭉쭉 올라가야한다

if n.key > key:

n.left = self.put_item(n.left, key, value)

elif n.key < key:

n.right = self.put_item(n.right, key, value)

else:

n.value = value

return n

30

20      40

10      25

여기서 5를 넣는다고 하면 얘는 10의 왼쪽으로 가야한다.

재귀적으로 볼때 새로운 값, 10이 하나의 서브트리로 완성 되야하고 이 서브트리를 왼쪽 노드, 25, 20 을 원소로 하는 서브트리가 또 완성되어야 한다.

그리고 이 서브트리는 결국 30, 40으로 이루어진 트리가 되어야한다.

그렇기때문에 값을 넣고(return Node) 한 후에 계속 해서 올라가서 결국은 return n을 해줘야한다...

이거는 직접 코드를 손으로 써본다음에 선 그으면서 봐야한다..

3.3 삭제연산

제일 생각할 것도 많고, 코드도 길고.. 그렇다 암튼.

3가지의 경우의 수가 있다.

우선 삭제할 노드를 n 이라 칭하겠다.

첫번째 : n이 자식이 없을 경우

=> n의 부모노드의 자식을 None으로 만든다

두번째 : n의 자식이 하나만 있을경우

=> n의 부모노드와 n의 자식을 직접 연결한다

세번재 :  n의 자식이 많을 경우..

=> n의 자시에서 중위순회하면서 n을 방문한 직후 방문하는 노드를 n의 자리로 옮긴다

=> 이진탐색에서 n 기준 왼쪽자식은 n보다 작고 오른쪽 자식은 n보다 크다.

그렇기에 n이 삭제되면 그 다음으로 큰 n의 오른쪽 자식이 와야한다.(n보다 큰 다음 노드가 와야 한다는 뜻)

코드는 다음과 같다.

def delete(self, k):

self.root = self.del_node(self.root, k)

def del_noe(self, n, k):

if n == None:

return None

if n.key > k:

n.left = self.del_node(n.left, k)

elif n.key < k:

n.right = self.del_node(n.right, k)

# 여기까지의 코드는 k를 찾으러 가기 위한 과정이다.

else:

if n.right == None:

return n.left;

if n.left == None:

return n.right;

# 위의 코드는 첫번째 경우, 자식이 없을때

target = n #1번

n = self.minimum(target.right) #2번

n.right = self.del_min(target.right) #3번

n.left = target.left #4번

return n

target부분부터 설명을 하자면.

우리는 자식이 많은 노드를 삭제하는 경우를 생각해야한다.

여기서도 이진 탐색트리의 특성을 꼭 기억해야하는데

왼쪽 자식은 작고 오른쪽 자식은 크다는 것이다.

즉 내가 삭제 되더라도 나를 대체할 애를 뎃구와야하고

뎃구 오는 애는 오른쪽 아이들, 그리고 그 아이들에서도 제일 작은 애를 부모로 해야 정렬이 알아서 된다. 그리고 작은 자식을 뎃구 왔으면 당연히 그 친구를 삭제해주고..

그렇기에 #2번을 보면 지우려는 노드의 오른쪽 자식들 중 가장 작은 애를 고른다.

(minumum이란 함수가 있다.. 위에서 작성 안함...ㅠ)

그리고 그 고른 애들 지워준다(#3번), 이때!! 이러한 결과는 노드의 오른쪽에서 이뤄지므로 n.right로 받아준다!!(#3번)

그리고 왼쪽애들을 그대로 붙여준다(#4번)

다시 정리하자면

1. 삭제 전 오른쪽 자식들 중에서 제일 작은 값 선정

2. 제일 작은 값 삭제

3. 오른쪽, 왼쪽 연결

이렇게 된다..

- 리스트의 경우 삽입, 삭제 후에도 정렬 상태를 유지해야 하므로 O(N)시간이 소요

- 이러한 문제점을 보완한 자료구조가 트리 구조

- 트리는 일반적 트리, 이진트리로 구분

- 이진트리는 탐색트리, heap자료구조, 구문트리(syntax Tree)로 구분

- 트리의 용어는 Root, child, Degree(count of child), parent, leaf(no child), Sibling, Ancestor, Descendant, Subtree, Level, Height, Key로 구성

- leaf의 경우 Terminal or External 이라 불리며 leaf가 아닌 노드를 internal or Non-Terminal 라고 불린다.

- 용어에 대한 확실한 이해가 없으면 차후 공부할때 많이 힘들므로 용어는 꼭 외우는 것이 좋다

- 최대 차수가 k인 트리에 n개의 노드가 있다면 none 레퍼런스 수는 nk - (n-1) = n(k-1) + 1 이다

- 즉 아이들이 최대 k개인 노드가 있다면 

- 일반적인 이진트리는 왼쪽 자식, 오른쪽 형제 순으로 key를 구성한다.

- 이진트리의 정의는 각 노드의 자식수가 2 이하인 트리이다. 즉 자식이 2, 1 또는 없을수도(이때의 경우는 leaf) 이다

- 이진트리는 널리 활용된다.

- 이진트리의 경우 포화이진트리, 완전 이진트리, 두가지가 있다.

- 포화이진트리란 모든 이파리의 깊이가 같고 각 내부노드가 2개의 자식노드를 가지는 트리이다

- 완전이진트리란 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리이다.

(레벨은 곧 높이, 즉 4레벨의 트리라면 3레벨까지는 포화이진트리로 구성되어있고 마지막 4레벨의 노드들의 경우 왼쪽부터 채워진 트리)

- 레벨 k에 있는 최대 노드 수는 2^(K-1) 이다.( 3레벨의 경우 최대 4개의 노드가 있을 수 있다)

- 레벨 k인 이진트리의 최대 노드 수는 2^H -1 이다

챕터3은 스택, 큐, 데크 구조를 설명한 챕터이다.

스택은 뒤로만 값이 들어오고 뒤로 나가며

큐는 앞으로 나가고 뒤로 들어오고

데크는 앞뒤 전부 다 되고..

문제는 보통 스택에서 많이 나왔다.

자바 컴파일러가 syntax에러를 찾는 원리 역시 스택이고

후위표기법 역시 스택이고... 

3.6 부터 3.11 까지는 모두 스택 경우의 수를 따지는 문제이다.

수기로 일일히 찾아해보는 것이 좋다.

3.17 괄호 짝맞추기 프로그램 작성

이는 기본 스택의 원리 + 컴파일러 문법에러 찾기 문제인데

이번엔 중괄호, 소괄호 두개를 구분해야 하는게 붙었다.

def test(lst):

 # { = 123 , } = 125, (  = 40, ) = 41

 # 따라서 짝이 맞다면 두 값의 차는 

 numlst = []

 for i in lst:

  num = ord(i);

  if num == 123 or num == 40:

   numlst.append(num)

  else:

   chnum = numlst.pop();

   k = chnum - num 

   if k != -2 or k != -1  :

    return 'false lst';

 if len(numlst) != 0:

  return 'no lst';

 return 'ok lst'

문자열로 바로 확인하는 방법이 아닌 아스키 코드값으로 확인하고 짝맞추는 경우엔 두 값의 차로 계산을 해봤다. 하지만 이 경우 ) } 이런식으로 바로 닫히는 괄호가 나오면 찾지를 못했다..

3.18 회문을 검사하는 프로그램 작성

회문이란 abba 이런식으로 문자가 짝지어지는 것을 뜻한다. 데칼코마니처럼

위에 괄호 맞추는 것과 같은 원리로 하면 된다.

def checkstr(str):

 lst = list(str)

 chenum = len(lst) / 2;

 elst = []

 for i in lst:

  if len(elst) == 0:

   elst.append(i)

   k = elst[-1];

  elif k == i:

   elst.pop();

   if len(elst) == 0:

    continue;

   else:

    k = elst[-1];

  elif k != i:

   elst.append(i)

   k = elst[-1];

 if len(elst) != 0 :

  return 'false str'

 return 'ok str'   

17, 18번 원리는 다음과 같다

일단 빈 스택 리스트에 값을 하나한 집어 넣다가 같은 문자가 왔을 경우 (또는 닫히는 같은 종류의 괄호가 올경우) pop으로 스택 리스트에서 제거 해준다.

이런식으로 끝까지 반복했다면 제일 마지막에는 빈 스택리스트가 나와야한다.

만약 무언가가 남아있다면 이는 짝이 없다는 것.

3.20 후위표기법의 식을 계산하는 프로그램 작성

우리가 보통 사용하는 식은 중위표기법이다

1 + 2 + 3 이렇게.. 보기도 좋다.

후위표기법이란 12+3+ 이렇게 표현한다

이러한 식을 계산 하는 것도

결국 빈 스택 리스트에 값을 넣되 만약 사칙연산이 들어오면 그 앞서 있던 두개의 값들을 계산 해주면 된다.(식은 기본적으로 2개의 숫자와 1개의 연산자로 구성되므로 가장 짧은 후위표기식도 최소 2개의 숫자가 저장되어야한다)

1 2 + 일 경우엔  (1+2 계산 한 값)을 다시 스택에 집어 넣는다.

이런식...

def reverse_(for_lst):

 lst = []

 for i in for_lst:

  if isinstance(i, int):

   lst.append(i);

  elif i == '+':

   k = lst.pop() + lst.pop();

   lst.append(k)

   continue;

  elif i == '-':

   k = lst.pop() - lst.pop();

   lst.append(k);

   continue;

  elif i == '*':

   k = lst.pop() * lst.pop();

   lst.append(k);

   continue;

  elif i == '/':

   k = lst.pop() // lst.pop();

   lst.append(k);

   continue;

 return lst

괄호인 경우 까지 생각 못했다...

3.23 오늘 생각했던 문제중 가장 뿌듯했기도 하면서 어려웠던 문제..

이거때문에 아래는 생각도 못했다. 얘도 역시 괄호 버젼은 풀지도 못했다.

문제는 중위표기법을 후위표기법으로 바꾸는 코드를 짜시오 이다.

1 + 2 + 3 을 12+3+ 이렇게 바꿔야한다.

크게 스택 리스트를 두개 만들어서 하나는 숫자, 하나는 연산자만 담게 한다.

여기서 연산자 리스트에 조건이 3개가 갈린다.

위의 1+2+3의 예시는 간단하지만

만약 1 + 2 * 3 이라면? 사칙연산 때문에 123*+ 가 된다.

즉 * , / 때문에 고민을 한번 더 해야한다.

그렇기에 만든 조건은 다음과 같다(feat 승완군..

0. +,- 와 *, / 를 서로 다른 가중치를 두어 구분한다.

나의 경우 +,- 는 1로, * , / 는 2로 구분지었다.

0. 항상 연산자 리스트에 있는 요소가 무엇인지 확인한다.

그리고 새로 들어오는 값을 비교한다

1. + 가 있을 경우에 +와 같은 가중치 값이 연산자 리스트로 들어온다면 

기존에 있던 +를 숫자 리스트로 보내버린 후 새 값을 연산자 리스트에 넣는다.

즉 1 + 2 - 3 의 경우

숫자 리스트 : 1,2

연산자 리스트 + 인 상황에서 -가 들어올때 1의 조건에 걸리므로

숫자: 1,2,+

연산자 : -

이렇게 저장이 된다.

2. +가 있을 경우에 + 보다 가중치 값이 큰 연산자가 들어온다면 연산자 리스트에 그대로 쌓는다.

즉 1 + 2 * 3 의 경우

숫자 : 1 2

연산자: + 인 상황에서 *가 들어와야 한다.

2의 조건에 걸리므로

숫자 : 1,2

연산자 : +, * 가 된다.

3. 만약 가중치가 작은 값이 새로 들어온다면? 즉 *, /가 있는 상황에서+, -가 들어온다면 기존에 있던 애들을 모두 숫자로 보낸 후 새로 들어오는 값을 연산자에 넣어준다.

즉 1+ 2 * 3 -4 인 경우

숫자: 12

연산자: +* 인 상황에서 - 가 들어와야 한다.

3의 조건에 걸리므로

숫자: 12*+(+,*를 pop()으로 뽑아서 *,+ 로 들어왔다)

연산자 - 가 된다

그리고 모두 다 돌아가면 연산자 리스트에 있는 애들을 전부 숫자로 옮겨주면 된다.

def make_for2(lst):

 chlst = {'+' : 1, '-': 1,'*':2, '/':2}

 str_lst = []

 op_lst = []

 for i in lst:

  if isinstance(i, int):

   str_lst.append(i)

   if i == lst[-1]: # 모두 다 돌아갔을때, 즉 마지막 값이 숫자일 경우를 뜻한다.

    num = len(op_lst)

    for n in range(num):

     str_lst.append(op_lst.pop())

   continue;

  else:

   if len(op_lst) == 0:

    op_lst.append(i);

   elif chlst[i] == chlst[op_lst[-1]]: # 키 값이 같으면

    str_lst.append(op_lst.pop())

    op_lst.append(i)

    continue;

   elif chlst[i] > chlst[op_lst[-1]]: # 새로 들어오는게 기존보다 크면

    op_lst.append(i) # 연산자 스택에 쌓는다

    continue;

   elif chlst[i] < chlst[op_lst[-1]]: # 새로 들어오는게 나보다 작으면

    # 새로 들어오는 것을 산술 스택에 쌓고 그 이전에 있던 애도 산술 스택에 쌓는다

    num = len(op_lst)

    for n in range(num):

     str_lst.append(op_lst.pop())

    op_lst.append(i);

 return str_lst;

물론 위 경우는 아직 괄호를 고려하지 않은 경우이다.

괄호 경우도 구상은 해놨는데 아직 코드화를 못했다.

스택 문제를 다 푼것은 아니지만 스택의 꽃은 후위표기법이라 생각한다.

생각보다 재밌다.

풀어본 결과를 올리는 것일뿐, 정답은 아니라는점... 주륵..

2.7 각각 정렬되어 있는 2개의 단순 연결리스트를 하나의 정렬된 단순연결리스트로 만드는 함수를 작성하시오

(이하 함수는 clsss안에서 만듬)

def add_two(self, slst):

sh = slst.head

fh = self.head

while sh != None:

if fh.item >sh.item:

self.insert_front(sh.item);

sh = sh.next

else:

fh = fh.next

continue;

1. 외부서 리스트를 받는다.

2. 각 리스트의 헤드를 초기화

3.여기서 기준이 될 리스트를 정해준다, 여기선 fh가 기준

원리는 fh, sh를 비교하고 fh보다 작으면 앞에다 넣고

sh를 옆으로 옮긴다. fh는 옮기지 않는다

4. 3이 아닐 경우 기준을 옮겨준다.

node와 item이 좀 헷갈림..

2.10

각 노드에 1개의 정수가 저장된 단순연결리스트와 정수 k가 주어질때 이 단순연결리스트를 하나는 k와 같거나 작은 정수를 가진 연결리스트로, 다른 하나는 k보다 큰 정수를 가진 노드들로만 구성된 연결 리스트로 분리하는 함수를 작성하시오

def seperate(self, k):

s = tdlist();

m = tdlist();

num = 0;

dh = self.head;

while num < self.size:

if dh.item < k:

s.insert_front(dh.item);

dh = dh.next;

num += 1;

elif dh.item >= k:

m.insert_front(dh.item)

dh = dh.next;

num += 1;

elif dh == None:

break;

return(s, m)

1. 두개의 클래스를 만든다. 값을 나눠야 하니까..

2. num은 while의 플래그로 횟수를 카운트 한다.

즉 처음 단순연결리스트의 사이즈 횟수만큼 돌아간다

3. 해당 아이템이 지정된 수 보다 작으면 s, 크거나 같으면 m에 넣는다

여기서도 헷갈리는 부분으 dh와 dh.item, 

None은 노드 값이라 dh.item이 아닌 dh와 비교해야하는 듯