본문 바로가기

Legacy(~18.10)/컴퓨터공학

(14)

[Data Structure] Hashing - 이론 HahsingSearch 알고리즘과 관련해서, 정렬이 되어있을 때, binary Search로 O(logn)의 성능을 낼 수 있다.이에 반해서, Hashing은 최대 O(1)의 성능을 낼 수 있다.Hash table은 Slot으로 이루어져있는데, 각각Slot의 이름은 숫자로 되어있고, 0부터 시작한다.이를 통해서 쉽게 item을 찾을 수 있다.item과slot을 맵핑하는 방법으로 Hash Function을 이용한다. Hash Function은 Slot name의 범위내의 int 값을 리턴한다. 위와같이 Hash Table이 만들어 지면, search는 O(1)에 할 수 있다.그러나, Hash Function의 결과 값이 같으면 한 Slot에 여러 Item이 들어 가게 되는데 이것을 Collision 이라..

[Data Structure] Deque - 이론 && ADT Deque양쪽 끝에서(rear, front) 삽입, 삭제를 모두 수행할 수 있다.Deque가 Stack과 Queue의 특징을 모두 취할 수 있어도 LIFO, FIFO 순서를 정하도록 요구하지는 않는다.전적으로 Deque를 어떻게 사용할지는 사용자에 선택에 달려 있다. class Deque: def __init__(self): ''' 데큐를 리스트로 초기화한다. ''' self.deque = [] def isEmpty(self): ''' 데큐의 길이가 0인지를 확인한다. ''' return len(self.deque) == 0 def addFront(self, item): ''' 데큐의 Front에 item을 추가한다. ''' self.deque.append(item) def addRear(se..

[Data Structure] Queue - 이론 && ADT QueueQueue는 rear로 item이 추가되고, front로 item이 삭제된다.이러한 특징을 First In, First Out - FIFO라고 한다.중간에 점프를 뛸 수 없고 front로 갈 때까지 순서대로 기다려야만 한다.Queue의 예로 프린터에서 프린트 하는 것도 있고OS에서 스케쥴링, 키보드 타이핑치는것 등등도 Queue의 예로 볼 수 있다. class Queue: def __init__(self): ''' 리스트를 이용해서 큐를 초기화한다. ''' self.queue = [] def isEmpty(self): ''' 큐의 길이가 0인지를 확인한다. ''' return len(self.queue) == 0 def enqueue(self, item): ''' 큐의 rear에 item..

[Data Structure] Stack - 이론 && ADT Stack - 이론 && ADT스택은 새로운 아이템의 추가와 존재하는 아이템의 삭제가 동일한 위치에서 발생한다.가장 최근에 추가된 아이템은 가장 먼저 제거 될 수 있다. 이것을 Last In First Out - LIFO 라고 한다.실생활에서 스택의 예시를 많이 찾아볼 수 있다.스택은 아이템의 삽입 순서가 제거 순서와 반대이다.class Stack: def __init__(self): ''' 스택을 초기화 - 빈 리스트로 초기화 한다. ''' self.stack = [] def isEmpty(self): ''' 스택의 길이가 0 인지를 확인한다. ''' return len(self.stack) == 0 def push(self, item): ''' 스택의 마지막에 item을 추가한다. ''' self.s..

[자료구조 && 알고리즘] 버블정렬 버블 정렬비교 방법옆과 비교하고 좌측/우측이 크면 교환한다. 인접한 두 수를 비교해서 큰수를 앞/뒤로 보낸다.과정요소의 개수 - 1 번을 돌리는데,1바퀴를 돌면, 젤 큰게/작은게 가장 왼쪽/오른쪽으로 이동한다.이것을 요소의 개수 -1번 까지 돌리면 모두 정렬이 완료 된다.코드#pseudo for i in range(0,len(n)-1): #(0,n-1-i)에서 -i하는 이유는 젤 바깥쪽 루프가 1바퀴 돌 때마다, 맨마지막 부분이 정렬이 되기 때문이다. for j in range(0,len(n)-1-i): if(j > j+1): #혹은 j > j+1 교환#python n=[4,5,2,3,1] for i in range(0,len(n)-1): for j in range(0,len(n)-1-i): if..

[자료구조 & 알고리즘] 그래프 / 인접 행렬 / 인접 리스트 [자료구조 & 알고리즘] 그래프 / 인접 행렬 / 인접 리스트요약그래프Vertex, edge의 모임G = (V,E)인접 관계?이웃 관계라고도 부른다.path의 개념말 그대로 '길' 을 나타내는데, edge로 연결된 각 verte 사이에 '길'Cycle의 개념Vertex 들을 edge로 연결하다 보면, 원형으로 path가 되는 경우가 있는데, 이때 Cycle이라고 부른다.연결성위와 같은 개념들을 활용해서, edge 간의 인접 관계를 어떻게 나타낼 수 있을까?방법은 2가지로 나뉜다.인접행렬설명 및 특징그래프를 행렬로 나타낸 것을 말한다.행렬의 특정 원소를 통해서 vertex 간의 인접 관계를 알 수 있다.예를 들면, 행렬의 0,1 번째가 '1'이라면 0번째, 1번째 vertex 가 인접함을 알 수 있다.방향..

이전 1 2 다음

티스토리툴바