개발자 기술면접 #2 - 자료구조

배열(array)에 대해 설명하시오.

 

가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있는 것이다.

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다.

삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

 

연결 리스트(linked list)에 대해 설명하시오.

 

이 부분에 대한 문제점을 해결하기 위한 자료구조가 linked list 이다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결할 수 있는 것이다.

하지만 LinkedList 역시 한 가지 문제가 있다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다. 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다. 그렇다고 해서 아주 쓸모없는 자료구조는 아니기에, 우리가 학습하는 것이다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

 

포인터(pointer)에 대해 설명하시오.

 

주소값의 이해

데이터의 주소값이란 해당 데이터가 저장된 메모리의 시작 주소를 의미합니다.

C언어에서는 이러한 주소값을 1바이트 크기의 메모리 공간으로 나누어 표현합니다.

예를 들어, int형 데이터는 4바이트의 크기를 가지지만, int형 데이터의 주소값은 시작 주소 1바이트만을 가리킵니다.

 

포인터란?

C언어에서 포인터(pointer)란 메모리의 주소값을 저장하는 변수이며, 포인터 변수라고도 부릅니다.

char형 변수가 문자를 저장하고, int형 변수가 정수를 저장하는 것처럼 포인터는 주소값을 저장합니다

 

Call by value와 Call by reference에 대해 설명하시오.

 

call-by-value (값에 의한 호출)

• 함수가 호출될 때, 메모리 공간 안에서는 함수를 위한 별도의 임시 공간이 생성된다. (c++의 경우 stack frame) 함수가 종료되면 해당 공간은 사라진다.

• 스택 프레임(Stack Frame) : 함수 호출시 할당되는 메모리 블록(지역변수의 선언으로 인해 할당되는 메모리 블록)

• call-by-value 값에 의한 호출방식은 함수 호출시 전달되는 변수의 값을 복사하여 함수의 인자로 전달한다.

• 복사된 인자는 함수 안에서 지역적으로 사용되는 local value의 특성을 가진다.

• 따라서 함수 안에서 인자의 값이 변경되어도, 외부의 변수의 값은 변경되지 않는다.

• Java의 경우 함수에 전달되는 인자의 데이터 타입에 따라서 (원시자료형 / 참조자료형) 함수 호출 방식이 달라진다.

  • 원시 자료형 (primitive type) : call-by-value 로 동작 (int, short, long, float, double, char, boolean )

  • 참조 자료형 (reference type): call-by-reference 로 동작 (Array, Class Instance)

call-by-reference (참조에 의한 호출)

• 함수가 호출될 때, 메모리 공간 안에서는 함수를 위한 별도의 임시 공간이 생성된다. (예: stack frame) 함수가 종료되면 해당 공간은 사라진다.

• call-by-reference 참조에 의한 호출방식은 함수 호출시 인자로 전달되는 변수의 레퍼런스를 전달한다. (해당 변수를 가르킨다.)

• `따라서 함수 안에서 인자의 값이 변경되면, 아규먼트로 전달된 객체의 값도 함께 변경된다.

Iterative와 Recursion에 대해 설명하시오.

 

재귀 메소드

메소드는 특정한 문제를 해결하기 위해 다른 메소드를 호출할 수 있으며 자신을 직접 호출하는 것을 재귀라고 한다.

재귀적인 방법을 사용함에 있어 주의할 점은 종료하는 지점을 정의하는 것이다.

그렇지 않으면 재귀는 무한 반복되기 때문이다.

 

재귀와 반복

재귀와 반복은 같은 문제를 해결하는 두 가지 방법이지만, 재귀 방법이 적은 코드를 사용해 효율적으로 처리할 수 있다.

 

반복

메소드의 호출은 매개변수 리스트를 보관할 메모리 영역과 (메소드가 static이 아니라면) 메소드를 실행할 수 있는 복사 공간이 필요하다.

반복적인 메소드 호출을 위한 메모리는 한번만 필요하기 때문에 반복 프로그래밍이 성능적인 면에서 유리하다.

 

재귀

세련된 방법. 코드를 이해하고 유지하는 것이 더 중요하다면 재귀 프로그래밍을 고려한다.

메소드가 자신을 호출할 때에 메모리를 위한 비용과 CPU 사용 시간이 더 많이 소요된다.

 

스택(stack)에 대해 설명하시오.

 

선형 자료구조의 일종으로 Last In First Out (LIFO). 즉, 나중에 들어간 원소가 먼저 나온다. 이것은 Stack 의 가장 큰 특징이다. 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.

 

큐(queue)에 대해 설명하시오.

 

선형 자료구조의 일종으로 First In First Out (FIFO). 즉, 먼저 들어간 놈이 먼저 나온다. Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다. 

 

1차원 배열의 선형 큐에서 잘못된 포화 상태 문제를 해결하는 방법을 설명하시오.

 

1차원 배열의 선형 큐는 큐의 처음을 가리키는 front가 자료가 새로 넣어짐에 따라 점차 뒤로 이동하게 되어 있다. 그러한 상황에서 front의 포인터가 배열의 끝가지 가게되면 사용하지 않는 공간이 있음에도 포화 상태를 일으키는 잘못된 포화 상태 문제가 일어난다.

큐의 끝인 rear가 배열의 끝에 도달하면 다시 배열의 처음으로 포인터를 이동시키는 환형큐를 사용해서 앞에 비워지는 front자리를 다시 채워준다.

 

트리(Tree)에 대해 설명하시오.

 

트리는 자료들이 리스트, 스택, 큐와 같은 1:1 관계의 선형구조가 아니라 1:n 관계의 비선형 자료구조이다. 또한 계층 관계로 만들어진 계층형 자료구조이다.

 

사용 예 : 눈에 쉽게 보이는 사용으로는 현재 사용하고 있는 PC나 모바일 핸드폰에서의 파일들을 생각해볼 수가 있다.
각 폴더에 대해 자식 폴더 또는 파일들이 있고, 이 때 자식 폴더는 부모가 되어 자식 폴더 또는 파일들을 가지게 된다.

 

이진 트리(Binary Tree)에 대해 설명하시오.

 

이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다. 재귀적인 정의라 맞는듯 하면서도 이해가 쉽지 않을 듯하다. 한 가지 덧붙이자면 공집합도 이진 트리로 포함시켜야 한다. 그래야 재귀적으로 조건을 확인해갔을 때, leaf node 에 다 달았을 때, 정의가 만족되기 때문이다. 자연스럽게 노드가 하나 뿐인 것도 이진 트리 정의에 만족하게 된다.

 

다음 이진 트리의 순회 방법에 대해 설명하시오.

 

1) 전위 순회(Preorder Traversal)

 

전위순회는 현재 노드를 가장 먼저 방문합니다. 그러니 왼쪽 자식과 오른쪽 자식을 현재 자식보다 나중에 방문합니다.

전위 순회 방법을 순환식으로 기술하면 다음과 같다.

 

1. 루트 노드(root node)를 방문한다.

2. 왼편 서브트리(left subtree)를 전위 순회한다.

3. 오른편 서브트리(right subtree)를 전위 순회한다.

 

2) 중위 순회(Inorder Traversal)

 

우선 왼쪽 자식을 방문하고, 현재 노드를 방문합니다. 그리고 나서 오른쪽 자식 노드를 방문하게 됩니다. 현재 노드를 중간에 방문한다고 해서 중위순회가 됩니다.

중위 순회 방법을 순환식으로 기술하면 다음과 같다.

 

1. 왼편 서브트리(left subtree)를 중위 순회한다.

2. 루트 노드(root node)를 방문한다.

3. 오른편 서브트리(right subtree)를 중위 순회한다.

 

3) 후위 순회(Postorder Traversal)

 

현재 노드를 가장 나중에 방문하는 방식의 순회입니다. 그러니 왼쪽 자식, 오른쪽 자식 노드를 우선적으로 방문합니다.

후위 순회 방법을 순환식으로 기술하면 다음과 같다.

 

1. 왼편 서브트리(left subtree)를 후위 순회한다.

2. 오른편 서브트리(right subtree)를 후위 순회한다.

3. 루트 노드(root node)를 방문한다.

 

이진 탐색 트리(Binary Search Tree)에 대해 설명하시오.

 

힙(heap)에 대해 설명하시오. 

 

힙은 최댓값, 최솟값을 찾아내는 연산을 쉽게하기 위해 고안된 자료형이다.

힙은 각 노드의 값이 그 자식 노드의 값보다 작지않거나(최대 힙), 그 자식의 키값보다 크지 않은(최소 힙) 완전 이진 트리이다.

힙의 데이터 삽입 시 시간복잡도는 O(logN)이고 삭제 시 시간복잡도도 O(logN)이다.

 

그래프(Graph)에 대해 설명하시오.

 

그래프는 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조이다.

원소를 노드라고 할 때, 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료구조라고도 한다.

 

다음 그래프를 구현하는 방법에 대해 설명하시오.

 

1) 인접 행렬(Adjacent Matrix)

 

인접행렬은 인접리스트와 같이 그래프를 저장하고 탐색할 수 있도록 도와주는 하나의 자료구조이다. 보통 배열을 사용해서 그래프의 정보를 저장한다.

 2차원 배열의 특성상 공간복잡도가 O(n2)이므로 정점의 수가 많을 경우 인접행렬을 사용한다면 메모리의 낭비가 문제가 될 수 있다. 더욱이 대부분의 인접행렬의 탐색은 시간복잡도도 O(n2)이므로 사용에 주의를 기울일 필요가 있다.

 

2) 인접 리스트(Adjacent List)

 

인접행렬과 함께 인접리스트는 주로 그래프를 데이터로 저장하고 탐색하기 위해 사용한다.
간단한 구조의 그래프는 인접행렬로 구현이 가능하나 시간복잡도 O(n2)이 걸리기 때문에 그래프의 정점이 많은 경우 O(n)이 걸리는 인접리스트로 구현하는 것이 효율적이다. 그렇기 때문에 복잡하고 어려운 상황의 그래프에서는 인접리스트가 더 효율적으로 그래프를 저장 & 탐색할 수 있도록 해준다.

 

인접행렬 vs 인접 리스트

두 가지 방식은 완전히 정반대의 특성을 가져서, 한 방식의 단점이 바로 다른 방식의 장점이기 때문에
구현하려는 알고리즘의 종류나 그래프의 종류에 따라 적절히 사용해야 합니다.

 

1. 정점 u - v간의 간선 여부 확인

인접 행렬 - 정점 u, v가 주어졌을 때, 단 한 번의 배열의 접근만으로 연결 여부 파악 가능

인접 리스트 - ad[u]의 처음부터 읽어나가면서 각 원소를 일일이 확인해야 함

 

2. 공간 복잡도 

인접 행렬 - V개의 Node를 표현하기 위해선 V*V 개수 만큼의 공간이 필요하므로 공간복잡도는 O(V^2)

인접 리스트 - V개의 리스트에 실제 간선만큼 원소가 들어 있으므로, 공간복잡도는 O(V+E)

만약 간선의 개수가 V^2에 수렴한다면 비슷할 수 있으나, 현실 세계에서는 간선의 수가 훨씬 적은 그래프가 많음

 

3.결론

간선의 수가 V^2에 비해 훨씬 적은 그래프를 희소 그래프 —> 인접 리스트

간선의 수가 V^2에 비례하는 그래프를 밀접 그래프 —> 인접 행렬  

 

깊이 우선 탐색(Depth First Search : DFS)에 대해 설명하시오.

 

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. 어떤 자료구조를 사용해야할까? 바로 Stack 이다. 

Time Complexity : O(V+E) : vertex 개수 + edge 개수

 

너비 우선 탐색(Breadth First Search : BFS)에 대해 설명하시오.

 

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS 에서는 자료구조로 Queue 를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다. 

Time Complexity : O(V+E) … vertex 개수 + edge 개수 ! BFS 로 구한 경로는 최단 경로이다.

 

MST(Minimal Spanning Tree)에 대해 설명하시오.

 

크루스칼 알고리즘(Kruskal Algorithm)에 대해 설명하시오.

 

프림 알고리즘(Prim Algorithm)에 대해 설명하시오.

 

다익스트라 알고리즘(Dijkstra Algorithm)에 대해 설명하시오.

 

플로이드 알고리즘(Floyd Algorithm)에 대해 설명하시오.

 

다음 정렬 기법에 대해 설명하시오.

 

1) 선택 정렬(Selection Sort)

 

2) 버블 정렬(Bubble Sort)

 

3) 퀵 정렬(Quick Sort)

 

4) 삽입 정렬(Insertion Sort)

 

5) 병합 정렬(Merge Sort)

 

6) 힙 정렬(Heap Sort)

 

해싱에 대해 설명하시오.

 

Collision에 대해 설명하시오.

 

Synonym에 대해 설명하시오.

 

이진검색에 대해 설명하시오.