CS 썸네일형 리스트형 탐색(Search) * 보간 탐색(Interpolation Search) 이진 탐색처럼 중앙에서 탐색을 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작 // s는 찾고자 하는 데이터의 인덱스 값 // 찾는 데이터의 값 arr[s]를 x라 하면 * 이진 탐색 트리 이진 트리에 데이터의 저장 규칙을 더해놓은 것 1) 이진 탐색 트리의 노드에 저장된 키는 유일하다. 2) 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. 3) 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다. 4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. * AVL 트리 AVL 트리는 노드가 추가될 때, 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리이다.. 정렬(sorting) * 버블 정렬 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식 두 데이터를 비교하여, 정렬순서상 위치가 바뀌어야 하는 경우 두 데이터의 위치를 바꿔나감 "정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내기" 시간복잡도 : O(n^2) * 선택 정렬 "정렬 순서상 가장 앞서는 것을 선태개서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓음" 시간복잡도 : O(n^2) * 삽입 정렬 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해 가면서 정렬을 진행 "정렬 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상" "삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면.. 힙(Heap) * 우선순위 큐 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옴 enqueue : 우선순위 큐에 데이터를 삽입하는 행위 dequeue : 우선순위 큐에서 데이터를 꺼내는 행위 - 구현 방법 1) 배열을 기반으로 구현 단점 : 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 앞으로 당기는 연산 수반 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있음 2) 연결 리스트를 기반으로 구현 단점 : 삽입의 위치를 찾기 위해 첫 번째 노드에서부터 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있음 3) 힙(heap)을 이용하는 방법 - 시간 복잡도 배열 기반 데이터 저장 O(n) / 삭제 O(1) 연결 리스트 기반 데이터 저.. 트리(Tree) * 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조 * 트리 관련 용어 - 노드(node) : 트리의 구성요소에 해당하는 A,B,T,... 등과 같은 요소 - 간선(edge) : 노드와 노드를 연결하는 연결선 - 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 A와 같은 노드 - 단말 노드(terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 K,G,J,H와 같은 노드 - 내부 노드(internal node) : 단말 노드를 제외한 모든 노드로 A,B,... 등과 같은 노드 * 서브 트리(sub tree) * 이진 트리(binary tree) - 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어짐 - 나뉘어진 두 서브 트리도 모.. 큐(queue) - FIFO(First-in First-out) - 삽입과 삭제가 서로 다른 곳에서 이뤄지는 리스트 - 삽입은 rear에서, 삭제는 front에서 - 원형 큐 - 순차 큐 예제 코드 스택(stack) - LIFO(Last in First out)- 마지막에 삽입한 원소를 가장 먼저 삭세하는 리스트- top에서 삽입과 삭제가 일어남 * 연결리스트 스택 - 예제 코드 - 실행 결과 순차 자료 구조 1) 배열- 배열이란? 같은 형의 자료를 여러 개 저장할 수 있는 자료형으로 순서가 있는 원소들의 모임- 배열의 원소 : 기본 자료형, 참조형을 가진 자료 - 배열의 생성int intarray[]; int[] intarray2;char chararray[]; - 배열 객체 생성 예intarray = new int[3]; int[] L = {1,2,3,4,5,6};int[] month = new int[12]; - 배열 a와 배열 b의 각 원소를 더하여 배열 c에 저장하고 각 배열의 원소 출력 프로그램 - 실행 결과 2) 행렬- n개의 행과 m개의 열로 행렬을 구성할 때, n × m 으로 표현- 행렬의 총 원소 수는 n * m 개- 정방 행렬(square matrix) : n과 m이 같은 것- 희소 행렬(.. 성능 분석과 측정 - 캡슐화 : 정보 은닉- 추상화 : 데이터 객체의 명세와 구현을 분리하는 것- 데이터 타입 : 객체들과 이들 객체들에 대해 동작하는 연산들의 집합(int, 산술연산자)- 추상 데이터 타입(ADT) : 기능의 구현을 나타내지 않고 정의만 한 것 - 복잡도(complexity) : 프로그램은 실행하는 하드웨어에 따라 실행 시간이 다르므로 컴퓨터에 관계없이 시간과 공간을 추산하는 것 시간 복잡도, 공간 복잡도- 성능 평가 : 성능 분석(사전 예측), 성능 측정(사후 검사) (1) 성능 분석 - 공간 복잡도 : 필요한 공간의 크기, 고정공간과 가변공간 - 시간 복잡도 : 프로그램이 실행될 때 피료한 실행분의 실행 횟수(count문 삽입, 실행문의 빈도수 계산) - 성능 분석을 위한 점근 표기법 * 점근 표기법.. 이전 1 2 3 다음
