Data Science LAB

1. 그래프 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색하는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미함 -> DFS, BFS 모두 그래프를 탐색하는 방법 2. DFS (Depth - First Search) : 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 의미함 1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함 2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림 스택 (stack) 자료구조를 사용하는 것이 핵심 -> 현재 방문한 노드에 연결된 노드를 방문해야 한 방향으로 갈 수 있음 -..

시간 복잡도 : 알고리즘이 실행되는데에 걸리는 시간 (연산의 횟수) -> 주로 Big-O 표기법을 사용하여 표시 O(1) 상수 시간 O(log n) 로그 시간 O(n) 선형 시간 O(n log n) 로그 선형 시간 O(n^2) 이사 시간 O(n^3) 다차(polynomial) O(3^n) 지수 시간 O(n!) 팩토리얼 시간 아래로 갈수록 더 복잡한 알고리즘이며 수행시간이 오래 걸린다. n의 크기가 커질 수록 시간복잡도 형태 간 수행시간 차이는 더욱 커지게 된다. 자료형 별 시간 복잡도 - 리스트 - 집합 (Set) - 딕셔너리

1. Deque 정의 큐의 앞, 뒤에서 삽입, 삭제가 가능한 큐 (double-ended queue의 줄임말) 2. Deque 사용 방법 from collections import deque data = [1, 2, 3, 4, 5] d = deque(data) print(d) # deque([1, 2, 3, 4, 5]) - deque.append(item): item을 데크의 오른쪽 끝에 삽입한다. - deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다. - deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다. - deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다. - deque.extend(array..

1. sort() 함수 : 원본을 정렬 문자열은 알파벳, 가나다 순서이고 숫자는 오름차순이 기본값 num_list = [4,5,2,1] num_list.sort() print(num_list) # [1,2,4,5] str_list = ['q','d','e','a','b','가'] str_list.sort() print(str_list) # ['a', 'b', 'd', 'e', 'q', '가'] 2. sorted() 함수 정렬된 결과를 반환시키지만 원형을 변형시키지는 않음, 정렬 기준은 sort와 같음 num_list = [4,5,2,1] print(sorted(num_list)) print(num_list) # [1, 2, 4, 5] # [4, 5, 2, 1] 3. Parameter - reverse :..

1. 스택이란 ? 가장 나중에 넣은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조로 Last In First Out(LIFO) 방식, (혹은 FILO : First In Last Out) => 파이썬에서는 이미 리스트[]로 구현되어져 있음 2. 스택 기본 연산 push() 스택에 원소를 추가한다. pop() 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다. peek() 스택 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다.) empty() 스택이 비어있다면 1, 아니면 0을 반환한다. 3. 스택 라이브러리 from collections import deque dq=deque() # 덱 생성 dq.append() # 덱의 가장 오른쪽에 원소 삽입 dq.popleft() # 가장 왼쪽 원소 반..