개발조아

완전 이진 트리의 일종 중복된 값을 허용 Max Heap 트리의 루트가 가장 큰값인 트리 Min Heap 트리의 루트가 가장 작은값인 트리 삽입 가장 끝 칸에 새로운 데이터 삽입 해당 위치부터 루트노드까지 올라가면서 종류에 맞게 값 변경 삭제 루트 노드를 제거하는 것 루트와 가장 끝칸의 노드의 값을 변경 힙의 사이즈 1 감소 루트 노드에서 다시 힙 구성 시간 복잡도 heapify 힙 구성 트리의 높이만큼 수행되므로 O(logn) build heapify O(nlogn) 원소를 하나씩 넣고 힙 구성 O(n) 모든 원소를 배열에 넣고 n/2번째 부터 힙 구성

이진트리의 일종 효율적인 탐색 가능 규칙 노드의 키는 유일해야한다 왼쪽 자식노드는 부모노드 보다 값이 작다 오른쪽 자식노드는 부모노드 보다 값이 크다 왼쪽, 오른쪽 자식 노드도 이진 탐색 트리 형태이다 탐색은 O(logn)의 시간복잡도를 갖는다 삽입 루트 노드에서 시작하여 단말 노드에 도달할 때까지 규칙에 맞게 진행하여 삽입 삭제 자식이 없을 시는 그냥 삭제 자식이 1개 있을 시 해당 자식을 올림 자식이 2개 있을 때 왼쪽자식 중 가장 큰값 또는 오른쪽 자식 중 가장 작은값을 올림

비선형 자료구조 계측적 관계를 표현한 자료구조 Node(노드) Edge(간선)으로 구성 특징 사이클이 존재하지 않는다 루트에서 한노드로 가는 경로는 유일하다 노드의 개수가 n이라면 간선은 n-1개 이다 트리 순회 전위순회(pre-order) 부모노드를 먼저 탐색 후 왼쪽, 오른쪽 자식 노드로 탐색 중위순회(in-order) 왼쪽노드를 먼저 탐색 후 부모, 오른쪽 자식 노드로 탐색 후위순회(post-order) 왼쪽노드, 오른쪽 노드 탐색 후 부모노드 탐색 레벨순회(level-order) 루트부터 계층별로 탐색 이진 트리(Binary Tree) 자식이 최대 두개인 트리 포화 이진 트리 모든 레벨이 꽉찬 트리 완전 이진 트리 왼쪽 부터 차례대로 채워진 이진트리

연속적인 메모리에 저장되지 않는 선형 자료구조 각각의 노드들이 데이터 필드와 인접한 노드에 참조하기 위한 데이터로 구성 배열 VS 연결리스트 배열과 연결리스트 선형으로 데이터를 저장하는 구조 배열 배열은 전체 길이가 고정되어 있고 사전에 길이를 알고 할당 해줘야함 탐색이 빠르다 요소를 삽입,삭제할 때 비용이 많이 듬 중간에 삽입하면 뒤로 나머지를 밀고 삽입 삭제 시 뒤에 있는 것을 모두 당겨야함 연결리스트 전체 길이를 알필요도 없고 사전에 만들어둘 필요가 없음 삽입, 삭제시 용이 삽입 시 해당 위치의 앞,뒤 노드와 연결만 시켜주면 됨 삭제 해당 위치의 앞뒤 노드를 연결 시켜주면 됨 탐색이 느리다 해당 위치에 바로 접근할 수 없어 head부터 순차적으로 접근해서 가야함 종류 노드끼리 방향을 어떻게 지정하느..

데이터를 (key, value) 쌍으로 저장하는 자료구조로 데이터를 검색할수 있다 검색시 key 값을 해시 함수를 통해 해시 값으로 바꾸고, 해시 값 으로 테이블에 접근하여 실제 데이터를 가져와 빠르게 접근이 가능하다. 해시 임의의 크기의 데이터(key)를 고정된 크기의 데이터로 변환시킨 것 해시테이블의 인덱스 해시 함수 key를 해시값, 해시 테이블의 인덱스로 변환시켜주는 것 key 값을 일정한 크기의 해시값으로 바꿔준다 충돌(collision) 해시 함수로 해시 테이블의 크기는 물리적으로 한계가 있기 때문에 같은 해시 값을 같는 경우가 발생 이처럼 해시 값이 같은 경우 충돌(collsion)이 발생 충돌 해결 Open Address 방식(개방주소법) 해시 충돌이 일어나면 다른 공간을 찾아 저장하는 것..

안정정렬 정렬 후에도 같은 데이터에 대해서는 초기 순서가 유지되는 정렬 3,2(1),2(2),1 이 있을때 오름차순으로 정렬하면 1,2(1),2(2),3 으로 2의 순서가 유지되는 정렬 삽입정렬, 병합정렬, 버블정렬 불안정 정렬 정렬 후에도 같은 데이터에 대해서는 초기 순서가 유지되지 않는 정렬 퀵정렬, 선택정렬, 계수정렬 제자리 정렬(In memory sort) 주어진 공간외에 별도의 공간이 필요로 하지 않는 정렬 Comparisons Sorting 선택 정렬(Selection Sort) 데이터를 넣을 위치를 선택 후 해당 위치에 넣을 데이터를 찾아 정렬하는 방식 오름차순 정렬 i번째 위치 선택 i~n번 위치에서 가장 작은 값 찾기 i번째 위치와 값 변경 i += 1 총 n번 수행 시간 복잡도 최소, ..

고속의 CPU와 상대적으로 저속인 주기억장치(메인메모리) 사이의 속도 개선을 위한 기억장치 CPU가 사용했던 데이터를 임시로 저장한다 이미 사용했던 데이터에 대해 재접근시 메모리 참조, 인출 과정에서의 비용을 줄인다 CPU 기억장치의 상호작용 CPU에서 주소 전달 -> 캐시에서 명령이 존재하는지 확인 Hit (존재) CPU로 명령 전달 Miss (존재하지않음) 명령어를 주기억장치에서 찾아 데이터 인출 -> 캐시에 해당 데이터 저장 -> CPU에 명령 전달 캐시의 지역성 캐시의 적중률(Hit rate)를 극대화 시키기 위해 지역성의 원리를 사용 지역성 기억장치의 모든 정보를 균일하게 접근하는게 아니라 한순간 특정 부분만을 집중적으로 참조하는 특성 시간 지역성 최근 참조한 부분은 다시 참조되는 특성 공간 지..

Demand Paging(요구 페이징) 프로그램 실행 시 전체 데이터를 메모리에 올리는 것이 아닌 필요한 것만 메모리에 올려 사용한다. 이때 필요한 페이지를 요구 페이징이라고 한다. 가상 메모리 시스템에서 많이 사용된다. 가상메모리에 데이터 올리고, 실제 필요로하는 요구 페이지를 메인메모리에 올려 사용 page fault CPU가 적재된 페이지 말고 다른 페이지가 필요할 때 page fault(페이지 부재)가 발생한다 이때 보조기억장치에서 해당 페이지를 가져오게 된다. 하지만 메모리가 꽉찼다면 페이지 교체가 이루어줘야한다. 이때 교체가 이루어지는 메모리 페이지를 victim page라고 한다 Page Reference String 연속된 페이지를 갖는 논리주소를 처리할때는 page fault가 발생하지 ..