대학원생 신짜오는 공부중

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다. 저번 시간에 다익스트라 알고리즘에 대해 배웠는데다익스트라 알고리즘의 가장 중요한 특징 중 하나는edge의 weight들 중에 negative weight가 있으면 안된다는 점이다 기본적으로 다익스트라는 greedy algorithm에기초하고 있기 때문에negative weight가 있으면 기존에 확정 되었던 값이이후에 더 짧아지는 경우가 생길 수가 있는데이는 greedy algorithm의 기본적인 가정에 반하게 되는 것이기 때문이다 따라서 edge들의 weight에 음수가 있는 경우다익스트라 대신에 사용할 수 있는 알고리즘은 바로Bellman-Ford Algorithm이다  Bel..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이 번 시간은 single-source shortest paths의첫 번째 강의 내용에 대해서 정리를 해보려고한다주된 내용은 Dijkstra(다익스트라) 알고리즘이었다  다익스트라는 대표적인 single-source shortest path 알고리즘이다single-source shortest path의 가장 대표적인 예시는 위의 상황이다 마을이 7개의 건물이 있고 가장 왼쪽에 우체국이 있다고 할 때각각의 집에 방문할 수 있는 가장 짧은 path는 무엇일까  일반적으로 single-source shortest path는weighted, directed graph에서 path를 찾는 알고..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.Dynamic Programming에 대해배운 내용을 정리해보도록 하겠다  학창시절을 보내다보면 한 번쯤은 들어봤을피보나치 수열 피보나치 수열은 각각의 숫자가 앞의 두 숫자의 합으로이루어져있는 수열로피보나치 수열을 위와 같이 점화식으로 나타낼 수 있다  이는 대표적인 Divide and Conquer 방식인데일반적으로 어떤 problem을 작은 subproblem으로 나누는것이다 위 ppt에서의 코드를 보면피보나치 함수를 정의해놓고 있다 Fib함수 내에서 계속해서 Fib를 호출하면서recursive하게 구현하였고n이 0이거나 1일 때 0 또는 1의 값을 리턴한다 이렇게 구현한 피보나치..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번시간에 배운 내용은Red-Black Tree.. 지금까지 배웠던 알고리즘과는약간 다르게 일관된 방법이 있는게 아니라좀 어렵고 까다롭다고 느껴질 수 있다 그래서 무작정 외우려거나 하기보다는그냥 이런식으로 이런 문제를 해결하고자했구나하는 관점에서 차근차근 정리를 해보려했다 그럼 시작..  Binary Search Tree일단 Red-Black Tree를 이해하기 위해선Binary Search Tree를 기본적으로 이해하고있어야한다 Red-Black Tree는 기본적으로binary search tree의 문제점을해결하기위해서 나온 것이기 때문이다 Binary Search Tree는각각의..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간에는 graph와 tree에 대한기본 용어 및 개념 복습곽Minimum Spanning Tree, 그리고이를 찾는 대표적인 알고리즘인Prim's Algorithm과Kruskal's Algorithm에 대해 정리해보려고한다  Graph  graph에 대한 기본 개념 복습니다 rechable -> 정점 u에서 정점 v까지 path가 존재connected graph -> 모든 vertex가 다른 모든 vertex로부터 Rechable한 graphconnected component -> 두 connected graph가 있는데 서로 연결하는 path가 없음completed graph..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이전 시간에 이어 이번에는Heap Sort와 Prioirity Queue 내용을정리해보려고한다  Heap Sort Heap Sort는 유명한 정렬 알고리즘 중 하나이다정렬이 되지 않은 array를 heap을 바탕으로정렬을 시키는 방식이다 이 과정을 수행하기 위해서는우선 array에 build_max_heap을적용시켜줘야한다 하지만 위 ppt만 봐도 알겠지만build_max_heap만 했다고그 array가 정렬이 되는 것은 아니다 우선 build_max_heap을 시켜준다음subarray에 대해서 계속max_heapify를 해줘야한다이게 무슨 말인지 자세히 살펴보자  정렬이 안된 arr..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.중간고사가 지나고 이전까지는 기본적인c++에 대해서 공부했다면이제부터는 알고리즘에 대해서 공부를한다고한다 그 첫 시간인 Heaps and Priority Queues 나에게도 처음들어보는 개념들이조금 있었어서 다른 수업들보다는더 공부를 해야겠다는 생각이 들었다 우선 Heap과 Prioirty Queue를배우기전에 기본적으로 알아야하는Binary Tree의 개념에 대해 알아보자 Binary Tree 우선 Binary Tree에 대해 알아보자한국어로는 이진트리이다 이진트리는 위 ppt 그림과 같이최대 2개의 자식노드를 가질 수 있는 트리구조이다  한 node가 갖고있는 자식의 개수를deg..