수업 내용 정리 (15) 썸네일형 리스트형 chapter 2. divide-and-conquer 설계 전략 Divide: 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. Conquer: 나눈 작은 문제를 각각 해결한다. Combine: 해결된 해답을 모은다. => 하향식(top-down) 이분 검색: 재귀적 방식 분할: 배열을 반으로 나누어서 중앙에 위치한 값과 x를 비교해서 두 배열 중 하나를 선택 정복: 선택된 반쪽 배열에서 x를 찾는다. 시간복잡도 경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 n/2이 되는 경우 경우2: 일반적인 경우 - 반쪽 배열의 크기는 n/2의 같거나 작은 실수 합병정렬 합병 알고리즘 시간복잡도 분석(최악) W(h,m) = h+m-1 (예 U: 4,5,6,7 V: 1,2,3,8) 합병정렬 알고리즘 시간복잡도 분석(최악) W(h,m) = W(h) + W.. chapter 1. 알고리즘: 효율, 분석 그리고 차수 순차검색 알고리즘 배열의 수 더하기 교환정렬 행렬곱셈 이분검색 알고리즘 최대 검색횟수 : lg(n) + 1 피보나찌 구하기 재귀적 방법 문제점: 어떤 피보나찌 수를 구하기 위해 다른 피보나찌 수가 중복될 수 있다. fib(n)의 함수 호출 횟수 계산 수학적 귀납법을 통한 호출 횟수 검증 T(n) > 2**(n/2) 임을 보이자 반복적 방법 중복 계산이 없다 => 수행속도가 훨씬 빠르다! 계산하는 항의 총 개수: T(n) = n + 1 (f[0] 부터 f[n]까지) 알고리즘 분석 Every-case analysis Worst-case analysis 입력배열이 거꾸로인 최악의 상태일 때 => (n-1)*n/2 행렬곱셈 시간 복잡도 단위 연산이 for 루프에 있는 곱셈 : T(n) = n*n*n 순차검색 시.. Chapter 2 : Application Layer Principles of network applications creating a network app end systems에서 실행 network 넘어 통신 network-core devices와 관련해서까지 코딩할 필요 없음 Client-server paradigm server host에 항상 있음 영구적인 IP address data center에 존재 clients server와 통신 간헐적으로 연결됨 동적 IP 주소를 가짐 직접적으로 client끼리 연결하지 않음 ex. HTTP, IMAP, FTP Peer-peer architecture 서버가 항상 켜져있지 않음 end systems 끼리 직접적으로 통신함 peer는 간헐적으로 연결되고 IP를 바꿈 자기 확장성을 가짐 ex. P2P file .. Chapter 1 : Introduction Internet The Internet: a "nuts and bolts" view hosts = end systems packet switch: router, switch Internet: Interconnected ISPs protocol: control sending, receiving of messages The Internet: a "service" view Infrastructure가 application에게 service를 제공 programming interface를 distributed application에게 제공함 Protocol 모든 Internet 통신은 protocol에 의해 관리됨 Network edge: hosts, access network, physical media ho.. Lecture 3 | Loss Functions and Optimization Summary 2강에서 linear classification에 대해 배웠었다. linear classification은 Weights를 통해 예측을 하는 것이다. 이번 강의에서는 Weights를 평가하고 어떻게 좋은 weights를 구할지에 대해 다룬다. Multiclass Support Vector Machine Loss loss funciton은 w(앞으로 weights를 w로 표기)가 얼마나 구린지 수치화하는 함수이다. 따라서 loss를 줄이는 것이 궁극적인 목표이다. 그럼 loss를 구해보자! 사진 밑의 숫자는 w를 이용해 구한 예측값이다. 자동차를 제외한 나머지는 부정확하게 예측된 것을 알 수 있다. 최종 Loss는 고양이, 자동차, 개구리의 Loss의 평균이다.(종류별 로스의 평균) 종류별 .. 13. Project Planning & Management agile말고 전통적 방식으로 개발하는 회사의 스타일을 알아보자. (간트차트, 워터폴 방식) Man-Month 이 프로젝트에 사람을 얼마나 투입해야 하지? 4명이요. 그냥 사람 4명??, 능력상관없이 4명?? Man-Month: 일을 한달동안 해서 끝내기 위해 필요한 사람 (ex. 12 M/M는 한달에 12명, 12달동안 1명필요) => 개발자마다 능력이 제각각인데 이렇게 계산해도 되는가? The Mythical Man-Month 이 책은 소프트웨어개발에서 개념적 일관성이 왜 중요한지, 프로토타입(파일럿시스템)이 얼마나 중요한지, 사람을 많이 투입해도 진행이 더뎌지는 이유는 뭔지, 왜 여전히 만능도구는 없는지 등등 소프트웨어 개발에 관련한 고찰 소프트웨어 개발이 man-month로 측정한다는건 신화다. .. 10. Sorting and Searching Algorithms Selection Sort 1. 일단 전체에서 가장 작은 값 찾아서 앞으로 가져옴=> 첫번째는 sorted 나머지는 unsorted(최솟값이랑 현 위치만 바꾸고 나머지는 순서 바뀌지 않음) 2. unsorted에서 가장 작은 값 찾아서 또 땡겨옴 => 두번째까지 sorted 나머지 unsorted 3. 위 과정 반복 시간복잡도: 갯수가 n개일때 비교횟수는 n*(n-1)/2이므로 O(n**2)이다. template int MinIndex(ItemType values[], int startIndex, int endIndex) // Post: Returns the index of the smallest value in // values[startIndex]..values[endIndex]. { int inde.. 9. Priority Queues, Heaps, and Graphs Heap complete binary tree & 조상>자식 ReheapDown 노드가 heap의 규칙을 어기고 있을 때 하는 것 노드의 자식노드 중 자기보다 크고 둘중에 큰것을 고른다음 바꾼다. 이과정을 반복해서 자기 자리를 찾는다. ReheapUp 조상노드가 자기보다 작다면 올라가는 것 Removing the largest element 1. bottom rightmost element를 root로 가져옴 2. bottom rightmost element를 삭제 3. root를 ReheapDown 해줌 Inserting new element 1. bottom leftmost place에 삽입 2. ReheapUp 해줌 Priority Queue only the highest-priority eleme.. 이전 1 2 다음
