Kyongineer

Mergesort vector를 사용해 구현한 병합정렬이다. // sort.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다. // #include "pch.h" #include <iostream> #include <vector> using namespace std; void merge(vector<int>& v, int left, int right, int mid) { vector<int> ret; int l = left, mnext = mid + 1, copy=0;...

BFS python에서 bfs를 구현했다. 방문순서 : 깊이1 - 깊이2 - 깊이3 깊이1 A 깊이2 B C 깊이3 D E F import queue #graph표현 방식으로는 인접리스트와 인접행렬이있다. #노드개수에 비해 엣지 개수가 훨씬 적은 그래프라면 인접 행렬보다는 인접리 #스트를 사용하여 탐색하는게 효율적이다. graph = {'A': set(['B', 'C']), 'B': set(['A', 'D', 'E']), 'C':...

MinHeapsort 파이썬에서 작은순서대로 나열하는 최소힙을 구현하였다. class minheap: def __init__(self): self.lst = [None] def __init__(self,a): #리스트를 삽입 self.lst=[None]+a[:] #idx 0은 안쓸거라서 None포함 for i in range(len(self.lst)//2,0,-1):#자식이 하나라도 있는 마지막 부모의 index가 len/2 self.heapify(i) def heapify(self,i): left = self.leftchild(i) right = self.rightchild(i) small = i if left <=len(self.lst)-1 and self.lst[left]<self.lst[small]: small...

Quicksort c++의 vector를 사용해 구현한 퀵정렬이다. pivot은 random으로 정해야 복잡도가 좋지만 left로 설정했습니다. 퀵정렬은 divide and conquer방식입니다. 매우 빠른 수행속도를 가졌습니다. 시간복잡도 : O(log2n) 공간복잡도 : O(logn) ​ Divide(분할) : pivot값을 기준으로 2개의 부분집합으로 나눈다. ​ Conquer(정복) : 부분집합의 원소들 중에서 ​ (pivot보다작은 값들) , (pivot보다 큰 값)으로 정렬한다. 부분집합의...

Linked list Node(class)설계방식 data와 next(다음 Node를 가리키는 포인터)로 이루어져 있다. 생성자의 parameter를 잘 설정해야 한다. #include <iostream> using namespace std; class Node { friend class LinkedList; private: int data; Node *next; public: Node(int tmp, Node *n) { data = tmp; next = n; } Node() { data = 0; next...