이빨 빠진 미남이

Peak Finder peak을 찾는 것이 주제입니다! Find a peak if it exists a peak: 극대값이 여러 개여도 하나만 찾으면 됨 if it exists: 극대값의 정의에 따라 배열에 극대값이 존재 여뷰가 갈림. 따라서 이 조건이 붙음 두 가지 버전이 있는데, 1-dim과 2-dim입니다. One-dimensional Version 여기서는 Position 2와 9가 peak이라고 합니다. 대신 조건으로 $b \ge a$, $b \ge c$이고, $i \ge h$이어야 합니다. 앞에서부터 직진하면서 시작하고, left에서 시작하게 될 경우, 평균적으로 n/2개를 살펴보게 될 것입니다. 그리고 가장 worst case는 모든 n개를 다 살펴보는 경우가 됩니다. Complexity는 ..

MIT의 INTRODUCTION TO ALGORITHMS 수업을 바탕으로 공부하였고 정리합니다. - 잘못된 내용이 있다면 댓글로 지적 부탁드립니다. 구구절절한 설명 시작 AVL tree는 Balanced Binary search tree라고 볼 수 있습니다. 기본 property가 BST이기 때문입니다. 중요한 점은 being balanced입니다. 이미 균형이 잡혀 있다는 것이 기본 속성이기 때문인데요. Balance factor의 부분이 AVL tree의 중요한 속성이기 때문에 이점을 중심적으로 보면 좋을 것 같습니다. 강의는 AVL trees의 definition, rotations, insert를 중점으로 봅니다. Binary Search Tree(BSTs)의 경우, left/right subtr..

MIT의 알고리즘 수업 강의 자료를 참고하였습니다. 왜 정렬하는가? 확실한 응용 사례 MP3 보관함 정렬 전화번호부 정리 검색하기 쉬움 정렬하면 쉬워지는 문제들 중간값 또는 가장 가까운 쌍 찾기 이진 탐색, 통계적 이상치 확인 응용 사례 데이터 압축 컴퓨터 그래픽(화면 렌더링) Finding a median 중간값을 찾아보겠습니다. 정렬되지 않은 배열 A를 정렬된 B로 바꾸려고 합니다. array A[0:n] → B[0:n] unsorted → B[n/2] 입력값으로 비교 함수를 갖는 정렬 알고리즘이 있다면 충분한 시간이 흐른 뒤에 정렬된 배열 B를 얻을 수 있음 정렬된 배열이 있다면 상수의 시간이 걸림 Binary Search 이진 탐색을 하는 경우입니다. A[0:n] looking for specif..

Array(배열) List(리스트) LinkedList(링크드 리스트) Stack(스택) Queue(큐) Dequeue(디큐) Tree(트리) Heap(힙) Graph(그래프) 0. 자료구조와 알고리즘이란? 자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조입니다. 알고리즘은 자료구조에 쌓인 데이터를 활용하여 어떤 문제를 해결하기 위한 여러 동작의 모임입니다. 1. Array 가장 기본적 자료 구조로, 논리적 저장 순서와 물리적 저장 순서가 일치합니다. 따라서 index로 해당 원소(element)에 접근이 가능합니다. 찾고자 하는 원소의 인덱스 값을 안다면 Big-O(1)에 해당 원소로 접근 가능합니다. 즉, random access 가 가능합니다. 이 말의 뜻은 어떤 위치라도 접근 ..