자료구조 & 알고리즘
1.자료구조와 알고리즘
1 자료구조(data structures) 1.1 파이썬의 기본적인 데이터 타입 문자열 (str) “This is a string” 리스트 (list) [1, 4, 3, 2] 사전 (dict) {’A’:1, ‘B’:2} 순서쌍 (tuple) 집합 (set) 등... 1.2 자료구조를 왜 알아야 하는가? 리스트 속 최대값을 찾는 max() 함수의 실행...
2.선형 배열(Linear Arrays)
선형 배열: 데이터들이 선처럼 일렬도 길게 늘어서 있는 배열파이썬에서 리스트를 활용해 구현 가능배열: 원소들을 순서대로 늘어놓은 것python에는 없는 자료형(C++, java 등 다른 언어에 존재)같은 타입의 데이터만 포함할 수 있다리스트: python에서의 원소들을
3.정렬(Sort), 탐색(Search)
복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업4,5,1,2,3,4 → 1,2,3,4,4,5sorted()내장 함수(built-in function)정렬된 새로운 리스트를 얻어냄 (반환함)해당 리스트는 달라지지 않는다sort()리스트의 메서드(me
4.재귀 알고리즘
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것생각보다 많은 종류의 문제가 재귀적으로(recursively) 해결 가능재귀: 꼬리에 꼬리를 문다는 것이진트리는 두 개의 서브트리를 자식으로 갖는데, 왼족 서브트리의 원소들은 모두 작거나 같아야 하고, 오른쪽 서브
5.알고리즘의 복잡도(Complexity of Algorithms)
시간 복잡도 (Time Complexity): 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계공간 복잡도 (Space Complexity): 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계평균 시간 복잡도 (Average Time Complex
6.연결 리스트(Linked Lists)
1 연결 리스트 Node는 Data와 Link로 이루어져 있다. Link는 다음 노드로 이어진다 Node 내의 데이터는 다른 구조로 이루어질 수 있다 문자열, 레코드, 또 다른 연결 리스트 등 맨 첫 노드와 마지막 노드를 Head와 Tail로 지정한다
7.양방향 연결 리스트(Doubly Linked Lists)
8.1 양방향 연결 리스트 한 쪽으로만 링크를 연결하지 말고, 양 쪽으로! → 앞으로도 뒤로도 진행 가능 복잡해 보이지만 막상 코딩하면 보다 간단하다 단방향 연결리스트와 다르게 마지막 노드에 대한 연산도 빨라질 수 있다 리스트 처음과 끝에 dummy nod
8.스택(Stacks)
자료(data element)를 보관할 수 있는 (선형) 구조단, 넣을 때는 한쪽 끝에서 밀어 넣어야 하고 꺼낼 때는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있다push, pop후입선물(LIFO - Last-in First-Out)초기 상태: 비어 있는 스택(empty
9.큐(Queues)
자료 (data element)를 보관할 수 있는 (선형) 구조단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고, 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있다 → enqueue & dequeue → 선입선출(FIFO First-In First-Out)
10.환형 큐(Circular Queue)
정해진 개수의 저장 공간을 빙 돌려가며 이용한다배열로 큐를 구현했을 때처럼 dequeue 후 생기는 문제를 보완하기 위해 사용된다큐가 가득 차면 더이상 원소를 넣을 수 없다 → 큐 길이를 기억하고 있어야 함 size(): 현재 큐에 들어 있는 데이터 원소의 수를 구
11.우선순위 큐(Priority Queues)
큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식운영체제의 CPU 스케줄러Enqueue할 때 우선순위 순서를 유지하도록Dequeue할 때 우선순위 높은 것을 선택→ 2번으로 하려면 dequeue할 때마다 큐 안에서 가장 높은 우선순위를
12.트리(Trees)
정점(node)과 간선(edge)을 이용해 데이터의 배치 형태를 추상화한 자료 구조뿌리(root) → 이파리(leaf)모든 노드의 차수가 2 이하인 트리재귀적으로 정의할 수 있다루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 모든 서브트리가 이진 트리)termi
13.이진 트리 (Binary Trees)
1 이진 트리 (Binary Trees) 란? 모든 노드의 차수가 2 이하인 트리 재귀적으로 정의할 수 있다 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 모든 서브트리가 이진 트리) terminal 조건: 빈 트리(empty tree)
14.이진 탐색 트리(Binary Search Trees)
1 이진 탐색 트리(Binary Search Trees) 란? 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리 중복되는 원소는 없다고 가정 배열을 이용한 이진 탐색 알고리즘과 유사하다 장점: 데이터 원소의 추가, 삭제가 용이...
15.힙(Heap)
1 힙(Heap) 이란? 최대 힙 조건이 추가된 이진 트리의 한 종류 → 이진 힙 (Binary Heap) (재귀적 정의) 어느 노드를 루트로 하는 서브트리도 모두 최대 힙 힙의 조건 루트 노드가 언제나 최댓값 또는 최솟값을 갖는다 최대