대학원생 신짜오는 공부중

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간은 apsp의 두번째 강의 내용을 정리해보려고한다내용은 Floyd-Warshall Algorithm과Johnson Algorithm이다 Floyd-Warshall Algorithm Floyd-Warshall Algorithm의 가정은 아래와 같다negative weight는 존재하지만 negative weight cycle은 존재하지 않는다 time complexity는 O(V세제곱)이 소요되고dynamic programming(dp)를 이용해서 해결하는 알고리즘 중 하나이다 최적해를 찾는 구조를 살펴보자우선 그래프G가 있다고 할 때 모든 vertex들을1부터 n까지 numb..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간에는 all-pair shortest path의첫 번째 강의 내용을 정리해보려고한다 저번 시간에는 single-source shortest path(sssp)에관한 내용을 2차례에 걸쳐 정리했는데이번에는 all-pair이다  All-Pairs Shortest Path (APSP)는주어진 그래프가 있을 때 모든 pair의 vertex에 대해서shortest path를 찾는 것이다 이전의 sssp는 한 개의 vertex에 대해서shortest path를 찾는 것이지만apsp는 모든 vertex에 대해서 찾는 것이다 따라서 apsp에 관한 내용은 위의 ppt처럼Matrix로 표현할..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다. 저번 시간에 다익스트라 알고리즘에 대해 배웠는데다익스트라 알고리즘의 가장 중요한 특징 중 하나는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..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간에 정리해볼 내용은c++에서의 type casting과 Exception Handling  Type Casting  type castring이란어떤 variable을 어떤 타입에서다른 타입으로 바꿔주는 것을 말한다 type casting의 종류는c-style castingstatic castingdynamic castingconst castreinterpret cast가 있다 먼저 c-style casting이다 C언어에서 casting을 하는 타입이다타입 캐스팅을 하고하자하는 변수 앞에괄호를 열고 바꾸고싶은 타입을 적어주면 된다 예를 들어 float을 int로 바꿔주고싶으면..