[Technical Organize] 기술면접_자료구조&알고리즘

문제. 시간복잡도란

알고리즘을 구성하는 명령어들이 몇번이나 실행됬는지 센 결과(frequency count)

 +

각 명령어의 실행시간(execution time) 을 곱한 합계를 의미함

그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에

알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다.

시간의 복잡도는 크게 세가지로 나눌 수 있다.

최상의 경우, 최악의 경우, 평균 => 이래서 표기법도 3개가 존재하는것이다.

시간과 공간은 반비례 하는 경향이 있다.

요즘은 공간보다는 시간이 우선이다!

정의 : 프로그램을 실행시켜 완료하는데 걸리는 시간을 의미한다. 어떤 프로그램의 실행 시간을 추정하기 위해서는 모든 기본 명령문의 실행빈도수를 알아야 한다.

 

문제. 정렬의 종류와 시간복잡도를 설명.

O(n²)인 것

- 버블 정렬(Bubble Sort)

- 선택 정렬(Selection sort)

- 삽입 정렬(Insertion sort)

O(n log n)인 것

- 병합 정렬(Merge sort)

- 힙 정렬(Heap sort)

- 퀵 정렬(Quick sort)

하이브리드 정렬

- 팀 정렬(Tim sort)

- 인트로 정렬(Intro sort)

그 밖에

- 기수 정렬(Radix sort)

- 카운팅 정렬(Counting sort)

- 셸 정렬(Shell's sort)

- 보고 정렬(Bogo sort, stupid sort)

- 보고보고 정렬(Bogobogo sort)

- 대기 정렬(Sleep sort)

 

문제. 빅오표기법이 무엇인지 설명.

빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다.

쉽게 생각하면 알고리즘 스카우터라 생각하면 된다.

알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.

빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.

(시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)

그런데 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서

빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.

- 그렇다면 세 가지 중 왜 빅오 표기법을 사용할까?

결론부터 말하자면 빅오 표기법은 알고리즘 효율성을 상한선 기준(최악의 경우)으로 표기하기 때문이다. (알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.)

빅오메가는 하한선(최상의 경우)을 기준으로하고, 빅세타는 상한선과 하한선의 사이(평균의 경우)를 기준으로 표기한다.

 

문제. 버블 정렬에 대해 설명

서로 인접한 레코드들끼리 비교하여 순서가 맞지 않으면 위치를 서로 바꾸면서 정렬하는 방식이다. 시간복잡도 O(n2)

 

문제. 힙 정렬에 대해 설명

이진트리의 개념으로 가장 큰 키 값을 가지는 루트 노드를 삭제하는 과정을 계속해서 반복해 정렬하는 방식이다. 시간복잡도는 O(n log 2n)으로 큐를 예로 들 수 있다.

우선순위 큐를 완전 이진 트리로 구현해 배열을 최소 힙으로 변환한 다음 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법이다.

 

문제. 퀵 정렬에 대해서 설명

평균적으로 가장 빠른 정렬, 분할정복기법, 피봇이라는 한 요소를 사용해 비균등하게 분할

- 장점

1) 속도가 빠르고 추가 메모리를 요구하지 않음

2) 불필요한 데이터의 이동을 줄임

3) 먼 거리의 데이터 교환 가능

4) 한 번 결정된 피봇들을 추후 연산에서 제외

- 단점

1) 이미 정렬된 리스트에 대해서는 수행시간이 오래걸림

- 단점 해결책

데이터 중에서 크기 순으로 중간 값을 피봇으로 선택. 일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기 순으로 중간 값을 선택하는 방법이 많이 사용된다.

배열을 두 부분으로 분할한 다음에 pivot을 기준으로 크고 작은 값을 나누며 그 분할된 부분을 재귀적으로 정렬한다. O(n log 2n)이고, 스택을 사용하며 분할-정복 개념이다.

최악의 경우는 pivot으로 가장 작은 수가 선택되는 경우이며, 이 경우 O(n2)의 시간복잡도를 갖는다.

 

문제. 쉘 정렬을 설명

전체 리스트를 일정 간격의 부분 리스트로 나누고, 부분 리스트를 정렬한다. 간격을 점점 줄여가며 반복하며 부분 리스트에 대해 삽입 정렬을 수행한다.

장점으로는 거의 정렬된 데이터의 정렬이 매우 빠르다 삽입 정렬에 비해 자료 교환을 위해 비교적 큰 거리를 이동할 수 있다.

 

문제. 기수 정렬을 설명

비교를 하지 않음. 숫자의 자릿수 정렬. 다단계 정렬(단계 수 = 데이터의 자릿수) 큐로 구현

10개의 버켓을 만들어서 입력 데이터를 각 자릿수의 값에 따라 버켓에 넣는다. (십진수에서는 각 자리수가 0~9여서)

각 왼쪽 상자부터 순차적으로 버켓 안에 들어 있는 숫자를 순차적으로 읽는다.

LSD : 가장 낮은 자릿수

MSD : 가장 높은 자릿수

단점 : 정렬할 수 있는 레코드의 타입이 한정

 

문제. 합병 정렬에 대해 설명

리스트를 두 개로 나누어 각각 정렬한 다음 다시 하나로 합친다.(분할정복 기법이다.)

장점으로는 크기가 큰 레코드를 정렬할 경우, 연결 리스트를 이용하는 합병 정렬은 다른 어떤 정렬 방법보다 매우 효율적이다.

단점으로는 배열을 이용하는 합병 정렬은 레코드의 크기가 큰 경우, 매우 큰 시간적 낭비를 초래한다.

 

문제. 분할정복 기법이란

– 분할

배열을 같은 크기의 2개의 부분 배열로 분할한다.

- 정복

부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀호출을 이용해 다시 분할정복 기법을 사용한다.

- 결합

정렬된 부분 배열을 하나의 배열에 통합한다.

 

문제. 당신이 정렬을 할 때 어느 알고리즘을 선택하겠는가 또한 그 이유는?

정렬 알고리즘의 선택 시 고려사항

- 키 값들의 분포상태

- 소요 공간 및 작업시간

- 정렬에 필요한 기억공간의 크기

- 데이터의 양

- 초기 데이터의 배열상태

- 사용 컴퓨터 시스템의 특성

 

문제. 반복자(iterator)에 대해 설명

반복자(iterator)는 포인터와 상당히 비슷하며, 컨테이너에 저장되어 있는 원소들을 참조할 때 사용한다.
좀 추상적으로 말하자면, 반복자란 컨테이너에 저장되어 있는 모든 원소들을 전체적으로 훑어나갈 때 사용하는, 일종의 포인터와 비슷한 객체라고 할 수 있다.

반복자(iterator)란 STL 컨테이너에 저장된 요소를 반복적으로 순회하여, 각각의 요소에 대한 접근을 제공하는 객체다.

즉, 컨테이너의 구조나 요소의 타입과는 상관없이 컨테이너에 저장된 데이터를 순회하는 과정을 일반화한 표현이다.

템플릿이 타입과 상관없이 알고리즘을 표현할 수 있게 해준다면, 반복자는 컨테이너와 상관없이 알고리즘을 표현할 수 있게 해주는 것이다.

반복자가 가져야 할 요구 사항과 정의되어야 할 연산자는 다음과 같다.

1. 가리키는 요소의 값에 접근할 수 있어야 한다. 따라서 참조 연산자(*)가 정의되어야 한다.

2. 반복자 사이의 대입 연산, 비교 연산이 가능해야 한다. 따라서 대입, 관계 연산자가 정의되어야 한다.

3. 가리키는 요소의 주변 요소로 이동할 수 있어야 한다. 따라서 증가 연산자(++)가 정의되어야 한다.

위와 같은 요구 사항을 모두 갖춰야만 STL 알고리즘에서 반복자로 사용될 수 있다.

반복자는 포인터를 일반화한 것으로, 포인터는 반복자가 가져야 할 모든 요구 사항을 만족한다.

 

문제. Emplace_back 이랑 push_back 차이

Push_back은 인자로 필요한 객체를 생성 후  Push_back 함수 내부에서 다시 한번 복사가 일어난 뒤 Push_back이 끝날 때 인자들과 객체가 파괴된다. 즉 객체를 하나 추가할 때 쓸데없이 2번 복사하고 파괴한다.

emplace_back은 push_back과 같이 vector의 요소 끝에 원소를 추가하는 함수이다. 두 함수의 가장 큰 차이점은, push_back은 삽입할 객체를 받아 임시 객체를 만들고 push_back 내부에서 복사가 일어난 뒤 vector vector에 추가를 한다. emplace_back은 삽입할 객체의 생성자를 위한 인자들을 받아 std::vector 내에서 직접 객체를 생성하여 삽입하므로 임시 객체의 생성과 파괴, 복사(혹은 move)를 하지 않아도 되어 성능상 유리하다는 것이다. 즉 emplace_back은 객체를 추가할 때 std::vector 내에서 직접 객체를 추가하고, push_back은 임시 객체를 생성 후 push_back 함수 내부에서 객체 추가를 위해 복사를 한 뒤 객체 추가를 한다.

두 함수의 차이 : push_back과 같은 삽입 함수들은 삽입할 객체를 받지만 emplace_back과 같은 생성 삽입 함수는 삽입할 객체의 생성자를 위한 인자들을 받아 std::vector 내에서 직접 객체를 생성하여 삽입하므로 임시 객체의 생성과 파괴, 복사(혹은 move)를 하지 않아도 되어 성능상 더 유리하다는 것이다.

결론 :

push_back은 전달받은 객체를 임의 복사하거나 이동시켜서 값을 복사한다. 즉, 따로 추가 연산작업이 필요하다.

emplace_back은 필요한 인자를 직접 parameter로 받아 내부에서 생성-삽입-소멸 하므로 따로 임시 객체가 생성되지 않는다.

결과 : push_back으로 하여도 컴파일러 내부적으로 최적화 하기 때문에 emplace_back으로 하는 것과 별차이가 없을 수 있다. 그러나 모든 상황에서 emplace_back이 유리하다고 할 순 없다. push_back이 효율적일 수도 있다.

 

문제. Map, multimap, unroded_map 차이점

그냥 간단하게만 설명

- map

자료구조는 레드블랙트리 기반이다.

<키, 값> 의 구조를 갖는다.

여기서 키는 집합처럼 중복된 key는 갖을 수 없다.

해당 키가 이미 존재할 때, 값을 변경하도록 처리하기 위해서는 따로 검사하여 처리해주어야 한다.

자동으로 정렬이 된다.

- multimap

기존의 map과는 다르게 동일한 Key를 갖을 수 있다. (안에 리스트가 있다고 하면 됨)

erase() 함수를 사용하여 삭제 시 값을 인수로 준다면 전부 지우지만

하나 씩 지우기 위해서는 find() 함수를 추가적으로 사용하여 삭제하여야 한다.

at() 함수를 사용하여서 값을 변경할 수 없다.

- unroded_map

자료구조는 해시 기반이다.

기존의 map과 동일하지만 정렬을 하지 않는다. (해시테이블이라 정렬이 필요없음)

 

문제. STL에 대하여 설명.

Standard Template Library의 약자로 표준 C++ 라이브러리이다.

프로그램에 필요한 자료구조와 알고리즘을 Template로 제공하는 라이브러리다.

- STL의 구성요소

컨테이너(자료구조 라기도 하는것 같고 아닌것 같기도하고), 반복자(이터레이터), 알고리즘, 함수객체, 어댑터, 할당기

장점 : 당연히 속도가 빠름.

단점 : 탬플릿 코드로 만들어져서 소스 분석이 힘들다.

 

문제. 컨테이너 개념 및 장단점 특징

STL에서 제공하는 컨테이너 종류에는 선형 자료구조인 vector와 list, 선형 자료구조를 특정 목적에 맞게 변형한 stack, queue, priority_queue가 있으며

자료를 비선형으로 보관하는 set, multiset, map, multimap, hash_map, 기타 컨테이너로 bitset, valarray 등을 제공하고 있다.

표준 시퀀스 컨테이너 : vector, deque, list (선형적)

표준 연관 컨테이너 : set, multiset, map, multimapp (비선형적)

이 외에도 map이나 multimap에서 사용되는 단순히 키와 값의 쌍으로 구성된 pair를 제공한다.

 

문제. 시퀀스 컨테이너와 연관 컨테이너의 차이점

시퀀스 컨테이너는 저장한 위치에 삽입되며, 그 순서가 유지되고, 연관 컨테이너는 삽입 시 이진트리 구조에 맞춰 검색에 빠르도록 자등으로 위치가 정해진다. 따라서 삽입 속도는 시퀀스 컨테이너가 빠르지만, 검색은 연관 컨테이너가 빠르다.

 

문제. 어댑터 컨테이너에 대해 설명

시퀀스 컨테이너에 제약을 가해서 데이터들이 정해진 방식으로만 입출력하는 컨테이너 (Stack, Queue, priority Queue)

기존 컨테이너를 변형하여 자료를 미리 정해진 일정한 방식에 따라 관리하는 특징을 가지고 있다. 자료를 넣고 빼는 순서를 외부에서 마음대로 조작할 수 없으며 컨테이너의 규칙대로 조작해야 한다. 종류에는 큐, 스택, 우선순위 큐가 있다.

 

문제. 연관 컨테이너보다 정렬된 벡터가 나은 경우와 이유는 무엇인가?

데이터를 미리 다 밀어 넣고, 데이터를 검색할 때이다. 왜냐하면 연관 컨테이너는 메모리 참조 위치의 근접성이 보장되지 않기 때문이다. 또한 연관 컨테이너에 사용된 메모리가 많아지면서 메모리 페이지 오류가 증가됨에 따라 탐색, 삽입, 삭제 시간이 오래걸린다.

많은 메모리를 사용하는 이유는 연관 컨테이너는 자신에게 데이터를 밀어 넣으면 그 데이터와 함께 3개의 포인터가 생성되면서 균형 이진 탐색트리 구조를 갖추게 된다. 즉 원소 한 개당 메모리 오버헤드를 지불해야 한다.

하지만 vector는 미리 메모리 공간을 확보하여 그 공간에만 사용하기 때문에 초기 vector 생성 시 들어가는 메모리 오버헤드만 지불하면 되는 차이를 보인다. 즉 연관 컨테이너는 정렬된 vector 보다 page fault가 더 많이 발생하여 느릴 수 있다는 점을 지적한다.

 

문제. 벡터에서 카파시티보다 사이즈가 커졌을 때 재할당되는 과정을 설명

새로 메모리를 할당하는데 그 메모리의 크기는 기존의 메모리에서 카파시티의 사이즈만큼 메모리 사이즈를 합하여 할당한다. 그 후 기존의 데이터를 새로 할당한 메모리에다가 복사시킨 후, 기존의 데이터를 삭제한다.

이때 포인터와 래퍼런스 반복자를 모두 해제시켜주고 다시 할당시켜 주게 된다. 그래서 할당시에 느려지기 때문에 이것을 막기 위해 미리 리저브(reserve) 함수를 써서 카파시티를 들어올 데어트의 크기만큼 할당시켜준다면 오버헤드가 줄어들 것이다.

 

문제. 벡터에서 사용하지 않는 메모리를 해제시켜 주기 위해서는 어떻게 하나?

메모리를 해제시켜 주는 STL 객체의 타입과 같은 타입으로 임시객체를 생성하고, 그 임시객체와 해제시켜 줄 객체와 Swap을 통해서 메모리 해제를 할 수 있다.

 

문제. 자료구조란

자료구조(Data-Structure)는 데이터들의 모임, 관계, 함수, 명령 등의 집합을 의미한다.

더 쉽게 표현하자면,

1) 처리하고자 하는 데이터들이 모여 있는 형태 혹은

2) 처리하고자 하는 데이터들 사이의 관계(수직 관계, 상하 관계, 일방적인 관계, 상호 관계 등)를 정의한 것 혹은

3) 데이터들을 사용하기 용이하게 저장해 놓은 형태라고 볼 수 있다.

자료구조를 잘 선택하면 사용하는 메모리를 최소화 할 수 있으며 시간, 공간적으로 효율성을 확보할 수 있다.

 

문제. 선형구조와 비선형구조의 종류를 나열하고 설명

- 선형구조

배열 :

연속적인 기억 공간에 배정하며 각 요소들은 동일 데이터 타입으로(인덱스, 값)의 쌍으로 표현한다.

스택 :

일정한 연속 공간에서 데이터의 삽입과 삭제가 한쪽으로 이루어지는 방식(LIFO)

큐 : 

일정한 연속 공간에서 데이터의 삽입은 한쪽 끝에서, 삭제는 다른 한 쪽에서 이루어지는 방식(FIFO), 응용 분야는 운영 체제의 작업 스케쥴링을 예로 들 수 있다.

데크 :

일정한 연속 공간에서 데이터의 삽입과 삭제가 양쪽에서 이루어지는 방식.

연결리스트 :

노드, 즉 포인터로 연결함으로써 위의 선형 구조들과는 달리 순차적으로 메모리가 할당되지 않고, 될 필요도 없다.

- 비선형구조

이진트리 :

(L: 왼쪽링크, D: 데이터, R: 오른쪽링크)로 구성된 노드에서 두 링크에 왼쪽 자식과 오른쪽 자식 노드의 주소를 저장하는 방식이다. 트리 순회 방식에는 전위순회, 중위순회, 후위순회 방식이 있다.

그래프 :

사이클이 형성되는 자료구조로서, 트리의 일반 형식이다. 그래프의 순회 방식에는 깊이우선탐색(DFS), 너비우선탐색(BFS) 방식이 있다.

 

문제. Array와 list의 차이점은?

배열은 데이터가 메모리 상에 선형적으로 나열되어 있고, 리스트는 메모리 곳곳에 떨어져 있지만 포인터로 연결되어 있다. 탐색은 배열이 빠르고, 삽입 삭제는 list가 빠르다.

          

문제. Array와 List의 Search에 대한 Time?

Array : O(1)

List : O(n)

 

문제. 연결 리스트(Linked List)란

자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조.

- 노드의 삽입, 삭제 작업이 용이하다.

- 기억공간이 연속적으로 놓여있지 않아도 저장이 가능하다.

- 접근 속도가 느리다. (포인터를 찾아가는 시간이 필요하기 때문에 배열에 비해 접근속도 느림)

- 중간 노드의 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

종류

- 단일 연결 리스트 ( Singly Linked List ) : 단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

- 이중 연결 리스트 ( Doubly Linked List ) : 이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

- 원형(환형) 연결 리스트 ( Circular Linked List ) : 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

- 이중 원형(환형) 연결 리스트 ( Doubly Circular Linked List ) : 이중 원형 연결 리스트는 이중 연결 리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

 

문제. 원형 연결리스트에 대해 설명

단순 연결리스트는 마지막 노드가 NULL을 갖는데, 이 NULL 링크 대신 리스트의 처음 노드의 포인터를 갖도록 구성한 리스트다.

장점으로는 어느 한 노드로부터 다른 모든 노드에 접근할 수 있다. 임의의 노드 검색 시 첫 노드부터 찾지 않고, 현재 노드부터 검색할 수 있다. 결합, 분리 작업에 효율적이고 큐 구축이 가능하다.

단점으로는 노드 검색 시 무한 루프에 빠질 수 있다. Head node를 두어 무한 루프를 제거한다.

 

문제. 이중 연결리스트에 대해 설명

노드 한 개에 하나의 데이터 부분과 두 개의 포인터(링크)부분으로 구성된 리스트다.

장점으로는 노드 검색 시 양방향 검색이 가능하므로 속도가 빠르고 선행 노드의 검색이 쉽다. 한 노드의 포인터가 파괴되었을 경우 복구가 가능하다.

단점으로는 일반 링크드리스트보다 메모리 공간을 더 많이 사용한다.(앞 뒤 2개의 링크를 걸기 때문에)

 

문제. 이중 원형 연결리스트에 대해 설명

마지막 노드의 Rlink는 처음 노드를 가리키게 하고, 처음 노드의 Llink는 마지막 노드를 가리키게 한다.

장점으로는 마지막 노드까지 데이터가 저장되었을 때, 빈 노드를 찾아 입력할 수 있도록 많은 융통성을 부여한다. 무한루프에 빠지는 것을 방지한다.

단점으로는 알고리즘의 구현이 매우 복잡하다.

 

문제. map에 대하여 설명.

map의 자료구조는 '트리(tree)' 다. (정확하게 말하자면 트리 자료구조 중 하나인 '레드-블랙 트리' 다).

          5

 

     7        11

 

 9     12        20

 

     30  35

트리 자료구조에서 제일 최상 위의 '5'는 루트노드(root node)라고 하고, 노드'5'와 노드'7'의 관계에서 노드'5'는 부모노드(parent node), 노드'7'은 자식노드(child node)라고 한다.

자식이 없는 노드는 리프노드(leaf node)라고 한다.

균형을 이룬 트리는 시퀀스하게 자료를 자정하는 연결 리스트에 비해서 검색이 빠르나 정해진 규칙에 따라서 자료를 삽입, 삭네 해야하기 때문에 삽입과 삭제가 간단하지 않으며 구현이 복잡하다.

value는 저장할 자료이고, key는 value를 가리킨다.

- map을 사용하는 경우

1. 정렬해야 한다.

2. 많은 자료를 저장하고, 검색이 빨라야 한다.

3. 빈번하게 삽입, 삭제하지 않는다.

 

문제. Map에서 데이터 삽입 방법을 설명

- 배열처럼 삽입하는 방법

Std::map<string, int> p;

P[“창현”] = 100;

- Insert()를 사용해 안에 인자를 넣어주는 방법

p.insert(std::map<string, int>::value_type(“창현”, 100));

p.insert(std::map<string, int>(“창현”, 100));

p.insert(make_pair(“창현”, 100));

pair를 사용하는 방법이 value_type을 사용하는 것보다 속도 면에서 유리하지 못하다.

 

문제. 트리와 이진트리 차이

- 트리

공백트리가 포함되지 않으며 비순서 트리

계층적인 구조를 표현하기 위한 자료구조로 여러 노드가 한 노드를 가리킬 수 없는 구조를 의미한다. 일반적으로 조직도, 디렉토리 구조등을 생각하면 된다. 스택이나 큐와 같은 선형구조가 아닌 뒤집어놓은 나무 모양 같은 계층구조를 가지며, 탐색이나 계층적 구조를 가져야 하는 데이터를 다루는데 많이 사용된다.

- 이진트리

공백트리가 포함되며 순서트리

이진 트리(Binary Tree)는 최대 2개의 자식 노드를 가질 수 있는 노드를 의미한다. 즉 한개의 노드가 2개의 자식노드를 가지거나 한개를 가지거나 아예 안 가질수 있다.

 

문제. 완전 이진트리

임의의 두 단말 노드의 레벨 차이가 1이하인 경우이며, 왼쪽에서 오른쪼으로 채워진 이진트리다. 레벨 n까지 모든 노드수는 2n승-1이다.

 

문제. Linked list에서 특정 node 하나를 삭제하는 방법.

해당 linked list 내에서 삭제하고자 하는 node 값이 나올 때까지 loop를 돌면서 해당 값을 비교해보고 해당 값과 일치한다면 erase 함수를 이용하여 삭제한다. 순차탐색

 

문제. 이진 탐색트리(BST(binary search tree))란

이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.

- concepts

예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(log n)으로 빠르지만 자료 입력, 삭제가 불가능하다.

연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산복잡성이 발생한다.

두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적이다.

자신의 왼쪽 서브트리에는 현재노드보다 Key값이 작은것. 오른쪽 서브트리에는 Key값이 큰 것들이 오게된다.

이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 쓴다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회)

이렇게 하면 이진탐색트리 내에 있는 모든 값들을 오름차순으로 정렬된 순서대로 읽을 수 있다.

- 문제점

계속 큰것만 들어오면 트리가 생길 수 있음

최악의 경우 O(트리의 높이 = h)만큼의 탐색시간이 걸림.

 

문제. 입력이 순차적으로 들어올 때, BST(binary search tree : 이진탐색트리)를 구성하는 방법을 설명하라

입력하는 값과 루트의 값을 비교하여 만약 값이 같다면 false를 반환하고, 입력 값이 루트의 값보다 작다면 왼쪽 부 트리에서 다시 입력이 들어갈 위치를 찾는다. (비교 후 작으면 왼쪽, 크면 오른쪽) 만약 입력 값이 루트 값보다 크다면 오른쪽 부 트리에서 입력 값이 들어갈 위치를 찾는다.

 

문제. 이진 탐색트리(BST)를 이용해 탐색할 때 최악의 경우는 어떤 경우인가

예를 들어 1, 2, 3, … n의 순서로 키 값이 삽입되는 경우, 이진 탐색트리는 오른쪽 사항트리가 되어 높이가 n이 된다. 따라서 최악의 경우 노드 탐색에 O(n)의 시간이 소요된다. 평균 시간 복잡도는 O(log2n)이다.

 

문제. 위의 최악의 경우 해결방안은?

AVL트리를 사용해 해결할 수 있다. AVL 트리는 높이 균형 이진 탐색트리이다. 높이 균형이란 트리 내 모든 노드에 대해 왼쪽과 오른쪽 부 트리의 높이 차가 1 이하인 것을 의미한다,

높이 균형이 깨지는 경우 회전 연산에 불균형을 해결할 수 있다. 회전 연산이 수행되기 위해서는 균형 인수를 유지해야 한다. 균형 인수란 오른쪽 부 트리의 높이 = 왼쪽 부 트리의 높이

 

문제. 레드블랙 트리는 무엇이고 사용하는 이유에 대해서 설명.

레드블랙 트리는 자가 균형 이진 탐색 나무로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조이다.

레드블랙 트리도 이진탐색 트리이기 때문에 왼쪽 서브트리에는 현재 노드의 Key값보다 작은값이. 오른쪽 서브트리에는 현재노드의 Key값보다 큰 값 위치

1. Root Property : 루트노드의 색깔은 검정(Black)이다.

2. External Property(자식이 없는) : 모든 external node들은 검정(Black)이다.

3. Internal Property : 빨강(Red)노드의 자식은 검정(Black)이다.

 == No Double Red(빨간색 노드가 연속으로 나올 수 없다.)

4. Depth Property : 모든 리프노드(자식이 없는)에서 Black Depth는 같다.

 == 리프노드에서 루트노드까지 가는 경로에서 만나는 블랙노드의 개수는 같다. (그냥 노드의 수는 다를 수 있음.)

- Double Red 해결법 (현재 insert된 노드의 uncle node(내 부모의 형제)의 색깔에 따라 방법을 정함)

● Restructuring (uncle noder가 검정일 때) = 재건축 방법

● Recoloring (uncle noder가 빨강일 때) = 색깔을 재설정하는 방법

레드블랙트리에 삽입(insertion)하는경우, Restructuring을 하든, Recoloring을 하든 O(logn)이 걸리게 된다.

 

문제. 이진탐색 트리에서 어떤 한 노드를 삭제 했을 때 어떻게 되는지 그리고 왜 그렇게 되는지를 설명.

삭제할 때, 문제는 그자리에 누굴 채워야 하는가이다. (이진 탐색 트리가 유지되도록)

정리하면

1. 삭제할 노드를 대체할 노드를 찾고

2. 대체할 노드에 저장할 값을 삭제할 노드에 대입하고

3. 대체할 노드의 부모 노드와 자식노드를 연결(주소값)한다

 

문제. 그래프에 대해서 설명

연결되어 있는 객체간의 관계를 표현하는 자료구조(트리도 그래프의 일종이다.) 전기회로, 프로젝트관리, 지도에서 도시들의 연결 등, 그래프G는 (V, E)로 표시된다. 정점과 간선은 모두 관련되는 데이터를 가질 수 있다.

- V는 정점(vertex, 노드: node)

- E는 간선(edge, 링크: lingk)

무방향그래프 – 양방향

방향그래프 – 한쪽 방향

노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.

Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있다.

 

문제. 깊이우선탐색이란(DFS)

깊이 우선탐색은 트리의 전위순회방식을 일반화시킨 그래프의 정점 순회방법이다. 탐색 도중 인접된 모든 정점이 이미 방문된 정점을 만났을 때, 바로 이전에 방문한 정점으로 돌아가기 위해 스택을 이용한다.

 

문제. 너비우선탐색이란(BFS)

주어진 정점 v를 출발점으로 하여 이를 방문한 후, 방문표시를 하고 v의 인접리스트에 있는 모든 정점들을 차례로 즉시 방문한다. 그리고 v의 인접리스트 상에 존재하는 첫 번째 정점에 인접한 방문하지 않은 정점들을 모두 차례로 방문한다.

이 때 각 정점을 방문할 때마다 그 정점을 큐에 저장한다. 하나의 인접리스트에 방문이 끝나면 큐에서 한 정점을 꺼내서 그 정점에 대한 인접리스트의 정점들을 동일한 방법으로 계속 방문한다. 너비우선탐색은 큐를 이용한다.

 

문제. 해싱이란 무엇인가

해싱 함수를 이용해 자료를 검색하는 방법이다. 데이터를 해시 테이블이라는 배열에 저장하고 해싱 함수를 이용해 데이터가 위치한 곳의 주소를 찾기 때문에 신속하게 원하는 자료를 검색할 수 있다.

 

문제. 해시 테이블이란

해싱 함수에 의하여 참조되는 테이블이다. 데이터를 저장하는 배얼로 보통 하나의 배열에 한 개 이상의 레코드를 수용할 수 있다.

 

문제. Burket(버켓)이란 무엇인가

해싱 함수에 의해 계산된 주소인 홈 주소 혹은 버켓 주소에 레코드 키를 저장하기 위해 마련된 기억장소를 말하며 대개 한 개 또는 여러 개의 레코드를 저장할 수 있는 슬롯으로 구성된다.