전체 글68 Chapter04 트리 알고리즘 4.1 트리 ADT 운영체제 파일 시스템 HTML, XML을 다룰때 쓰는 DOM 검색엔진, 데이터베이스 4.1.2 트리의 구성요소 뿌리 가지 잎 부모노드 : 바로 하위 노드가 자식노드 자식노드 : 바로 상위 노드가 부모노드 형제노드 : 한 부모 밑에서 태어난 노드 경로 : B-D-F는 B에서 F까지의 경로 경로의 길이 : 2 노드의 깊이 : 뿌리노드에서 해당노드까지 이르는 경로의 길이(B가 뿌리면 F의 깊이는 2) 레벨 : 깊이가 같은 노드의 집합 트리의 높이 : 가장 깊은 곳에 있는 잎의 노드까지의 깊이 차수 : 그 노드의 자식 노드 개수 트리의 차수 : 트리 내에 있는 노드들 중에 자식노드가 가장 많은 노드의 차수 4.2 이진트리 하나의 노드가 자식노드를 2개 까지만 가질 수 있는 트리, 즉 노드의 .. 2023. 4. 7. Chapter11 알고리즘 성능 분석 11.1.1 알고리즘 성능측정기준정확성 : 정확하게 동작하는가?작업량 : 얼마나 적은 연산을 수행하는가? (정렬 : 비교횟수, 탐색 : 거치는 노드개수)메모리 사용량 : 얼마나 적은 메모리를 사용하는가?단순성 : 얼마나 단순한가? 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가? 알고리즘 수행시간최악의 경우 O평균의 경우 Omega최선의 경우 Theta 재귀 알고리즘의 수행시간 팩토리얼을 재귀 방정식으로 나타내면 1 (n=0,n=1) f(n)=f(n-1)*n (n>1) int RecurrenceSum( int Data[], int SizeOfData) { if(SizeOfData==1) return Data[0]; else return RecurrenceSum(&Data[1], SizeOf.. 2023. 4. 7. 5. java 필드, static field math : java가 제공해주는 클래스 사용하려면 API를 봐야 한다. field : static double method : 엄청 많음. static이 붙어있다? : 인스턴스를 만들 필요가 없다. 필드와 메소드 모두 static하기 때문이다. 모든 메소드에 static이 붙어있다. 따라서 math 클래스 사용할 때는 인스턴스를 만들면 안된다. 만약에 클래스 안에 아무런 메소드를 쓰지 않으면 public 클래스명(){} 라는 생성자가 컴파일할 때 자동으로 만들어진다. 그러나, 만약 해당 클래스 내부 외에 다른 클래스에서 인스턴스를 못 만들게 하려면 생성자를 private으로 만들면 된다. private 클래스명(){} Math클래스를 만든 사람은 메모리를 절약할 수 있도록 만든것. 클래스 메소드 vs .. 2023. 4. 5. chapter02 자료구조 스택 2.1.1 스택의 개념 활용도가 높은 자료구조 (아래서는 자료구조를 말하지만 메모리에서) 지역변수는 스택에 할당된다. 요소의 삽입과 삭제가 한쪽 끝에서만 이루어진다 스택의 주요기능 : Push (삽입), Pop (제거) 2.2 배열로 구현하는 스택 각 노드를 동적으로 생성하고 제거하는 대신 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성한다. (미리 메모리 용량을 정해줘야 함…) 그리고 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산을 수행한다. (아래에서는 다르지만, 생성 함수에서 바로 스택의 주소를 반환하면 포인터변수를 선언함과 동시에 값을 삽입할 수 있다.) #include #include //배열기반으로 구현되는 스택의 노드 typedef int ElementType.. 2023. 3. 27. chapter01 자료구조 리스트 (c언어) 1.1.1. 리스트의 개념 헤드 : 첫번째 노드 테일 : 마지막 노드 리스트의 길이 : 헤드부터 테일까지의 노드 개수 갖춰야할 연산 : Append(추가), Insert(삽입), Remove(제거), GetAt(반환) 1.1.2 리스트와 배열 비교 배열 : 배열의 크기를 지정해 줘야 하고 생성한 후에 그 크기를 변경할 수 없다. 리스트 : 배열 처럼 집합 보관 기능을 가지면서도 크기를 바꿀 수 있는 자료구조 1.2 링크드 리스트 구조 데이터 다음 노드를 가리키는 포인터 구현 노드를 표현하는 방법 : 구조체로 나타낼 수 있다. #include typedef int ElementType; struct Node{ ElementType Data; //데이터 struct Node* NextNode; //다음 노드.. 2023. 3. 27. chapter00 알아두면 쓸 데 있는 자료구조와 알고리즘 1. 자료구조 자료구조 : 컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터 보관 방법과 데이터에 관한 연산의 총체 단순 자료구조 : int, char 등등 복합 자료구조 선형 : 데이터 요소를 순차적으로 연결하는 자료구조 배열 링크드리스트 스택 큐 힙 비선형 : 데이터 요소를 비순차적으로 연결하는 자료구조 트리 그래프 ADT (Abstract Data Types) 추상데이터 형식 자료구조가 갖춰야 할 일련의 연산 c언어로 표현하면 함수 ADT가 청사진을 제공하면 자료구조는 이를 구현한다. 예를 들어 리스트 구현(배열을 이용하여)할 때 리스트의 길이 : 배열의 길이 시작노드 : 배열의 첫 요소 마지막 노드 : 배열의 마지막 노드 현재노드 : 현재 요소의 인덱스 여기에 탐색/추가/삽입/수정/삭제 .. 2023. 3. 23. 이전 1 2 3 4 5 6 7 8 ··· 12 다음