본문 바로가기

분류 전체보기

 (502)
[코딩인터뷰 완전정복] 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..
[코딩인터뷰 완전정복] 3.3 접시 무더기 Q : 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다. ...더보기 #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) {..
[코딩인터뷰 완전정복] 3.2 스택 Min Q : 기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다. #include class stack { private: int *start; int nOfE; int size; int *minStack; int minNofE; int minStackSize; public: stack() { start = new int[10]; nOfE = 0; size = 10; minStack = new int[10]; minNofE = 0; minStackSize = 10; } stack(int N) { start = new int[N]; nOfE = 0; size = N; ..
[코딩인터뷰 완전정복] 3.1 한 개로 세 개 Q : 배열 한 개로 스택 3개를 어떻게 구현할지 설명하라. A : 임의접근이 가능하도록 스택을 구현 할 경우 시작 노드가 변하지 않는다. 배열을 3등분해서 각 스택의 공간을 정적으로 할당한다. 공간을 동적으로 사용하려면 스택에 넣을 공간이 부족할 때 스택의 공간을 늘려주고 그자리에 있던 원소들은 밀어준다. 스택을 노드로 구현한다면 공간을 정적으로 지정해 줄 필요없이 세 스택의 총 길이가 배열의 길이를 넘지 않도록만 해준다.
[코딩인터뷰 완전정복] 2.8 루프 발견 Q : 순환 연결리스트(circular linked list)가 주어졌을 때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서 변질된 방식의 연결리스트를 의미한다. ...더보기 // LinkedList.h #include template struct node { T data; node *next; }; template class linked_list{ private: node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } node* add_node(T n) { node *temp = new node; temp..

티스토리툴바