<-->
본문 바로가기

반응형

분류 전체보기

(39)
트리 - 1 트리 : 루트와 서로 연결되지 않는 서브트리로 이루어진 특수한 그래프이다. n-트리 중간 노드들이 n개의 자식 노드를 갖는 것을 의미한다. ( 이진트리는 모든 중간노드들이 2개의 자식노드를 가짐) 이진트리 : 공집합이거나 루트,왼쪽 또는 오른쪽 서브트리로 이루어져있다. 1. 사향이진트리 : 왼쪽 또는 오른쪽으로 편향된 이진트리 2. 완전 이진트리 : 레벨 k-1 까지만 차있고 레벨 k부터 왼쪽부터 하나씩 채우는 이진트리 3. 포화이진트리 : 잎노드를 제외한 모든 노드가 2개의 자식노드를 갖는 경우.
그래프 1. 그래프의 정의 그래프 G = (V,E) vertex의 집합 V edge의 집합 E 경로: 연결된 정점들의 순서 순회: 사이클 ( ex) 1->2->3->1) 2. 그래프의 용어 단순그래프 : 한쌍의 정점사이에 최대 하나의 연결선이 존재. 멀티그래프 : 단순 그래프의 확장, 한쌍의 꼭지점 사이 연결선의 개수는 제한이 없다. 3. 그래프의 표현 그래프 관련 알고리즘을 사용하려면 그래프를 컴퓨터가 이해할수 있는 형태로 만들어 줘야한다. 인접행렬 : |v|=n일때 n*n행렬 인접리스트 : 인접한 정점들을 연결리스트로 표시한것.
생일 뚜뚜 뚜뚜뚜뚜 뚜뚜뚜뚜뚜 뚜뚜뚜뚜뚜뚜뚜 얼마전에 주문한 키보드랑 옷이 집에 도착했단 말에 하루종일 붕 떠있었다. 그리고 오늘은 바로 내 생일! 1년중에 가장 따뜻한 날이다. 폰을 5시간이나 봐서 죄책감이 들지만 오늘만큼은 조금 풀어져도 되지 않을까? 수정할점, 성과 불편한점 : 모르겟다~~~ 오늘 한 일 : 다익스트라 알고리즘 이론 학습
선택 정렬 시간복잡도 1. 각 반복마다 최소값 찾기 탐색 횟수는 n번 탐색에서 1번 탐색할때까지 감소 n + n-1 + n-2 + ... + 2 + 1 = 등차수열 (n^2+n/2) 2. swap 상수(c)시간안에 끝남 , n번 호출 c * n 3. 나머지 연산들 마찬가지로 상수시간안에 끝남(c), n번 호출 c *n 합산 결과 = n^2+ n/2 + c*n + c*n = θ(n^2) 선택 정렬은 best 케이스 이든 worst케이스이든 최소값 찾는 범위는 바뀌지 않는다. 따라서 입력 크기 n에 관계없이 θ(n^2)
삽입 정렬의 시간 복잡도 삽입 정렬이란? 삽입정렬은 화투나 포커 같은 카드게임과 비슷하다. 카드를 뽑을때 마다 알맞은 위치에 넣어 정렬된 상태를 유지하기 때문이다. 삽입 정렬의 시간 복잡도 최악의 케이스: 뽑은 숫자들이 정렬된 하위 배열 원소들보다 작은 경우 (역순으로 정렬된 상태) 매번 뽑은 숫자의 자리를 위해 하위 배열의 크기 k만큼 움직여야한다. 이 외의 잡다한 코드(크기 비교, swap)는 상수시간이 걸리기때문에 c로 취급한다. k=1 부터 시작하므로 ( 최초에 정렬된 하위배열 크기는 1) c*1 + c*2 + c*3 + ... +c*(n-1) = c * (n^2+(n-1)/2) = O(n^2) 최선의 케이스: 뽑은 숫자들이 정렬된 하위 배열 원소들보다 큰 경우 (바르게 정렬된 상태) 정렬된 하위 배열 원소들은 움직이지 ..
함수 - 2 단사,전사,전단사 함수 1. 단사함수 f: A->B에서 a1,a2 ∈ A에 대하여 f(a1)=f(a2)이면 x1 = x2일 경우 단사함수 라고한다 ( one - to -one function) Ran(f) ⊆ B이다. (치역) 롤 랭크게임이랑 비슷하다. 집합 A의 원소들은 겹치는 챔프를 고를수 없다. 2. 전사함수 f: A->B에서 에서 B의 모든 원소 b에 대하여 f(a)=b가 성립되는 a ∈ A가 적어도 하나존재할때 전사함수라고한다. (onto function) Ran(f)=B B의 모든 원소가 화살에 맞아야 성립할 수 있다. 3. 전단사 함수 f:A->B에서 f가 전사인 동시에 단사인 함수 (one-to-one correspond function) Ran(f) = B 여러가지 함수들 1. 함성함수 ..
함수 함수는 관계의 특수한 형태이다. (관계의 화살표 도표 형태) 함수는 관계에서 첫번째 원소가 같지 않은 순서쌍의 모임이다. ex) R = {(1,a),(2,b),(3,c)}를 함수로 표현하면 함수의 정의 집합 X에 있는 모든 원소 x가 집합 Y에 있는 원소 중 오직 하나씩만 대응되는 관계를 말한다. (집합 X의 모든 사람들은 무조건 화살 한발을 쏴야한다.) 이때 집합 X는 정의역(domain)이 되고 집합 Y는 공변역(codomain)이 된다. 화살을 맞은 Y의 원소는 치역(range)이라고 한다. 정의역 = Dom(f) = {x|(x,y)∈f, x ∈X, y∈Y} -> (x,y) 순서쌍의 x 치역 = Ran(f) = {y|(x,y)∈f, x ∈X, y∈Y} -> (x,y) 순서쌍의 y 함수는 자판기랑 비..
관계의 성질 집합 A에 대한 관계 R은 특정 성질에 따라 나뉘어진다 4개의 성질들을 외우고 방향그래프로 보면서 이해하는게 더 쉬운거같다! 1. 반사관계 : 집합 A의 모든원소 x에 대해 xRx을 만족 A = {1,2,3,4}라고 할때 집합의 모든 원소가 xRx를 만족하기 때문에 반사관계이다 2. 대칭관계 : xRy 이면 yRx임을 만족 1R2 이면 2R1 이기 때문에 대칭관계이다. ( 3R3 또한 대칭) 반사관계와 달리 위 그림에서 원소 1,3이 대칭관계가 아닌데도 관계 R이 대칭관계가 되는이유는 p -> q 에서 p가 false 일때 항상 참이 되기 때문이다. (xRy가 없(false)기 때문에 대칭관계는 참) 3. 반대칭관계 : xRy이고 yRx 일때 x=y를 만족 (대칭관계와 정반대개념이 아니다!) 반대칭 관계..

반응형