노아론 블로그

완전검색 Big-O복잡도의 점근적 상한 표기가장 느리면 이 정도 걸린다Big-Omega복잡도의 점근적 하한 표기최소한 이 시간만큼은 걸린다 Big-Theta빅오와 빅오메가가 같을때 표기 f(n) = 2n^2 + 8n + 3 = O(n^2) = C(n^2)f(n) = Theta(n^2) f(n)은 n이 증가함에 따라 n^2과 동일한 증가율을 가진다 라는 의미 비트연산 프로세스 성능 향상 위해 => 주소버스가 4의 배수형태의 주소만 허용 어떤 객체(byte)가 4의 배수형 주소에 있지 않다면메모리 접근을 2번 해야 한다. 변수 별 메모리 주소 번지 패턴1byte 형 : 모든 주소 번지에 기록 가능2byte 형 : 2byte boundary에 정렬4byte 형 : 4byte boundary에 정렬Double ..

PS 2018. 7. 19. 21:07

부분집합 생성 #include void main(void) { int i,j; int arr[] = {3,6,7,1,5,4}; int n = sizeof(arr)/sizeof(arr[0]); // n: 원소 갯수 for(int i=0;i

PS/자료구조 2018. 3. 12. 14:34

큐 구현 큐를 통한 미로찾기(최단거리) 하나의 큐를 만든다. 위치 (0,0)은 이미 방문한 위치임을 표시 큐가 빌 때까지 4를 반복한다. 1. 큐에서 하나의 위치p를 꺼낸다. 2. p에서 한 칸 떨어진 위치들 중에서 이동 가능하면서 아직 방문하지 않은 모든 위치들을 방문된 위치임을 표시하고 큐에 넣는다. 3. 만약 그 위치가 출구라면 종료한다. Queue queue = create(); Position cur; cur.x=0; cur.y=0; enqueue(queue,cur); maze[0][0]=-1; bool found=false; while(!is_empty(queue)) { Position cur=dequeue(queue); for(int dir=0;dir

PS/자료구조 2018. 1. 17. 12:21

큐 구현 큐 연결리스트 구현 Front(삭제) 가 오른쪽에 위치하면 삭제를 할때의 이전노드를 매번 알고있어야하므로 불편함. 삽입을 위해선 마지막노드(Rear)의 주소를 알아야 함. 큐 공간에서 front rear size 를 저장해둠 연결리스트를 통한 큐 구현 #include #include #include typedef int Item; typedef struct queue_type *Queue; Queue create(); void destory(Queue q); void make_empty(Queue q); bool is_empty(Queue q); void enqueue(Queue q,Item i); Item dequeue(Queue q); Item peek(Queue q); int get_siz..

PS/자료구조 2018. 1. 16. 15:06

스택 구현 스택, 배열로 구현 #include #include #include #include #define INIT_CAPACITY 100 typedef int Item; typedef struct stack_type *Stack; Stack create(); void destroy(Stack s); void make_empty(Stack s); bool is_empty(Stack s); bool is_full(Stack s); void push(Stack s,Item i); Item pop(Stack s); Item peek(Stack s); struct stack_type{ Item *contents; int top; int size; }; static void terminate(const char..

PS/자료구조 2018. 1. 15. 14:19