잡다한 IT/자료구조 썸네일형 리스트형 스택, 큐 클래스 설계 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include#includeusing namespace std; class STACK{private: int top; vector st; int MAX;public: STACK() {}; ~STACK() {}; void init(); bool isEmpty(); bool isFull(); void push(); void pop();}; void STACK::init(){ top = 0; MAX = 5; s.. 더보기 퀵소트 vs 머지소트 Sorting 알고리즘을 다시 공부하면서 궁금증이 생겼다. 머지소트는 시간 복잡도가 항상 O(NlgN) 인 반면에, 퀵 소트는 시간 복잡도가 최선일때 O(NlgN) 이고, 피봇값을 최대 혹은 최소로 설정할 경우 최악으로 O(N^2) 이 생긴다. 뭐 어떤 수열을 Sorting 하느냐에 따라 다르겠지만, 일반적으로 퀵소트를 많이쓰고 빠르다고 하는데 그 이유를 알 수가 없어서 SLACK을 통해서 물어봤다. 그 답은 더보기 Sort , Search 1. 선택 정렬 (Selection Sort) 2. 삽입 정렬(Insertion Sort) 3. 버블 정렬(Bubble Sort) 4. 병합 정렬(Merge Sort) 5. 퀵 정렬(Quick Sort) - 참조 블로그=> http://mygumi.tistory.com/308 6. 이분 탐색(Binary Search) 재귀/비재귀 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610.. 더보기 연결 리스트로 완전 이진 탐색(BST) 구현 이진 탐색 트리(Binary Search Tree) - 기본적인 접근 Search()는 대소 비교를 하면서 해당 값과 같은 Node 찾기 Insert()는 대소를 비교해서 빈 자리에 Insert , Tree가 비어있을 때 예외처리. Delete()는 3가지 경우로 나눠서 접근 (삭제할 값이 없는 경우 예외처리) 1. 자식이 없는 경우 – 그냥 삭제 2. 자식이 1개인 경우 – 부모와 교환 ,자식 데이터 delete 함수로 삭제(재귀) 3. 자식이 2개인 경우 – 오른쪽에서 가장 왼쪽 값이나, 왼쪽에서 가장 오른쪽 값이랑 교환, 바꾼 값을 delete 함수로 삭제(재귀) 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 더보기 연결리스트를 통한 큐 구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114#include#include typedef struct Node { int data; Node* next;}Node; typedef struct Queue{ int size; Node* front; Node* back;}Queue; //연결리스트 큐에서 큐가 비어있을때/ 비어있지 않을 때 나.. 더보기 연결리스트를 통한 스택 구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include#include typedef struct Node { int data; Node* next;}Node; typedef struct stack { int count; Node* top;}stack; //연결리스트 스택 push 에서는 count를 생각하지 않아도 된다.void push(stack* st, int data){ Node* New = (Node*).. 더보기 링크드 리스트 구현 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816.. 더보기 배열을 이용한 스택 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include // STACK_MAX 값 설정#define STACK_MAX 100 // top 변수 선언int top;int stack[STACK_MAX]; // Init 함수로 top을 0으로 초기화void stackInit(void){ top = 0;} // top==0 이면 true 리턴, 아니면 false 리턴int stackIsEmpty(void){ return (top == 0);} // top==S.. 더보기 이전 1 2 다음
