대학원생 신짜오는 공부중

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이 번 시간은 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로 바꿔주고싶으면..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.Multiple InheritanceMultiple Inheritance란 하나의 derived class가여러 개의 base class를 상속받게 해주는 것이다  저번 시간과 동일하게 포켓몬으로(..)예시를 한 번 보자 전기속성을 띄는 포켓몬은 electricLevel이라는 attribute를불속성을 띄는 포켓몬은 flameLevel이라는 attribute를갖고 있다 따라서 ElectricPokemon이라는 클래스와FirePokemon이라는 클래스를 또 만들려고 한다 그럼 Pikachu는 포켓몬이자 전기속성을 띄는 포켓몬이므로BasePokemon class와 ElectricPokem..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간에 정리해 볼 내용은c++에서의 class와 상속그리고 virtual function에 관한 내용이다  교수님께서 포켓몬을 이용한 ..예제를 들고오셨다 ㅋㅋ c++로 이런 귀여운 애들에 대한class를 만들어보자 각각의 attribute들과method들은 위와 같다  class design은 다음과 같다우선 Pokemon이라는 base class를 만든다base class에는name, hp, typed이라는 attributes가 있고attack, decreaseHp, getHp, getName이라는methods가 있다 그리고 Pokemon을 상속받은 class로Pikachu와..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.파이썬으로 프로그래밍을 할 때아직 프로그래밍을 잘 모르던 시절 int_list = [1, 2, 3]new_int_list = int_listnew_int_list.append(4) 위와같이 프로그래밍을 해줬는데int_list에도 4가 append되어있어당황했던 기억이 있을 것이다 그래서 막 구글링을 하다보면new_int_list = copy.deepCopy(int_list)와 같이 해야하는데그 이유는 deep copy를 해야int_list의 요소들만 담은완전히 새로운 new_int_list가생성된다는걸 들어본적이 있을 것이다 프로그래밍을 공부하다보면call by valuecall by..