후위 계산

ex) 2 5 + 3 2 1 + = 63

1. 25+에서 연산자 ‘+’를 만났을 때, 멈추고 2+5 실시
2. 73에서 연산자 ‘‘를 만났을 때, 멈추고 7×3 실시
3. 2121+에서 ‘+’ 앞에 두 숫자 2+1 실시
4. 213* 에서 21×3 실시

함수의 종류

call by value, call by reference

분류 기준

• 함수 호출에서의 인자 전달 방식
• func(p1, p2) 에서의 인자 전달 방식
• 파이썬은 call by value도, call by reference도 아닌 call by object reference 이다.

파이썬 학습

• 파이썬의 함수는 무조건 식이다.
• 식은 반환(return) 받는 것을 말한다. (a+b 도 식이다 -> None을 반환한다.)
• lambda는 return 의미가 내재되어 있으므로, return을 사용하지 않는다.
  • ex) lambda a, b: return a + b (X) –> lambda a, b: a + b (O)
• update()는 None을 return 한다.

TSP (Traveling-Salesman-Problem)

1. 무방향, 가중치 그래프

2. 출발한 곳으로 돌아온다.

3. 그래프의 모든 edge가 다 존재한다.

4. w(e) 합이 최소이다.

markov 문제

• 탈옥수가 검문을 피해 마을과 마을 사이를 돌아다니고 있다.
• 탈옥수는 탈출 당일 인접한 마을에 숨었다.
• d일이 지났을 때 각 마을에 숨어있을 확률을 구하시오.
• 알고리즘 문제해결전략 1권 p.269

Shortest Path(최단 경로) 특징

1. 음수 사이클이 없다.

2. 방향 그래프(directed graph)

3. 가중치 그래프(weighted graph)

4. 경로의 길이 : edge 가중치의 합

Prim algorithm

1. 정점 하나를 가진 트리에서 시작
   • TV = {v1}
     • TV : 트리의 정점
2. 트리 내의 정점 u와 트리 밖의 정점 v를 잇는 Edge 중 최소 비용을 가진 (u,v)를 트리 Edge로 만든다.
   • TE = TV U {u,v}
3. 트리 밖의 정점 v도 트리의 정점으로 만든다.
   • TV = TV U {v}
4. TV = V(G)와 같아지면 종료

Kruskal algorithm

1. Edge를 가중치가 작은 것에서 큰 것 순으로 정렬
2. 트리에 Edge를 하나씩 추가
3. 사이클이 생기면 추가하지 않는다.
4. 최소 비용 신장 트리가 완성되면 |E| = |v|-1

MST(Minimum cost Spanning Tree)

신장 트리(Spanning Tree)

1. connected(연결되어 있다.)
2. 최소 엣지 수 |E| = |V| - 1 (트리 조건)
3. E(G’)는 E(G)에 포함되어 있다.
4. V(G’) = V(G)

최소 비용 신장 트리

1. 무방향 그래프
2. 가중치 그래프
3. 비용(cost) 최소화

B-tree를 사용하는 이유

• 탐색에서 최악의 경우에도 O(log2n)이 걸리는 균형 이진트리도 굉장히 큰 성과이지만,
• 데이터가 메인 메모리에 저장되어 있거나,
• 데이터베이스의 경우 하드디스크에 저장되어 있으면,
• 데이터의 연산보다는 메모리 접근에 엄청난 시간이 소요된다.
• 이 문제를 해결하기 위해 B-tree 자료구조가 필요하다.