미소를뿌리는감자의 코딩

1. 개요이번에는 knap sack 문제에 대해서 알아보았다.knap sack은 보석의 무게와 가격이 있을 때, 어떻게 최대로 높은 가격의 보석을 제한된 무게 안으로 챙길 수 있는지에 대한 문제이다.이를 dynamic programming으로 코드를 작성해서 해결하게 된다.0, 1, 2, 3, 4, 5 는 가방의 최대 무게가 0일 때, 1일 때, ...을 의미한다. 이전 보석을 확인하고, 다음 보석을 확인할 때는 2가지 경우가 생기게 된다.보석이 남은 가방의 무게를 초과할 때보석을 가방에 넣을 수 있을 때 -> 보석을 가방에 넣을 것인가, 넣지 않을 것인가.로 나뉘게 된다. 이런 점화식을 기반으로 코드를 작성하게 된다. 점화식에서 B[i][w] = max(B[i-1][w], B[i][w - wi] + v..

1. 개요Dijkstra Algorithm과 Floyd Warshall Algorithm을 이용하는 이유가 무엇일까? MST의 kruskal Algo. 와 Prim. Algo 와는 다른 점이 무엇일까?MST의 경우엔, 모든 vertex를 방문할 수 있는 최단 경로를 나타낸다. 반면 Dijkstra는 하나의 vertex에서 다른 vertex까지의 최단 경로를 나타낸다.Floyd Warshll은 한 vertex에서 다른 vertex까지의 모든 최단 경로를 알아내고자 사용하는 알고리즘이다. 따라서, Dijkstra는 O(n^2)의 시간 복잡도를, Floyd Warshall은 O(n^3)의 시간 복잡도를 가진다. 아래 코드에서 Floyd Warshall 알고리즘을 Bellman Ford 알고리즘으로 잘못 적었다..

1. 개요잊어버리기 쉬운 알고리즘인 Kruskal's Algorithm과 Prim's Algorithm에 대해서 공부해 보는 시간을 가졌다.두 알고리즘은 Minimum Spanning Tree를 해결하기 위한 대표적인 두 알고리즘이다. Kruskal's Algorithm은 edge가 제일 작은 값들 순으로 접근하여, 해당 edge를 잇는 정점 u, v의 parent node가 동일하지 않다면 합쳐주는 방법이다. - parent node가 동일한데, 해당 edge를 포함시키게 되면 cycle을 형성하게 될 것이기 때문이다. Prim's Algorithm은 edge가 아닌, node를 기준으로 접근하는 방법이다.일단, 특정 node를 선택하고, 해당 노드가 접근할 수 있는 노드까지의 weight 중 가장 ..

1. 개요DFS와 BFS에 대해서 공부해 보는 시간을 가지게 되었다. 2. DFS & BFS 위 sudo code는 공유 정점이 있더라도 적용할 수 있는 코드이다.이는 3가지 색을 이용해서 방문 전, 방문 중, 방문 후 노드를 나타내어 주었다.흰색 : not visited회색 : visiting검정 : visited를 나타낸다. 시작 정점을 제외한 모든 정점에 대해서 색을 흰색과, parent node는 NIL 그리고 거리는 무한으로 설정해 주었다.시작 노드 색을 grey로 설정하고, 시작 노드는 부모 노드가 없으므로 pi 또한 NIL로 설정해 주었다.시작 노드와의 거리도 0으로 설정해 주었따. BFS 는 queue로도 구현이 가능하기에, Q에 대하서 deque를 선언해 주었다. 또한 queue에서 po..