큐(Queue) 자료(data element)를 보관할 수 있는 (선형) 구조 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 - enqueue 연산 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음 - dequeue 연산 선입선출(FIFO - First In First Out) 특징을 가지는 선형 자료구조 큐의 추상적 자료구조 구현 배열(Array)를 이용하여 구현 class ArrayQueue: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size() == 0 def enqueue(self, item): self.data.append(item) def d..
양방향 연결 리스트(Doubly Linked Lists) 한 쪽으로만 링크를 연결하지 말고, 양쪽으로! 앞으로도(다음 node) 뒤로도 (이전 node) 진행 가능 Node의 구조 확장 class Node: def __init__(self, item): self.item = item self.prev = None self.next = None 리스트 처음과 끝에 dummy node를 둔다. 데이터를 담고 있는 node들은 모두 같은 모양 class Node: def __init__(self, item): self.item = item self.prev = None self.next = None class DoubleLinkedList: def __init__(self, item): self.nodeCou..
추상적 자료구조(Abstract Data Structure) Data(정수, 문자열, 레코드...) A set of operations(삽입, 삭제, 조회, 정렬, 탐색...) 기본적 연결리스트 노드는 데이터와 링크로 이루어진다. 노드 내의 데이터는 다른 구조로 이루어질 수 있음 리스트의 맨 앞을 Head, 맨 뒤를 Tail이라고 한다. 노드가 몇개 있는지까지 기록해두면 편하다. 링크드 리스트 구현 노드 class Node: def __init__(self, item): self.data = item self.next = None class LinkedList: def __init__(self): self.nodeCount = 0 self.head = None self.tail = None 연산 정의 특..
정렬(sort) 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업. 📌 정렬 알고리즘에는 여러 종류가 있다. Python 의 리스트 (list) 를 이용한다면, 직접 정렬 알고리즘을 구현할 필요가 없다. 이미 리스트 (list) 에 내장된 정렬 기능이 있다 sorted() 내장 함수(built-in function) 정렬된 새로운 리스트를 얻어냄 L = [3, 8, 2, 7, 6, 10, 9] L2 = sorted(L) print(L2) # [2, 3, 6, 7, 8, 9, 10] print(L) # [3, 8, 2, 7, 6, 10, 9] sort() 리스트의 메서드(method) 해당 리스트를 정렬함 L = [3, 8, 2, 7, 6, 10, 9] L2 = sorted(L) pri..
알고리즘(algorithm)이란? [사전적 정의] 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합 [프로그래밍] 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택 해결하고자 하는 문제에 따라(응용 종류와 범위에 따라) 최적의 해법은 서로 다르다! -> 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 함 1강 실습: 리스트 원소 두 개의 합 구하기 def solution(x): return x[0] + x[-1] 배열(Arrays) 같은 종류의 데이터가 줄지어 늘어서있는 자료 구조를 의미한다. 파이썬에서는 리스트(List) 자료구조가 이와 비슷하게 사용된다. 리스트(배열) 연산 원소 덧붙이기 L = ['Bob', 'Cat', 'Spam', 'Programmers'] L.a..
정의 이진 트리의 한 종류(이진 힙 - binary heap) 루트 노드가 언제나 최댓값 또는 최솟값을 가짐 최대 힙(max heap), 최소 힙(min heap) 완전 이진 트리여야 함 📌 재귀적으로도 정의가 가능하다. max heap의 경우 어느 노드를 루트로 하는 서브트리인 경우에도 모두 최대 힙의 조건을 만족한다. 이진 탐색 트리와의 비교 원소들은 완전히 크기 순으로 정렬되어 있는가? 이진 탐색 트리 O, 힙 X 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? 이진 탐색 트리 O, 힙 X 부가 제약 조건은 어떤것인가? 힙은 이진 탐색 트리에 비해 완전 이진 트리여야 한다는 부가 제약 조건을 갖고 있다. 최대 힙(Max Heap)의 추상적 자료 구조 연산의 정의 __init__() : 빈 최..
이진 트리의 추상적 자료구조 연산의 정의 size() - 현재 트리에 포함되어 있는 노드의 수를 구함 depth() - 현재 트리의 깊이(또는 높이: height)를 구함 순회(traversal) 이진 트리의 구현 - 노드(Node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None class Node: def __init__(self, item): self.data = item self.left = None self.right = None def size(self): l = self.left.size() if self.left else 0 r = self.right.size() if self...
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/142085 문제 풀이) heap을 이용해 풀수 있었다. 문제 풀이 과정은 다음과 같다. enenmy list의 원소들을 순서대로 탐색하며 다음과 같은 절차를 밟는다. 1) n(내가 보유하고 있는 병사수)가 enenmy[i](i번째 스테이지 적의 수) 수보다 많다면 내가 보유하고 있는 병사수에서 빼준다. 이러면 특정 스테이지에서 무조건 막히게 되있는데 이때 최대힙을 이용한다. 최대힙에서 heappop()을 하게 되면 내가 지나온 스테이지중 가장 많은 적의 수가 나오게 되있다. 힙에는 내가 스테이지를 클리어하며 소모된 병사의 수(=enemy수)가 저장되어 있다고 가정한다. 2) 이때 부터 ..
