대학원생 신짜오는 공부중

이번엔 dynamic programming을 이용해서동전 조합 알고리즘 문제를해결하는 법을 정리해보려고 한다 동전 조합, 즉 Coin Combinations은우리가 학창시절 수학과목에서 볼 수 있었던확률과 통계 유형의 문제인데각 동전이 주어지고 합계가 주어질 때합계를 만들 수 있는 경우의 수를 구하는 문제이다 이같은 문제는 동전의 순서를 고려하는 경우와동전의 순서를 고려하지 않는 경우로 구분할 수 있는데이번 문제는 동전의 순서를 고려하지 않는 경우였다(조금 더 간단하게 구현이 가능하다) 알고리즘 문제는 다음과 같다   그리고 Input, Output, Constraints는 다음과 같다  이러한 Coin Combinations 문제는대표적인 dynamic programming 문제이다 dynamic pr..

이번에는 알고리즘에서는 기본이 되는BFS(넓이우선탐색)과 DFS(깊이우선탐색)을c++로 구현한 내용을 정리해보려고한다 알고리즘이 .. 원리를 이해해도계속 복습하지 않으면 자꾸 까먹어서기록용 + 공부용으로 남겨두려고한다 BFS와 DFS는많은 알고리즘에서 사용하는기본이 되는 탐색법이기 때문에툭 치면 나올만큼 외우고있으면 좋은 것 같다(머리가 안좋으면 외워야,,)우선 그래프 탐색에서 필요한 Node는아래와 같이 구현했다struct Node { int value; vector children; Node(int val) : value(val) {}}; 자기 자신의 int값인 value와Node 포인터의 vector인 children을요소로 갖고있다  BFS(Breadth First Search)넓..

이번 수업시간에서 MST(Minimum Spanning Tree)에 대해 배워관련 알고리즘 문제들을 LeetCode에서 찾아 풀다가MST에서 간단한 문제를 정리해보기로했다  https://think0905.tistory.com/entry/computer-science-Graph-Tree-Minimum-Spanning-TreePrims-Kruskals-Algorithm [computer science] Graph, Tree, Minimum Spanning Tree(Prim's, Kruskal's Algorithm)이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간에는 graph와 tree에 대한기본 용어 및 개념 복think0..

이번엔 수업시간에 배운MaxHeapify를 바탕으로HeapSort를 구현해보려고 한다 MaxHeapify와 HeapSort의 내용은 아래에 있다 https://think0905.tistory.com/entry/computer-science-Binary-Tree-Max-Heap [computer science] Binary Tree, Max Heap이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.중간고사가 지나고 이전까지는 기본적인c++에 대해서think0905.tistory.com https://think0905.tistory.com/entry/computer-science-Heap-Sort%EC%99%80-Priority-Queu..

이번에 해결한 알고리즘 문제는Find the Hub이다  sssp (single-source shortest path)와apsp (all-pair shortest path)를 이용해서city들 중에서 hub city를 찾는 알고리즘 문제이다 문제에서 찾아야하는 hub city는주어지는 distance threshold 이하의 거리로가장 많은 도시들을 연결하는 city이다   이번 문제의 자세한 설명은 위와 같다input으로는 총 3개가 들어오는데도시의 개수인 ndouble array 형식의 edges그리고 distanceThreshold가 들어온다 위 예시의 경우 city1은 총 3개의 도시를 threshold보다 같거나 작은 거리로 연결하고city2도 동일하게 3개의 도시를 threshole보다 같거나..

이번에 해결한 알고리즘 문제 내용 정리이다 문제 내용은 다음과 같다 위 Figure 1을 보자각 vertex는 학생을 나타내고각 edge들은 키의 서열을 나타낸다 1 -> 5는 학생 1은 학생 5보다 키가 작다는 뜻이고5 -> 2는 학생 5는 학생 2보다 키가 작다는 뜻이다그럼 자연스럽게 학생 1은 학생 2보다 키가 작은 것이 된다 이런식으로 학생들의 키를 graph로 나타내었는데위 Figure 1에서 학생 4만 유일하게 다른 모든 학생들과 키를 비교할 수 있다 이게 무슨 말이냐하면유일하게 학생 4만 다른 모든 학생들을 비교 대상으로 가져왔을 때누가 키가 더 크고 작은지를 판별할 수 있다는 말이다 한 번 예시와 함께 이해해보자 학생 1과 학생 4를 비교해본다면1->5->4 이므로 학생 4가 1보다 크다학..

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

원래 흔히 배우는 max heap은자료 구조를 array로 많이 사용한다 나도 배울 때는 분명 array 자료구조를 이용해서max heap을 구현하는 것을 배웠지만어째서인지 (..) 이번 과제는 array가 아닌tree 구조를 base로 Max heap을 구현하는 것이었다 max heap에 대한 강의 내용 정리는 아래 링크를 참고!https://think0905.tistory.com/entry/computer-science-Binary-Tree-Max-Heap [computer science] Binary Tree, Max Heap이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.중간고사가 지나고 이전까지는 기본적인c++에 대해서th..

과제 중에 root node를 input으로 받아root로부터 연결된 tree가red black tree의 속성을 모두 준수하고있는지확인하는 코드를 작성해야했다 우선 red black tree에 대한 강의내용정리는다음 링크에 접속하면 볼 수 있다https://think0905.tistory.com/entry/computer-science-Red-Black-Tree [computer science] Red-Black Tree이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번시간에 배운 내용은Red-Black Tree.. 지금까지 배웠던think0905.tistory.com 자세한 설명이 보고싶다면 위 게시글을 참고하고지금은 코드를 ..