지난번에 마무리 못했던 탐색트리 뒷 이야기. 

1. AVL 트리

2. 2-3트리, 레드블랙트리

3.B-트리 등

복습

이진탐색트리

- 이진 탐색 개념을 트리 형태에 접목시킨 자료구조.

- 삽입, 삭제 역시 이진 탐색을 바탕으로 진행된다.

(왼쪽, 오른쪽으로 들어가기만 하면 된다)

1. AVL 트리

- 이진탐색트리를 발전 시킨 개념이다.

- 기존의 이진탐색은 값을 나누기만 할뿐 모양에 대한 고려가 없다. 즉 한쪽으로 치우치는 트릭 나올 수 있음

- 그렇기에 AVL 트리는 balence를 통해 트리의 균형을 잡는다.

- 정의 : 임의의 노드 n에 대하여 n의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리.

- 위의 조건 때문에 AVL 트리의 높이는 피보나치 점화식으로 계산 가능.

- 균형을 위해 회전 연산을 한다.

위는 오른쪽으로 균형을 맞추는 코드의 예시

def rotate_right(self, n):

x = n.left

n.left = x.right

x.right = n

n.height = max(self.height(n.left), self.height(n.right)) + 1

x.height = max(self.height(n.left), self.height(x.right)) + 1

return x

위 그림에서는 return x를 표시 안했는데 무조건 return x를 해줘야 루트가 x로 바뀐다.

- left도 마찬가지..

- AVL 트리는 삽입 후 서브트리의 차를 바탕으로 1보다 크면 왼쪽으로 회전을, 1보다 작으면 오른쪽으로 회전을 시켜준다

2. 2-3트리, 레드블랙트리

2.1) 2-3트리

- 차수(자식)이 2인 노드가 2-노드, 차수가 3인 노드가 3-노드 라 부른다

- 모든 이파리가 동일한 층에 있어야 한다.

- 그렇기에 2-3트리는 포화이진트리이다

2.2) 레드블랙트리

- 노드의 색을 부여해서 트리의 균형을 유지한다.

- AVL 트리의 경우 알고리즘을 통해 규형을 유지한다면 레드블랙은 이러한 알고리즘을 색이라는 제약조건을 통해 구현한다.

- 책에 나와있는 것은 좌편향 레드블랙트리(좀더 단순화된 버젼인듯)

- 루트와 None은 블랙

- 루트로부터 각 None 까지 2개의 연속된 레드 link는 없다

- 루트로부터 각 None까지의 경로에 있는 블랙 link 수는 모두 같다

- 레드 link는 왼쪽으로 기울어져있다

- 이러한 조건을 통해 균형을 유지한다.

3. B-트리

- 다방향 탐색이 가능한 완전 균형 트리..

- 다양한 DBMS 시스템의 기본 자료구조로 활용된다고 한다..

- 어렵다...

5월 17일

no_continuous함수는 스트링 s를 매개변수로 입력받습니다.

s의 글자들의 순서를 유지하면서, 글자들 중 연속적으로 나타나는 아이템은 제거된 배열(파이썬은 list)을 리턴하도록 함수를 완성하세요. 예를들어 다음과 같이 동작하면 됩니다.

s가 '133303'이라면 ['1', '3', '0', '3']를 리턴 s가 '47330'이라면 [4, 7, 3, 0]을 리턴

위에 처럼 코드를 썻는데,

항상 파이썬 할때 헷갈리는건 매개인자가 "" 인 경우 str이어도 list로 처리 가능?!

그래서 굳이 list로 변환 해줄 필요가 없다.

연속되는 두개만 확인하면 되기에 for문을 돌면서 i, i+1을 비교했다.

이런 문제 풀때마다 느끼는 거는 list out of range문제 ㅡ,.ㅡ 그래서 종료 조건도 추가..

고수 정답:(드래그 하면 보임)
[s[i] for i in range(len(s)) if s[i] != s[i+1:i+2]]

놀라울 뿐이다. 저렇게 인덱싱 하는게 대단함.

5월 18일 금요일

getMiddle메소드는 하나의 단어를 입력 받습니다. 단어를 입력 받아서 가운데 글자를 반환하도록 getMiddle메소드를 만들어 보세요. 단어의 길이가 짝수일경우 가운데 두글자를 반환하면 됩니다. 예를들어 입력받은 단어가 power이라면 w를 반환하면 되고, 입력받은 단어가 test라면 es를 반환하면 됩니다.

이 역시 크기 계산 후 짝수, 홀수에 따라서 i, i+1로 리턴.

최대한 람다를 활용하려고 노력함.

람다식으로 변환 계속 해보려 노력중.

한가지 알게 된 점은 위에 처럼 코드를 치면 쟤는 람다 함수가 되서 return에 함수처럼 인자를 직접 넣어줘야한다 

8장 연습문제. 약 30여개 문제가 있음.

너무 단순하거나 간단히 풀수 있는 것을 제외하고 기록함.

8.10 N개의 정점을 가진 무방향 그래프 G에 대해 다음의 설명중 맞는 것만 모아놓은 것은?

1) G의 각 쌍의 정점 사이에는 1개의 경로만 존재하면 G는 트리이다

2) G가 하나의 연결성분으로 되어있고 N-1개의 간선을 가지면 G는 트리이다.

3) G가 N-1개의 간선을 가지면서 싸이클이 없으면 G는 트리이다.

용어를 정확히 이해하지 않고 풀면 많이 헷갈린다.

1) 트리란 1개 이상의 노드를 갖는 집합이다. 그렇기에 각 쌍의 정점 사이의 한개의 경로, 즉 최소 2개의 노드로 구성되어진 G는

트리이다.

2) 연결성분이란 최대로 연결된 부분의 그래프.

G가 하나의 연결성분을 가진다고 하였으므로 모든 정점들이 연결되어있다.

그런데 모든 정점을 연결하면서 간선이 N-1개란 뜻은 싸이클을 완성 할 수 없다는 뜻이다.

예를들어 5개의 정점을 하나의 연결성분으로 하면서 싸이클을 만들려면 5개의 간선이 필요로 하다.

(중간에 다른 방향을 통해서 3개의 싸이클을 만든다고 할 경우 하나의 연결성분이라는 조건을 충족 못함)

그렇기에 G는 트리라고 할 수 있다

3) 2에서의 설명을 다르게 바꾼 것. 

8.18 Kruskal 알고리즘과 Prim 알고리즘을 비교한 것 중 가장 적절하게 설명한 것을 고르시오.

이 문제에서 짚고 넘어가야 하는 부분은 그리디 알고리즘과 동적계획 알고리즘이다.

그리디 알고리즘 : 탐욕 알고리즘 이라한다. 처음엔 탐욕이라길래 뭔가 많이 가져가는거가 목표인가 라고 생각했으나

그게 아님.. 그래서 개인적으론 이기적이다 라고 이해하고 있다.

그리디 알고리즘은 쉽게 생각하면 근시안적으로 보는 것이다. 바로 3개 초콜릿, 1분뒤 10개 초콜릿 을 준다고 했을 경우

바로 3개의 초콜릿을 선택하는 것, 그것이 그리디 하다 할 수 있다(탐욕적이니까)

동적 계획법은 위와는 살짝 다르다.

얘는 조금 생각을 한다. 큰 맥락이 아닌 부분에 대한 이해를 바탕으로 최선을 고려하고 이를 통해 전체의 해답을 얻는다.

(작성중)

http://taewan.kim/post/numpy_cheat_sheet/

(추천 사이트)

차후에 정리를 위해서라도 남기는.

import numpy as np

파이썬 라이브러리 중 계산을 위한 필요 라이브러리. scipy랑 잘 사용.

다만 배워놓고 생각보다 많이 쓰지 않았음.

1. 리스트 만들기

np.array

np.arange(num)

두개다 리스트를 만들어 준다. 간편하게 만들 수 있어서 좋다.

2. 배열 연결 : 행이나 열을 연결할때 사용. 판다스에서 concat과 비슷.

np.hstack : 가로로 연결

np.vstack : 세로로 연결

np.dstack : 음... 차원이 새롭게 생긴다. 허허...

3.np.where(data 조건, true, false)

넘파이 하면서 첨 본듯.

삼항연산자이다. 조건을 주고 true일시, false일시의 값들을 정하면 된다.

np.where(lst > 10, 99, 88)

lst의 요소들이 10보다 크면 99로, 아니면 88로 

np.where(lst > 10, 99, lst)

lst요소들이 10보다 크면 99, 아니면 lst(그냥 둬라)

#번외 List Comprehension

for문을 한줄로 사용.

첨엔 헷갈리는데 익숙해지면 편한듯

for x in range(num):

print (x)

-> [x for x in range(num)] , 물론 얘는 리스트 이다.(위는 단순 출력)

 [[x + k*10+50*(i-1) for k in range(5)]  for i in range(1,4)]

이중 for문 형식으로도 사용 가능.

시간날때 천천히 개념 복습.

기본부터 충실히.

1) 객체 지향 언어.

- 가상세계의 현실화

- 현실에서의 상호작용의 주체를 객체(Object)로 이해한다.

예) 자판기에서 물건을 사는 고객이 있다고 할때 이를 

자판기(돈, 제품)

-메서드 : 돈을 받기, 검사하기, 잔돈주기, 제품주기

고객(돈, 제품)

-메서드 : 돈 넣기, 돈 받기, 제품받기 

등으로 쪼개어 이해한다.

- 모듈식으로 구성되므로 코드를 이해하고 유지하고 보수하는데 매우 용이하다.

이를 위해 추상화, 캡슐화 등이 있음(차후 설명)

* 그런데 객체지향의 반대를 절차지향이라 생각하는 것은 조금 위험한 발상 일 수도??

객체 지향이나 절차지향이나 결국 알고리즘, 데이터 플로우 대로 진행 된다. 그렇기에 객체지향과 절차지향을 서로 다르게 이해하는 것이 맞지, 무조건적으로 반대다 라곤 할 수 없다.

즉 절차지향은 프로그래므이 순서와 흐름이 먼저 고려한 후 자료구조와 함수들을 설계하는 방식이고, 객체지향은 자료구조와 함수를 설계한 후 실행순서와 흐름을 짜는 방식으로 이해

# 파이썬 -> 자바-> C언어 순으로 접하다 보니 확실히 모듈식으로 코드를 구성하는 것이 편하고 당연시 여겨진다.

2) 오버로딩과 오버라이딩

2.1) 오버로딩

- 같은 이름의 메서드를 매개변수의 변화를 통해 정의 하는것

- 같은 메서드 이름을 갖고 있으나 매개변수의 개수 또는 타입이 달라야 한다.

- 오로지 매개변수에 의해서 구분이 되어진다.

- 같은 기능을 하지만 서로 다른 인자를 받는 함수를 사용할때 편하다. 

2.2) 오버라이딩

- 조상클래스로부터의 상속 내용을 내 입맛대로 변경하는 것.

- 단 이름, 매개변수, return 타입은 같다.

- tostring 바꿀때 많이 사용했다.

# 오버로딩과 인터페이스, 다시금 정리할 필요가 있다.

3 추상클래스

- 자체로 역할을 하는 클래스는 아니지만 상속을 통해 자손에게 능력을 주는 클래스? 이다.

- 즉 추상클래스를 코드로 구현 후 자손에게 상속한뒤 자손은 이를 '오버라이딩' 해야만 한다.

# 그런데 나는 아직 경험이 없어서 그런지 추상클래스의 필요성을 못느끼겠다. 클래스를 작성할때 조상까지 생각할 겨를도 없고

그럴 필요도 못느낀다. 일을 두배로 하는 느낌? 물론 설계단계에서 추상클래스부터 작성한다면 모르겠지만...

4. 인터페이스

- 얘 역시 다른 클래스에게 도움을 줄 목적으로 만들어진다.

- 추상클래스와의 다른 점은 모양, 생긴것.

- 추상클래스는 말 그대로 클래스이지만 추상적(역할 x)이다.

- 하지만 인터페이스는 오로지 상수 멤버와 추상메서드만을 갖는다.

- 또한 extends와 implements의 차이도 존재한다.

- 한개만 받느냐 여러개를 받느냐..

# 보통 mapper로 인터페이스를 만들어서 사용 했는데 스프링 프로젝트할때는 mapper를 xml로 작성하다보니 이 마저도 사용을 잘 안하게 됬다.

큰그림을 얼마나 보느냐에 따라서 위 두개 개념을 사용하고 안하고가 갈리는 듯 하다.

5. 다형성(polymorphis)

- 같은 모양이 다르개 사용 되는 것?

- 전화기의 키보드, 문자할때의 키보드, 게임할때의 키보드 등... 모양은 같은데 서로 다른 기능을 수행

- 여러가지 형태를 가질 수 있는 능력

- 한 타입의 참조변수로 여러타입의 객체를 참조할 수 있도록 함.

# OOP에서 매우 중요한 개념이긴 한데 오랫만에서 봐서 헷갈림.

다시 정리 필요..

원래는 다익스트라 먼저 나와야 하는데

그 부분이 아직 정리가 덜 됬다.

플로이드 마샬의 경우 기존에 우리가 해왔던 임의의 정점, 또는 한 정점으로 부터가 아닌

모든 정점에 대한 계산을 실시한다.

바꿔 말하자면 X에서 Y로의 경로에 N 노드를 거치는게 빠르냐 아니냐를 따지는 것이다.

그렇기에 

1. X->Y의 비용

2. X->N + N -> Y의 비용

이 두개의 비용을 비교하여 최소 비용으로 업데이트 한다.

(아래 내용은 동빈나님의 블로그를 필기한 것이다, https://blog.naver.com/ndb796/221234427842)

위를 코드로 구성하자면

D = 인접 리스트

for i in range(len(D):

for k in range(len(D)):

for j in range(len(D)):

D[i][k] = min(D[i][k], D[i][j] + D[j][k])

매우 간단한데 이해가 바로 오지는 않는다.

위에 예시에 D[2,3] 이 누구랑 비교 되는지 확인하면서 생각해야한다.

2번째, 프림 알고리즘

개념은 이해가 되는데 코드로 구현한거는 이해가 안됬다.

그래서 수기로 순서대로 정리를...

import sys;

N = 7;

s = 0;

g = [None] * N # size 를 설정하기 위해서

g[0] = [(1,9), (2,10)];

g[1] = [(0,9), (3,10), (4,5), (6,3)];

g[2] = [(0,10),(3,9),(4,7),(5,2)];

g[3] = [(1,10),(2,9),(5,4),(6,8)];

g[4] = [(1,5),(2,7),(6,1)];

g[5] = [(2,2),(3,4),(6,6)]

g[6] = [(1,3), (3,8), (4,1), (5,6)];

visited = [False] * N

D = [sys.maxsize] * N #?????

D[s] = 0

previous = [None] * N;

previous[s] = s

if __name__ == '__main__':

 for k in range(N):

  m = -1

  min_value = sys.maxsize;

  print("k is %d" %k);

  for j in range(N):

   print("j in %d" %j);

   print("outter D[j] is %d" %D[j]);

   if not visited[j] and D[j] < min_value:

    print("D[j] is %d" %D[j]);

    min_value = D[j]

    m = j

  visited[m] = True

  for w, wt in list(g[m]):

   print("w : %d, wt : %d" %(w, wt));

   if not visited[w]:

    if wt < D[w]:

     print("if  wt :%d, D[w] : %d" %(wt, D[w]))

     print("previo", previous[w]);

     D[w] = wt

     previous[w] = m

     print("afeter pri", previous[w]);

 print("min tree", end = '');

 mst_cost = 0;

 for i in range(1, N):

  print("(%d, %d)" %(i, previous[i]), end='');

이 코드의 핵심은 방문리스트와 이전리스트를 활용하는 것이다.

방문이 되는 것은 최소 가중치로 선정이 됬을때이다.

이전 리스트는 가중치가 무한에서 자기가 갖고 있는 값으로 업데이트 됬을때 된다

이 장에선 여러가지 알고리즘을 배운다

이러한 알고리즘의 핵심은 최단 경로 혹은 최소 가중치로 신장트리를 만드는 것.

네비게이션이나 경로 탐색 등 다양한 분야에서 실제로 사용된다고 한다.

1. kruskal 알고리즘.

최소 신장트리를 만드는 것

if __name__ == '__main__':

 weights = [(0,1,9), (0,2,10), (1,3,10), (1,4,5), (1,6,3), (2,3,9), (2,4,7), (2,5,2), (3,5,4,), (3,6,8),(4,6,1),(5,6,6)]

 weights.sort(key = lambda t:t[2])

 mst = []

 N = 7

 p = []

 check = 0;  

 for i in range(N):

  p.append(i);

 def find(u):

  print("find", u)

  if u != p[u]:

   print("inner find", u, p[u]);ㅎ

   p[u] =find(p[u]);

  print("find p[u] : %d" %p[u]); 

  return p[u]

 def union(u,v):

  root1 = find(u)

  root2 = find(v)

  print("root1 :%d, root:%d" %(root1, root2));

  p[root2] = root1;

  print("p[r2] : %d, r1:%d" %(p[root2],root1))

 tree_edges = 0;

 mst_cost = 0;

 while True:

  if tree_edges == N-1:

   break;

  print("check", weights)

  u,v,wt = weights.pop(0);

  print("not if check", u, v, wt)

  if find(u) != find(v):

   print("check", u, v, wt)

   print("ch", p);

   union(u,v)

   mst.append((u,v))

   mst_cost += wt;

   tree_edges += 1

 print("최소 신장트리 :", end = '');

 print(mst)

 print('최소 신장트리 가중치 :', mst_cost)

코드는 위와 같다.

이 알고리즘의 핵심은 union-find 이다.

가중치로 정렬을 했기 때문에 제일 위부터 아래로 연결을 해주면 되는데

문제는 이 정점들이 싸이클이 되는지 확인하는 것이다.

그렇기에 이 싸이클 여부를 확인하는 것은 해당 정점의 최상 루트가 무엇인지를 파악 해주면 된다.

예를 들어 1-2, 2-3, 3-4, 4-5 이렇게 연결 되어 있는 경우에 5번 노드가 2,3번에 연결이 안되는 이유는 2,3의 최상 루트가 1번이기 때문이다.

재귀적 방식을 통해서 제일 위의 루트를 찾는것, 그리고 그것이 다를때만 연결을 해주는 것이 핵심이다.(이를 위해 p라는 임의의 리스트를 형성)

절반정도 해서 뒤로 점프!

8. 그래프

그래프는 광범위한 분야에서 활용되는 자료구조!

여러가지 알고리즘과 탐색방법등이 존재한다.

8.1.1 그래프 용어

그래프는 기본적으로 용어에 대한 이해가 없으면 공부가 아예 안된다...

정점(vertex): 노드, 

간선(edge): 두개의 정점을 연결한 선

차수(degree): 정점 a 에 인접한 정점

무방향그래프 : 간선에 방향이 없는 것, (a, b)

방향그래프 : 간선에 방향이 있는 것 <a, b>

- 진입차수(in-degree): 정점으로 들어오는 차수

- 전출차수(out-degree): 정점에서 나가는 차수

경로(path): 시작점부터 끝정점까지의 정점들의 나열

- 단순경로(simple-path) : 경로상의 정점이 모두 다름

- 싸이클 : 시작과 끝이 같음

연결성분: 그래프 중 서로 연결되어있는 부분

가중치(weighted) : 간선에 가중치를 부여(거리, 소요시간 등)

부분그래프(subgraph): 주어진 그래프 중 일부분

- 트리 : 싸이클이 없는 그래프

- 신장트리 : 그래프의 모든 정점을 싸이클 없이 연결하는 그래프

8.1.2 그래프의 자료구조

그래프를 자료구조로 저장하기 위한 방법은 2가지가 있다

인접행렬(Adjacency Matrix)

- 행과 열을 통해 연결되면 1, 아니면 0으로 표현한다

- 만약 노드가 무수히 많을 경우 연결이 되지않은 부분을 0으로 표현하다보니

메모리? 등의 낭비가 있다고 한다. 이런 경우엔 리스트 활용

인접리스트(Adjacency List)

- 연결 된 부분을 리스트로 표현

예) 1번노드와 3번 노드가 연결되어있다면

인접행렬 : a[1][3] = 1

인접리스트 : a = [[],[3]...]

- 1번째 인덱스가 3을 뜻한다 = 1이 3을 가리킨다로 이해