728x90 Lecture/Algorithm4 이진 트리의 표현 포화 이진 트리(perfect binary tree) - 전체의 노드의 개수 구하는 공식: 2^k -1 => 여기서 k은 트리의 높이를 대입하면 된다. - 노드에 번호를 부여하는 방법은 왼쪽에서 오른쪽으로 번호를 붙이면 된다. 완전 이진 트리(complete binary tree) - 완전 이진 트리는 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽에서 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다. 트리 표현 - 괄호 표현법 - 트리를 텍스트 상으로 표현하는 방법으로 괄호를 사용한 방법이다. *완전 이진 트리가 아님이라는 트리를 참고해서 괄호로 표현해 보자 (1(2(4)(5) 3()(6))) 트리 표현 - 배열 표현법 - 노드 i의 부모 노드 인덱스 =.. 2023. 10. 16. 이진 트리 트리의 특징: 노드 사이의 연결 관계가 계급적인 구조를 가진다. 이진 트리의 순회 방법 전위 순회(preorder traversal): root B C 중위 순회(inorder traversal): B root C 후위 순회(postorder traversal): B C root 전위 순회: root -> b -> c 순으로 크게 생각을 하고 b의 묶음으로 들어가서 2 -> 4 다음에 왼쪽 자식이 없으면 오른쪽으로 넘어간다. 이렇게 생각을 한다. 이런 식으로 반복을 한다면 2-> 4-> 7-> 8-> 9 형태의 b 묶음이 나온다. 다음으로 c 묶음이다. c도 마찬가지로 3-> 5-> 6이 된다. 1 -> 2 ->4 ->7- 8 -> 9 -> 3-> 5 ->6 명심하자! root(1)는 처음이다! 중위 순.. 2023. 10. 15. 연결 리스트 연결 리스트 기본 구조 자료 + 링크(포인터) 연결리스트 동적 자료구조라고 불린다. 그러므로 크기를 정할 필요가 없다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않다. 배열과의 비교 장점: 배열의 크기가 고정되는 것에 반하여, 연결리스트는 자료의 특성에 따라서 유동적이다. 단점: 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 때문에 임의로 접근하는 것이 불가능 하다. 그 말은 즉슨 데이터를 탐색할 때 순차적으로 접근해야 한다는 것 이다. 배열과 연결리스트로 표현 단방향 연결리스트 양방향 연결리스트: 삽입 연산 리스트 삽입(c언어) data=50인 새로운 노드를 리스트 ptr의 node뒤에 삽입 #include #include // 연결 리스트 노드 구조체 정의 typedef struct list.. 2023. 10. 10. 알고리즘 (Algorithm) 알고리즘의 기초사항 알고리즘이란? 문제가 있고 그 문제를 해결하기 위한 효율적인 알고리즘 찾고 그걸 반복적으로 수행하는 것을 말한다. 정말 알고리즘이 필요할 때는? 코딩은 다했고, 배포도 끝냈을 때.그러나 너무 심각하게 느릴 때 어디 코드를 최적화해서 빠르게 해야 할지 모를 때. 바로 이때 알고리즘을 활용한다. 문제를 해결하기 위해서 알고리즘을 활용해 접근해 본다면?(여기서 '피츄'를 찾는 방법은 이분탐색을 활용함) 전화번호부에서 '피츄'를 찾는다. 1. 전화번호부를 집어든다. 2. 전화번호부의 중간을 핀다. * 3. 그 페이지를 살펴본다. 4. '피츄'가 그 페이지에 있다면 5. '피츄'에게 전화를 건다. **6. 만약에 '피츄'가 더 앞쪽 페이지에 있다면 7. 책 앞쪽의 중간을 펴서 살펴본다. 8. .. 2023. 9. 5. 이전 1 다음 728x90
