문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion return ["leo", "kiki..
이진 탐색 트리 이진 탐색 트리란? - 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 - 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 - 이진 탐색 알고리즘과 비슷함 (이진 탐색 알고리즘 : 이미 정렬된 선형 배열을 대상으로 절반씩 잘라가면서 찾고자 하는 원소를 탐색) - 중복 데이터(원소) 는 없는 것으로 가정 이진 탐색 트리 삽입 연산 구현해 보기 - 연산의 정의 insert(key, data) - 트리에 주어진 데이터 원소를 추가 remove(key) - 특정 원소를 트리로부터 삭제 lookup(key - 특정 원소를 검색 (Ologn) inorder() - 키의 순서대로 데이터 원소를 나열 min(), max() - 최대,..
이진 트리의 넓이 우선 순회 넓이 우선 순회(Breadth First Trabersal) 원칙 - 수준(level)이 낮은 노드를 우선으로 방문 - 같은 수준의 노드들 사이에는, 부모 노드의 방문 순서에 따라 방문, 왼쪽을 먼저 방문 한 노드를 방문했을 때, 나중에 방문할 노드(자식노드) 순서를 기록해 둬야 함 (큐를 이용해야 함) 넓이 우선 순회 알고리즘 구현해보기 알고리즘 순서 1. traversal에 빈 리스트, q에 빈 큐를 초기화 2. 빈 트리가 아니면, root node를 큐에 추가 (enqueue) 3. q가 비어 있지 않는 동안 3.1. q에서 원소를 추출 및 node에 저장 (dequeue) 3.2. node를 방문처리 (traversal에 append) 3.3. node의 왼쪽, 오른쪽..
트리(trees) 트리란? - 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조 - 최상단은 root node, 최 하단은 leaf node, 중간에는 내부 노드(internal nodes)라고 부름 이진 트리(Bynary Trees) 연산의 정의 size() - 현재 트리에 포함되어 있는 노드의 수를 구함 depth() - 현재 트리의 깊이 (또는 높이; height)를 구함 traversal - 순회 넓이 우선 순회 (breadth first traversal) 깊이 우선 순회 (depth first traversal) - 중위 순회 : left subtree -> 자기 자신 -> right subtree - 전위 순회 : 자기 자신 -> Left subtree -..
우선순위 큐(Priority Queues) 특징 - 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 - 대표적으로 운영체제의 CPU 스케줄러가 있음 - Enqueue(큐 삽입) 할 때 우선순위 순서를 유지하도록 하는것이 Dequeue보다 유리함 - 연결 리스트를 활용하는것이 더 유리함 (중간에 데이터를 삽입하는일이 빈번함) 양방향 연결 리스트를 이용해 우선순위 큐 구현해보기 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..
환형 큐 - 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 자료구조 - 큐가 가득 차면 더 이상 원소를 넣을 수 없음 (큐 길이를 기억해 활용해야 함) - 저장 공간을 한정하여 공간 낭비를 줄일 수 있음 환형 큐 구현해보기 - 연산의 정의 size() - 현재 큐에 들어 있는 데이터 원소 수 구하기 isEmpty() - 현재 큐가 비어 있는지 판단 isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단 enqueue(x) - 데이터 원소 x를 큐에 추가 dequeue() - 큐의 맨 앞에 저장된 데이터 원소 제거 (또한, 반환) peek() - 큐 맨 앞의 저장된 데이터 원소 반환 (제거x) class CircularQueue: def __init__(self, n): self.maxCount =..
