vss121의 블로그

Graph review Graph : Graph G는 Vertex (정점) 들의 집합 V(G) , 두 vertex를 이어주는 edge (간선) 들의 집합 E(G) 로 구성되어 있는 구조. G = (V(G), E(G)) Simple graph(라 가정) : Self-loop 나 multiple edge 를 가지지 않는 graph - Directed graph : E(G) 의 각 원소들은 ordered pair 임 (방향성이 있음) e = (a,b) (≠(b,a)) - Undirected graph : E(G) 의 각 원소들은 unordered pair 임 (방향성이 없음). e = {a,b} - (v, u) ∈ E(G) 일 때, v는 u와 adjacent (인접 하다) (undirected graph 에서..

보호되어 있는 글입니다.

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 내부 검색 트리 : 메인 메모리 내에, 메인 메모리에 모든 키를 수용할 수..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

알고리즘 - 목적) 컴퓨터를 통해 문제를 푼다 - 컴퓨터가 풀 수 있는 문제인지 정의하고(컴퓨터가 쓸 수 있는 형태로 바꾸고), 이 문제(problem)를 컴퓨터가 이해할 수 있도록 명확하고 정확한 절차를 통한 해답(solution)을 찾아나가는 과정이 있어야 함 문제 : '답을 찾기 위한 질문' 매개변수 : 문제에서 언급되었지만 할당되지 않은 변수들, int x; 실체(instance) : 매개변수에 실제로 할당된 값, x=5; 알고리즘 : 어떤 문제를 풀기 위한 유한한 절차와 방법 - 문제 : 수학적으로 엄밀히 정의된 - 절차와 방법 : 계산 문제 -> 숫자, 사칙연산 이용 컴퓨터로 계산 문제 -> 컴퓨터에 주어진 명령어 집합(instruction set) 이용 의사코드 (pseudo-code) : ..