문제 풀기/코딩인터뷰 (36) 썸네일형 리스트형 [코딩인터뷰 완전정복] 4.5 BST 검증 Q : 주어진 이진 트리가 이진 탐색 트리인지 확인하는 함수를 작성하라. ...더보기 //Node.h template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } }; #include #include "Node.h" bool isBST(TreeNode* top, int low, int high) { if (top == NULL) return true; if (low != NULL && top->data data >= high) return false; bool left = isBST(top->left, low, top->data);.. [코딩인터뷰 완전정복] 4.4 균형 확인 Q : 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다. ...더보기 // Node.h template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } }; #include #include "Node.h" int checkBalanced(TreeNode* top) { int left = top->left == NULL ? 1 : checkBalanced(top->left) + 1; int ri.. [코딩인터뷰 완전정복] 4.3 깊이의 리스트 Q : 이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야 한다. ...더보기 template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } }; template class ListNode { T data; ListNode* previous; ListNode* next; ListNode(T data) { this->data = data; } }; #include #include #include #include "Node.h" using.. [코딩인터뷰 완전정복] 4.2 최소트리 Q : 오름차순으로 정렬된 배열이 있다. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을 때 높이가 최소가 되는 이진 탐색 트리를 만드는 알고리즘을 작성하라. ...더보기 template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } }; template class ListNode { T data; ListNode* previous; ListNode* next; ListNode(T data) { this->data = data; } }; #include #include "Node.h" TreeNode* Minimum.. [코딩인터뷰 완전정복] 4.1 노드 사이의 경로 Q : 방향 그래프가 주어졌을 때 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성하라. 그래프 노드 갯수만큼의 원소를 가진 배열을 사용한다. 이를 연결 배열이라고 하겠다. 연결 배열은 0으로 초기화 시켜준다. 주어진 2개의 노드는 각각 A,B노드라고 한다. 1. A노드를 시작점으로 삼고 연결된 노드들을 탐색한다. 2. 탐색한 노드에 해당하는 연결 배열의 원소를 1로 바꿔준다. 만약 탐색하려는 노드가 이미 1이면 리턴한다. 3. B노드에 해당하는 연결 배열의 원소가 1이 된다면 A에서 B로가는 경로가 존재한다. 연결되어 있지 않다면 시작 노드를 B노드로 바꿔 다시한다. 4. A,B 두 노드에서 모두 연결되어 있지 않다면, A와 B사이의 경로는 존재하지 않는다. [코딩인터뷰 완전정복] 3.6 동물 보호소 Q : 먼저 들어온 동물이 먼저 나가는 동물 보호소가 있다고 하자. 이 보호소는 개와 고양이만 수용한다. 사람들은 보호소에서 가장 오래된 동물부터 입양할 수 있는데, 개와 고양이 중 어떤 동물을 데려갈지 선택할 수 있다. 하지만 특정한 동물을 지정해 데려갈 수는 없다. 이 시스템을 자료구조로 구현하라. 이 자료구조는 enqueue, dequeueAny, dequeueDog, dequeueCat의 연산을 제공해야 한다. 기본적으로 탑재되어 있는 LinkedList 자료구조를 사용해도 좋다. #include #include class Animal { public: int num; Animal(int n) { num = n; } }; class Dog : public Animal { public : Dog(i.. [코딩인터뷰 완전정복] 3.5 스택 정렬 Q : 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop, peek, isEmpty의 네가지 연산을 제공해야 한다. ...더보기 #include template class Stack { private: T *start; int nOfE; int size; public: Stack() { start = new T[10]; nOfE = 0; size = 10; } Stack(int N) { start = new T[N]; nOfE = 0; size = N; } void push(T n) { if (nOfE == size) { T *sizeIncreas.. [코딩인터뷰 완전정복] 3.4 스택으로 큐 Q : 스택 두 개로 큐 하나를 구현한 MyQueue 클래스를 구현하라. #include #include "Stack.h" class MyQueue {private: Stack in; Stack out; bool inputFlag;public: MyQueue() { inputFlag = true; } void push(int n) { if (!inputFlag) { while (out.Size > 0) { in.push(out.pop); } } inputFlag = true; in.push(n); } int pop() { if (inputFlag) { while (in.Size > 0) { out.push(in.pop); } } inputFlag = false; return out.pop(); }};pu.. 이전 1 2 3 4 5 다음