복습용

이 챕터에서는 Dynamic Programming이라는 문제 해결 방법에 대해 배운다. Dynamic Programming은 어떤 문제를 해결할 때 sub문제들의 subsub문제가 overlap되는 경우 사용하는 Algorithm기법을 말한다. 책에서는 이 예시로 Rod Cutting문제를 말하고 있는데 Rod Cutting문제란 다음과 같은 문제를 말한다. Q: 어떤 Value를 지닌 통나무(Rod)를 판다고 해보자. 그런데 이 통나무는 길이에 따라 매기는 값이 비례하지 않게 달라진다. 예를 들어 다음 표와 같이 길이에 따른 값이 달라진다. 이 때 주어진 길이 n의 통나무와 값이 담겨있는 배열 p에 대해 이 Rod의 max Price는? Input: 통나무의 길이n, 값이 담긴 배열 p[1:n] Out..

이 챕터에서는 알고리즘 구현을 위해 이용되는 자료구조들 중 내가 잘 모르는 것에 대해서만 알아본다. (1) Stack과 Queue 쉽고 대충 알고 있으니까 안 다룸. array implementation과 linked list implementation둘다 가능. head와 tail정하는 것도신경써서 해야한다는 점만 유의하자. 근데 재미있어 보이는 문제가 있어서 소개한다. 사실 학교에서 자료구조 중간고사때 나왔던 문제 같은데 틀렸다. 근데 여기서 보니까 화가나서 열심히 풀어봤다. 그냥 발상 문제인 것 같다. 재밌는 문제: 두 개의 Stack을 써서 Queue를 만들고 Enqueue와 Dequeue의 Time Complexity를 분석하시오. Stack과 queue는 in과 out이 그 순서가 완전히 반대..

이 주에는 Data의 Classification문제를 다룬다. 내용 참고는 wiki docs에서 하는게 좋다. (https://wikidocs.net/book/587)한글 자막 없는 강의도 있고 사실 강의를 듣는거보다 wiki docs를 읽는게 영어 못하는 우리의 입장에서는 더 잘 이해가 된다. 이번 거는 내용 이해가 진짜 중요하다. 내용 잘 이해하고 과제를 풀어보도록 하자. 나같이 똑똑하지 않은 사람들에게 팁을 주자면 옆에 종이든 뭐든 메모할 수 있는 것을 놓고 풀어보자.. 행렬 연산은 복잡하니까 그냥 암산으로 척척!하기가 힘들다.. 물론 똑똑한 사람들은 잘 한다. 아 그냥 5개 채우면 되겠구나, 그리고 읽어보면 ex2.m이랑 ex2_reg.m이 메인 실행파일인 것 같다. 아마 reg가 붙은 건 reg..

이 챕터에서는 n time안에 끝낼 수 있는 sorting들을 배우는데, 대표적으로 Counting sort를 다뤄보고자 한다. (*책에는 Bucket sort랑 Radix sort도 있음) 우선, 원소들의 대소를 부등호로 비교해가며 정렬하는 비교정렬 방법들은 n time안에 끝낼 수 없다는 것이 알려져있다. 이론적 증명을 보고싶다면 책을 참고하면 된다. 나는 안궁이어서 안 봤다. 그럼 n time안에 끝낼 수 있는 정렬이 있을까? 수의 range가 n에 const하게 비례할 때 n time안에 끝낼 수 있는 정렬로서 Storing Sort가 알려져있는데 다음과 같은 아이디어를 생각해보자. 만약 우리가 정렬하고자 하는 배열에서 어떤 수가 몇 번 나오는지 세어 놓은 자료가 있다면, 그 자료만 가지고도 원래..

이 챕터에서는 과제하는 과정을 소개해본다. 이런 과제에 안 익숙한 사람들은 힘들 것 같아서,, 일단 과제 다운 받는 것부터 해보자. 이렇게 과제에 커서를 대고 클릭해보면 저렇게 here로 표시되어 있는 곳이 있다. 클릭하면 과제가 다운받아진다. 아무데나 저 폴더를 받아놓고 들어가자 그러면 이렇게 과제에 대한 설명PDF와 code들이 들어있는 폴더가 있다. pdf는 최대한 꼼꼼하게 읽어보자. 변수 설명 같은 것은 조금 이해하기 힘들겠지만 그래도 읽어야 풀기 편하다. 같이 읽어보자. 아 저 4개말고는 optional이라니까 저 4개만 일단 과제로 하면 될 것 같다는 생각이 든다. 그럼 저 넷 중 아무 코드나 열어보자. 저 넷 중 아마 아무 코드나 까서 열어보면 왼쪽과 같은 창이 나올 것이다. (matlab기..

배우는 내용 중에 조금 어려운 내용이랑 과제들 정리할 생각 모든 지식과 코드 출처는 이곳이다. https://www.coursera.org/learn/machine-learning/home/welcome

이 챕터는 Sorting의 한 방법인 Quick Sort에 대해 배운다. Average case의 Time Complexity 증명은 생략하지만, Worst case n2에 average case nlgn인 알고리즘이라고 생각하면 될 것 같다. worst case의 증명은 쉬우니까 알고리즘을 설명하고 한 번 하고 가겠다. (1) QuickSort Algorithm의 설명 QuickSort algorithm은 다음과 같은 재귀적 알고리즘이다. (i) 배열의 원소 중 하나의 원소를 골라 Pivot으로 선정한다. (-->이 Pivot선정을 Randomize시켜야 average nlgn이 나온다.) (ii)그 Pivot보다 작은 놈들을 Pivot왼쪽에, 큰 놈들을 Pivot오른쪽에 놓는다.(called Part..

이 챕터는 2-(0)에서 알아본 Heap의 성질과 그 연산들을 통해 어떻게 효율적인 Sorting을 구현할 수 있는지 알아본다. 우선, 원래 있는 배열을 Heap으로 만든다. 이것이 2-(0)에서 말했듯이 BuildHeap과정인데, 이것이 n time걸리는 것을 저번 글에서 알아보았다. 이제 해야할 일은 계속 최대인 원소를 뽑는 것이다. 우선, 처음으로 만든 Heap을 생각해보자. 그러면 그 Heap에서 최대인 원소, 즉 배열의 맨 뒤로 가야할 원소는 현재 배열의 제일 첫번째 원소인 root node에 존재한다. 따라서 이 root node와 마지막 node를 swap해준다. 그 다음 마지막 노드는 더 이상 Heap의 일종으로 생각하지 않는다. 이러면 이제 바뀐 root입장에서 양 옆 tree는 Heap..