vss121의 블로그

보호되어 있는 글입니다.

a selection algorithm is an algorithm for finding the kth smallest number in a list or array 여러 개의 데이터가 무작위로 있을 때 전체 데이터에서 매번 가장 작은 (또는 가장 큰) 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복하여 데이터를 오름차순(또는 내림차순)으로 정렬할 때 사용 01 평균 선형 시간 선택 알고리즘 02 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

01 점화식 Recurrence formula 수열의 항 사이에 성립하는 관계식 점화식은 자기 호출을 사용하는 함수(재귀함수, recursive function)의 복잡도를 구하는데 유용함 factorial (n) { if(n=1) return 1; return n*factorial(n-1) } Divide-and-conquer (분할 정복) 1. 주어진 문제를 작은 단위 (subproblem) 로 쪼갠다. 이 때 subproblem 은 본문제와 같지만 input size (입력 값) 가 작은 문제를 뜻한다. → Divide 2. 1번에서 나눈 subproblem 들을 (recursively 하게) 해결한다. → Conquer 3. 2번에서 푼 subproblem 들의 답을 적절하게 조합 (combine..

Ch01. 알고리즘이란 01. 알고리즘은 문제 해결 과정을 묘사하는 것 : 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것 - 명확하고 효율적으로 설계해야 - 입력이 충분히 큰 경우에 대한 분석 : 점근적 분석 02. 알고리즘은 생각하는 방법을 훈련하는 것 03. 알고리즘은 자료구조의 확장 Ch02. 알고리즘 설계와 분석의 기초 01. 몇 가지 기초 사항들 1 알고리즘 분석의 필요성 시간 분석(최악의 경우, 평균적인 경우)을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 필요한지 미리 짐작할 수 있다 2 알고리즘의 수행 시간 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다 Ex Ex factorial(n) -> n에 비례 3 재귀(자기호출)와 귀납..

01 레코드, 키의 정의 및 검색 트리 - 이진 검색 트리 : 자료를 찾는 색인 역할하는 자료구조 중 하나 ● 레코드 : 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 - 사람의 레코드 : 주민번호, 이름, 집주소, 집 전화번호 ... - 검색 트리는 개체의 레코드 저장, 검색 (대표할 수 있는 필드만으로 ) - 필드 : 레코드에서 각각의 정보를 나타내는 부분 ● 검색키, 키 : 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 - 키는 필드 하나 or 필드 복수 개 ● 검색트리 - 한 노드에서 최대 몇 개의 자식 노드로 분기? 1 이진 검색 트리 : 최대 2개, 2 다진 검색 트리 - 저장되는 장소? 1 내부 검색 트리 : 메인 메모리 내에, 메인 메모리에 모든 키를 수용할 수..

Moving data (데이터를 옮기기) : CPU와 Mem 사이, CPU-CPU movl source, dest ~복사 ● Move 4B("long") word - intel 32b 기준 그냥 mov는 16b Operand types 1) Immediate - constant integer data 상수값(C에서는 숫자값, Intel 어셈블리어는 $로 시작) - 1,2,4B로 2) Register - 8개의 범용 R중 하나 - %esp, %ebp는 스택을 나타내기 위해 특별한 용도로 사용 3) Memory - 4 consecutive bytes of memory - address movl operand combinations - Cannot do memory-memory transfers with si..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.