본문 바로가기

Algorithm

 (17)
자료구조 Graph == Graph 기본 개념 정리 == - Direct Graph - vertax 와 edge 가 있으면 Graph 라고 한다 - 방향성이 있으니 Direct Graph - Undirect Graph - 방향성이 없다. - Weighted Graph - edge에 cost가 있을 때 - Vertex List vertaxList = ['0', '1', '2', '3', '4', '5'] - Edge List edgeList = [(0,1), (1,0), (1,2), (1,3), (2,1), (3,1), (3,4), (4,3), (4,5), (5,4)] - Undirect graph 이니 양쪽 방향 다 있지. - Adjacency List adjacencyList = [[1], [0,2,3], [1], [1,..
자료구조 Binary_Search_Tree == Binary_Search_Tree(이진트리) ==- 매우 중요하다!!- Search, Delete, Insert : O(log n) - performance 좋다!! - 구현에 있으서 DP나 Recursion등을 물어볼 수 있기 때문에 이해하고 있어야 한다!! - Binary Search Tree - The left sub-tree of a node has a key less than or equal to its parent node's key. - The right sub-tree of a node has a key greater than or equal to its parent node's key. - Node- node들이 연결된 것이 tree 이다!! Class Node: def __init..
자료구조 Heap / Heap_Sort == Heap ==- Heap Tree - Root 값에 따라서 max heap과 min heap으로 나뉜다.- A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types: Min-heap, Max-heap. - heap의 특성은 탁 1개이다. parent node가 child node 보다 크면 heap 이다! - Heapify, 일반적인 tree를 heap-tree로 바꾸는 것을 말한다!! def heapify(a, size): p = (size//2) -1 # 자식노드가 있는 노드부터 보기 위해서!! while p>=0: siftdown(a,p..
자료구조 Linked_list ==Linked_list(node들이 link된 자료구조이다)==- Node class Node: def __init__(self, item): self.val = item self.next = None - LinkedList = LinkedNode - Add def add(self, item): cur = self.head while cur.next is not None: cur = cur.next cur.next = Node(item) - Print def printlist(self): cur = self.head while cur is not None: print(cur.val) cur = cur.next - Remove def remove(self, item): if self.head.val ==..
자료구조 Queue / Stack == Queue(FIFO, First In First Out) == - Enqueue def enqueue(self, item) : self.item.insert(0,item) - Dequeue def dequeue(self, item): self.item.pop - Queue Example- Print job queue- BFS(Breadth First Search) == Stack(LIFO, Last In First Out) ==- Push def push(self,item): if len(self.items) < self.max: self.items.append(item) else: print("overflow") - Stack Overflow stack 메모리의 최대치를 넘어서 push 할 수 없..
Sorting (정렬) Bubble sort (거품정렬)- performance : O(n^2) - performance 안좋지..- space complexity : O(1) - swapping을 위한 공간 1개 필요 - 인접한 두개의 자료를 비교해서 차순에 맞게 정렬하는 작업을 (자료개수-1) 번 만큼 반복한다.- 뒤부터 채워준다. [4, 3, 1, 2] [3, 4, 1, 2] [3, 1, 4, 2] -------------[3, 1, 2, 4] [1, 3, 2, 4] [1, 2, 3, 4] -------------[1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3, 4] Selection Sort (선택정렬)- Worst case performance : O(n^2)- Best case performance :..
Big-O notation / Time Complexity / Space Complexity - Big-O notation은 알고리즘의 performance를 이야기 할 때 좋은 방법이다. O(1) < O(log n) < O(n)
도화지를 차지하는 노트의 넓이 구하기 Q. 100 x 100 도화지 위에 10 x 10 노트를 중복 해서 놓는다. 그때 노트가 차지하고 있는 넓이를 구하시오. 단, 노트는 도화지와 직각 하도록 놓으며, 도화지의 끝 부분과 정수 배 만큼 떨어져 있게 된다. - 입력 조건 1 -- 총 테스트 수 3 -- 이번 테스트의 노트 수 3 5 -- 첫번째 종이의 (도화지 왼쪽 변과 노트 왼쪽 변 거리, 도화지 아래쪽 변과 노트 아래쪽 변 거리) 15 7 -- 두번째 노트의 (이하 동문) 5 3 -- 세번째 노트의 (이하 동문) - 출력 조건 => 각 테스트에 대하여 노트가 차지하는 넓이를 return 하시오. 236 - 풀이 !! 문제에서 주어진 조건들을 잘 분석하는 것이 중요하다. 단순한 카운팅 문제로 풀 수 있다... for문으로.. import j..
반응형

티스토리툴바