본문 바로가기

C++

 (44)
[C++ STL] Array 1. Array - C++에 내장되어있는 고정 배열(Fixed array)을 대채 할 수 있는 고정 길이 자료구조 - 고정 배열 선언처럼 array의 길이는 컴파일 타임에 설정해야 한다. - 크기가 고정이기 때문에 힙(Heap)을 사용하지 않고 스택(Stack)을 쓴다. - 임의 접근이 가능하다. ( [ ], at() 지원) - Vector와 의 비교 Array Vector 효율성 크기 변경 가능 X O Vector 삽입, 삭제 용이 X (push, pop, insert 등 멤버함수 지원하지않음, 할당된 크기 내에서만 사용가능) O Vector 저장 공간 Stack Heap Array - 고정 길이 배열과의 비교 고정 길이 배열 Array 함수에 전달할 때 포인터로 형변환 된다. 포인터로 형변환 된 배열..
[코딩인터뷰 완전정복] 4.10 하위 트리 확인 Q : 두 개의 커다란 이진 트리 T1과 T2가 있다고 하자. T1이 T2보다 훨씬 크다고 했을 때, T2가 T1의 하위트리인지 판별하는 알고리즘을 만들라. T1 안에 있는 노드 n의 하위 트리가 T2와 동일하면, T2는 T1의 하위 트리다. 다시 말해, T1에서 노드 n의 아래쪽을 끊어 냈을 때 그 결과가 T2와 동일해야 한다. T1이 T2보다 훨씬 크다는 조건이 있으므로, 우리는 큰 트리에서 작은 트리를 찾아내기만 하면 된다. 방법은 여러가지가 있겠지만, 가장 먼저 떠올린 것은 T1에서 T2의 루트노드와 같은 노드를 찾았을 때만, 그 하위트리를 조사하는 방법이다. 이때 시간 복잡도는 이론상 O(mn) 이다. m은 T1의 노드의 갯수, n은 T2의 노드의 갯수이다. T1과 T2의 비교과정중 차이점이 하..
[코딩인터뷰 완전정복] 4.9 BST 수열 Q : 배열의 원소를 왼쪽에서부터 차례로 트리에 삽입함으로써 이진 탐색 트리를 생성할 수 있다. 이진 탐색 트리 안에서 원소가 중복되지 않는다고 할 때, 해당 트리를 만들어 낼 수 있는 모든 가능한 배열을 출력하라. Input : 이진 탐색 트리 output : 가능한 모든 입력 배열 배열의 원소를 왼쪽에서부터 차례로 삽입하는 경우 루트는 항상 첫번째 원소가 된다. 나머지 트리의 각 원소는 다음의 한가지 조건만 고려하면된다. 부모 노드는 자식 노드보다 먼저 나와야 한다. 왼쪽의 원소가 먼저 입력되냐 오른쪽의 원소가 먼저 입력되느냐는 중요하지 않다. 1. 트리를 탐색노드로 한다. 2. 탐색노드를 입력배열의 원소에 추가한다. 3. 트리의 자식들을 후보 리스트에 넣는다. 4. 입력배열과 후보 리스트를 넘겨주며..
[코딩인터뷰 완전정복] 4.8 첫 번째 공통 조상 Q : 이진 트리에서 노드 두개가 주어졌을 때 이 두 노드의 첫번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성하라. 자료구조내에 추가로 노드를 저장해 두면 안 된다. 반드시 이진 탐색 트리일 필요는 없다. 1. brute force (무식한 방법) 한 노드의 조상들과 다른 노드의 조상들을 모두 비교해보면, 두 노드가 공통된 조상을 가지고 있는지 알아낼 수 있을 것이다. 우리는 두 노드의 첫번째 공통 조상을 찾아야 하기 때문에, 자식에서 부모순서로 탐색한다. 한 노드의 조상들을 다른 노드의 모든 조상 노드들과 비교하기 때문에 시간복잡도는 O(MN) 이다. 이때, M과 N은 각 노드의 조상 노드의 갯수이다. 임의의 노드 2개를 각각 A, B라고 하겠다. A의 부모노드 A'과 B의 모든 부모노드들을..
[코딩인터뷰 완전정복] 4.7 순서 정하기 Q : 프로젝트의 리스트와 프로젝트들 간의 종속 관계(즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두 번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻)가 주어졌을 때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다. 예시 입력 : 프로젝트: a, b, c, d, e, f 종속관계: (a,d),(f,b),(b,d),(f,a),(d,c) 출력 : f,e,a,b,d,c #include #include #include #include template std::list ordering(std::list proj, std::list relation) { int size = proj.size(); int *depNum = new int[size]; bool..
[코딩인터뷰 완전정복] 4.6 후속자 Q : 이진 탐색 트리에서 주어진 노드의 '다음' 노드(중위 후속자(in-order successor))를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자. ...더보기 // Node.h template class TreeNode{ public: T data; TreeNode* parent; TreeNode* left; TreeNode* right; TreeNode(T data) { this->data = data; } void addLeft(TreeNode* left) { this->left = left; left->parent = this; } void addRight(TreeNode* right) { this->right = right; right->paren..
[코딩인터뷰 완전정복] 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..

티스토리툴바