Adaid's Workroom

그리디 알고리즘(greedy algorithm)- 순간마다 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘- 최종적으로는 답이 아닐 수도 있음 거스름돈 문제- 최소의 동전과 지폐를 사용하여 N원을 거슬러주는 문제(ex) 1, 5, 10, 100, ... 으로 7570원-> 그리디(ex) 1, 4, 5 으로 12원-> 그리디 X, DP 동전0Ai는 Ai-1의 배수 -> 그리디 알고리즘 성립

트리(Tree)- 사이클이 없는 그래프- 정점의 개수: V- 간선의 개수: V-1루트 있는 트리(Rooted Tree)- 루트가 있는 트리- 루트부터 아래로 방향을 정할 수 있음용어- 부모(Parent)- 자식(Child)- 단말 정점(Leaf/Terminal Node)- 형제(Sibling)- 깊이(Depth): 루트에서의 거리- 높이(Height): 깊이 중 가장 큰 값- 조상(Ancester), 자손(Descendent): p->q로 갈 수 있을 때 p가 q보다 루트에 가까우면 p는 q의 조상, q는 p의 자손- 이진트리(Binary Tree) 트리의 표현- 그래프 표현과 같은 방식으로 저장 가능- 트리의 모든 노드는 0/1개의 부모를 가지기 때문에 부모만 저장하는 방식으로 저장할 수도 있음- 이진..

그래프(Graph)- 자료구조 일종- 정점(Node, Vertex)- 간선(Edge): 정점간의 관계- G = (V,E)로 나타냄경로(Path)- 정점 A -> B로 가는 경로사이클(Cycle)- 정점 A에서 다시 B로 돌아오는 경로단순 경로와 단순 사이클- 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클- 일반적으로 지칭하는 경로/사이클유향 그래프(Directed Graph)- 간선에 방향이 있음무향/양방향 그래프(Undirected / Bidirection Graph)- 간선에 방향이 없음루프(Loop)- 간선의 양 끝점이 같은 것가중치(Weight)- 간선에 가중치가 있는 경우: A->B로 이동하는 거리, 시간, 비용 등- 가중치가 없으면 1이라고 생각하면 됨차수(Degree)-..