얼렁뚱땅 Data Science

스택 (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( ) : 리스트 마지막에 괄호 안의 원소를 추가하는 연산 선형 시간이 걸리는 연산..