얼렁뚱땅 Data Science

큐(Queue) 자료를 보관할 수 있는 선형 구조. 즉, 선입선출 (FIFO - First in First Out)의 특징을 가지는 선형 자료구조 넣을 때에는 한 쪽 끝에서 넣어야함 -> enqueue 연산 꺼낼 떄에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음 -> dequeue 연산 큐의 추상적 자료구조 구현 (1) 배열 (2) 연결리스트 이용해 구현 연산의 정의 size() - 현재 큐에 들어있는 데이터 원소 수를 구함 isEmpty() - 현재 큐가 비어있는지 판단 enqueue(x) - 데이터 원소 x를 큐에 추가 dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음) 배열로 구현한 큐의 연산 복잡도 연산 복잡도 ..

중위 표기법 (infix notation) 우리가 일반적으로 사용하는 표기법으로 연산자가 피연산자들의 사이에 위치 (A + B) * (C + D) 후위 표기법 (postfix notation) 연산자가 피연산자들 뒤에 위치 A B + C D + * 스택을 이용하여 중위 표현식을 후위표현식으로 바꾸기 중위 표현식 후위 표현식 A * B + C A B * C + A + B * C A B C * + A + B + C A B + C + 괄호의 처리 여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop 연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록 여는 괄호의 우선순위는 가장 낮게 설정 중위 표현식 후위 표현식 (A + B) * C A B + C * A * (B + C) ..

스택 (Stacks) 한 쪽 끝에서 데이터를 push 하거나 pop해야한다. 즉, 후입선출 (LIFO : Last In First Out) 특징을 가지는 선형 자료구조 스택에서 발생하는 오류 비어있는 스택에서 데이터 원소를 꺼내려 할 때 : Stack underflow 꽉 찬 스택에 데이터 원소를 넣으려 할 때 : Stack overflow라고 부름 스택의 추상적 자료구조 구현 배열 Python 리스트와 메서드를 이용해 구현 연결리스트 양방향 연결리스트를 이용해 구현 연산의 정의 size() : 현재 스택에 들어있는 데이터 원소의 수를 구함 isEmpty() : 현재 스택이 비어 있는지를 판단 push() : 데이터 원소 x를 스택에 추가 pop() : 스택의 맨 위에 저장된 데이터 원소를 제거 및 반환..

양방향 연결 리스트 (Doubly Linked Lists) 한 방향으로만 연결하는 것이 아닌 양쪽으로 연결하는 리스트. 이전 노드, 다음 노드 방향으로 진행이 가능하다. Node 클래스의 생성자에 self.prev를 추가 설정해줌. 리스트 처음과 끝에 dummy node를 둔다 --> 데이터를 담고 있는 노드들은 모두 같은 모양을 가진다. 과제 1: 양방향 연결리스트 역방향 순회 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail..

연결 리스트 (Linked list) node에는 data와 next node의 link를 담고 있다. 노드 내의 데이터는 다른 구조로 이뤄져 있을 수 있음 리스트의 맨 앞, 리스트의 맨 끝, 노드의 개수를 기록해두면 좋다. class Node: def __init__(self): self.data = data self.next = None class LinkedList: def __init__(self): self.nodeCount = 0 self.head = None self.tail = None 연산 정의 특정 원소 참조 (k번째) def getAt(self, pos): if pos self.nodeCount: return None i = 1 curr = self.head while i < pos:..

알고리즘의 복잡도 (Complexity of Algorithm) 문제를 해결하는데 얼마만큼의 자원이 필요한가의 의미를 가지고 있다. 시간 복잡도 (Time complexity) : 문제의 크기와 이를 해결하는데 걸리는 시간과의 관계 평균 시간 복잡도 (Average time complexity) : 임의의 패턴의 경우 소요되는 시간의 평균 최악 시간 복잡도 (Worst-case time complexity) : 가장 시간이 많이 걸리는 패턴의 경우 소요되는 시간 공간 복잡도 (Space complexiry) : 문제의 크기와 이를 해결하는데 드는 메모리와의 관계 Big-O Notation 점근 표기법 (Asymptotic notation) 중 하나 입력의 크기가 n 일때, O(log n) - 입력의 크기..

재귀 알고리즘 (Recursive Algorithm) 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방법 재귀 알고리즘은 대부분 iterative version과 recursive version 모두 구현할 수 있다. Recursive version은 함수를 호출하는데 드는 시간이 드므로 iterative version이 더 효율적이다. 하지만 사람이 생각하는 방식대로 동작하는 경우가 많아 유용할때도 있다. Ex) Recursive combination 함수 파스칼의 삼각형 : \( _{n}\mathrm{C}_{m} = _{n-1}\mathrm{C}_{m} + _{n}\mathrm{C}_{m-1} \) def combi(n, k): if (n == k): return 1 elif (k == 0..

3강 : 배열 - 정렬과 탐색 1. 정렬 (Sorting) sorted() : 파이썬 내장함수, 정렬된 새로운 리스트 반환 sort() : 리스트 메서드, 해당 리스트 정렬 만약, 리스트가 string으로 이뤄져 있다면 알파벳 순서 따라서 정렬된다. 정렬 기준을 사용자가 직접 정하고 싶을때는 key 파라미터를 이용하여 정렬을 해준다. EX1) x의 길이를 기준으로 리스트를 정렬하여라. sorted(L, key = lambda x: len(x)) EX2) L이 name과 score로 이뤄진 딕셔너리가 든 리스트라 할 때, score를 기준으로 정렬하여라. L.sort(key = lambda x: x['score'], reverse = True) 2. 탐색 (Searching) 선형탐색 (Linear Sea..

Q. 우리는 왜 알고리즘과 자료구조를 배울까? 해결하고자 하는 문제에 따라 최적의 해법이 다 다르다. 자료구조 / 알고리즘을 통해 빠르고 효율적인 답을 얻을 수 있다. 알고리즘 [사전적 정의] 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합 [프로그래밍] 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택 선형 배열 (Linear Arrays) Python에서의 리스트는 다른 프로그래밍 언어들과는 달리 다양한 타입들의 원소를 가질 수 있다. 상수 시간이 걸리는 연산: 리스트의 길이와 상관없이 시간이 걸린다. (리스트 길이와 상관없이 수행됨) .pop( ) : 리스트 마지막 원소를 꺼내는 연산 .append( ) : 리스트 마지막에 괄호 안의 원소를 추가하는 연산 선형 시간이 걸리는 연산..

이번에 데이터 마이닝 수업 과제를 하면서 프로그램을 돌리려는데 제가 이미 설치한 모듈이 실행이 안되더라구요. 문제를 해결하기 위해 열심히 구글링을 하다가 원인을 알아냈는데요, 문제는 모듈이 설치된 python interpreter가 달랐기 때문입니다! pip install 을 이용해 라이브러리를 다운받을 때 다음과 같이 위치가 뜹니다. (저는 이미 깔려있어서 벌써 설치가 되어있다는 문구가 나옵니다.) 위에서 찾아낸 인터프리터를 vscode에서 설정을 해줘야겠죠? vscode에서 인터프리터를 바꾸는 방법은 두 가지 입니다. 1. ctrl + shift + p 를 누른다. 2. Python : select intepreter 3. 해당 인터프리터를 선택한다. 1. vscode 좌측 하단에 해당 사진 부분을 ..