CS/알고리즘 (2) 썸네일형 리스트형 [인프런|Dynamic Programming(1)] 영리한 프로그래밍을 위한 알고리즘 강좌 Dynamic Programming Recursive의 경우 이미 했던 호출을 다시 부르는 중복이 발생하여 효율이 떨어진다. ex) Fibonacci Numbers Memoization(Top-down) 배열에 중간 계산 결과를 저장한다(caching) 시작이 상위 사례부터 하위 사례(base case)까지 점점 작아지면서 호출되므로 위에서부터 시작된다하여 Top-down이라 한다. Dynamic programming(Bottom-up) 초기 작은 case부터 상위, 최종 case까지 값을 계산하면서 올라온다하여 Bottom-up이라 한다. binomial coefficient 이항계수 계산 N개 중에 K를 뽑는 경우를 계산한다. 수학적으로는 N! / (N-K)! K! 과 같이 풀 수도 있겠지만 컴퓨터 .. [인프런|그래프(1)] 영리한 프로그래밍을 위한 알고리즘 강좌 그래프 개념과 표현 - (무방향) 그래프 G=(V,E) V: 노드(node) 혹은 정점(vertex) E: 노드쌍을 연결하는 에지(edge) 혹은 링크(link) 개체(object)들 간의 이진관계를 표현 n=|V|, m=|E| - 방향그래프(Directed Graph) G=(V,E) 에지(u,v)는 u로부터 v로의 방향을 가짐 - 가중치(weighted) 그래프 에지마다 가중치(weight)가 지정 그래프의 표현 - 인접 행렬(adjacency matrix) - 인접리스트 (adjacency list) 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트 2m개 edge1개당 2개가 필요 그래서 2*m개가 필요 degree는 인접한 정점의 개수이다. 인접리스트는 노드의 최대 개수.. 이전 1 다음
