복습용

이 챕터에서는 Dynamic Programming 문제 카테고리에 속하는 Matrix Multiplication 문제에 대해 다뤄보고자 한다. (1)Intuition: 행렬의 연쇄곱 ABCDE같은 것을 생각해보자.(행렬곱이 conformable하다는 것을 가정하고) 이 행렬곱은 (((AB)C)D)E로 계산하든, A(B(C(DE)))로 계산하든, 그 결과는 동일하지만, 하는 연산의 횟수가 동일하지 않다. 우선, mxn행렬 A와 nxr행렬 B를 생각해보면 AB를 계산하는데 걸리는 시간은 mnr이다. (loop를 작성해보면 3중 loop가 보여서 명확히 알 수 있을 것이다.) 또한, 이를 바탕으로 밑의 그림과 같은 예제를 보면 행렬곱의 순서에 따라 연산횟수가 달라지는 것이 명백히 보일 것이다. 따라서 이런 연..

이 챕터에서는 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..