자료구조 및 알고리즘 관련 질문

자료구조

자료구조와 알고리즘이란 무엇인가요?

- 자료구조는 데이터를 원하는 목적에 맞게 저장하기 위한 구조를 말하고 알고리즘이란 문제를 해결하기 위한 모든 동작들의 모임이라고 할 수 있습니다.

 

 

스택, 큐, 트리, 힙 구조에 대해서 설명해주세요

- 스택: 데이터를 쌓아서 올려놓은 형태의 자료구조로 마지막에 들어간 데이터가 가장 먼저 나오는 후입선출의 구조로 되어 있습니다. 데이터의 삭제와 삽입이 한 곳에서 일어나며 활용 예시로는 브라우저의 뒤로 가기 기능, 컨트롤 z 기능 등이 있습니다.

- 큐: 데이터를 일렬로 세운 형태의 자료구조로 처음 들어간 데이터가 가장 먼저 나오는 선입선출의 구조이며 데이터의 삽입은 rear 부분에서 삭제는 front부분에서 일어납니다. 활용 예시로는 운영체제의 스케줄링이나 너비우선탐색 알고리즘 구현 등이 있습니다.

- 트리: 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태로, 계층이 있는 데이터를 표현하기 적합합니다.

- 힙: 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드의 값이 자식의 값보다 크거나(최대힙) 자식의 값보다 작은(최소힙) 이진트리입니다.

 

 

힙의 삽입과 삭제 과정에 대해서 설명해주세요

- 삽입의 경우 맨 끝 리프 노드를 생성하여 값을 추가하고 부모의 값과 비교하여 만약 최대힙의 경우 부모의 값이 더 큰 경우가 나올때까지 비교와 교환의 과정을 반복합니다. 완전이진트리에서 높이는 log(n)에 해당하므로 시간복잡도는 O(logn)이 됩니다. 삭제의 경우 맨 위 노드의 삭제를 의미하고 루트 노드와 맨 마지막 리프 노드를 바꾼 후 리프 노드는 삭제를 하고 바뀐 루트 노드는 제자리를 찾아갈때까지 자식노드와 값을 비교하고 교환하는 과정을 반복합니다. 삭제 역시 O(logn)이 됩니다.

 

 

우선순위 큐에 대해서 설명해주세요

- 우선순위 큐는 가장 우선순위가 높은 데이터를 꺼내기 위해 고안된 자료구조로 일반적으로 힙을 사용하여 구현하며 시간복잡도는 O(logn)입니다.

 

 

완전이진트리란 무엇인가요?

- 루트 노드부터 시작하여 각 레벨마다 노드가 왼쪽에서 오른쪽으로 채워지며 마지막 레벨을 제외한 모든 레벨은 노드로 완전히 채워져 있어야 하는 특수한 형태의 이진트리를 의미합니다. 완전이진트리에서의 높이는 logn이 되며 한쪽으로 완전히 편향된 이진트리의 경우 높이는 n이 됩니다.

 

 

포화이진트리란?

- 리프노드까지 완벽하게 가득찬 이진트리를 의미합니다.

 

 

BST에 대해서 설명해주세요

- 이진탐색트리란 이진 탐색과 연결리스트를 결합한 자료구조로 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 모든 값이 부모 노드보다 커야하는 특징을 가진 자료구조입니다. 탐색, 삽입, 삭제의 시간복잡도는 O(h)이며 트리의 균형이 깨지면 높이가 커지기 때문에 균형을 맞춘 트리가 avl tree입니다.

 

해시 테이블에 대해서 설명해주세요

- 해시 테이블은 키, 밸류로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용합니다. 해시 테이블은 key값에 해시함수를 적용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 자료구조입니다. 시간복잡도는 평균적으로 O(1)이지만 인덱스 값이 충돌될 경우 O(n)까지 증가할 수도 있습니다.

 

 

자바의 hashmap과 hashtable의 차이점에 대해서 설명해주세요

- 해시 테이블의 경우 동기화 지원을 해줍니다.

 

 

Array와 LinkedList의 차이에 대해서 설명해주세요 - 삽입, 삭제는 연결리스트가 조회는 배열이 유리하다!!!!

- 배열은 데이터가 실제로 인접한 메모리에 연이어 저장되고 인덱스를 통해 접근이 가능하기 때문에 특정 요소에 접근하는데 걸리는 시간복잡도는 O(1)입니다. 하지만 linkedlist의 경우 데이터가 실제로 인접한 메모리에 저장되는 것이 아니라 다음 데이터의 주소를 이전 데이터가 저장하는 방식이기 때문에 랜덤 엑세스가 되지 않고 순차적으로 접근해야 하기 때문에 시간복잡도가 O(n)이 됩니다.

- 삽입과 삭제의 경우 배열은 중간 데이터를 삽입 및 삭제하는 경우 나머지 데이터를 옮기는 작업이 필요하여 시간복잡도가 O(n)이 되지만 LinkedList의 경우 O(1)이 됩니다.

 

 

ArrayList와 LinkedList의 차이에 대해서 설명해주세요

1. 공간적 제약

• ArrayList : 결국 배열이므로 길이가 고정되어 있습니다. 때문에, 새로 배열에 새로운 요소를 추가하려고 할 때, 배열의 용량이 이미 가득 차있다면 새로운 배열을 생성해주어야 합니다. 이 때, 새로 생성된 배열이 메모리 상에 연속해서 생길 수도 있지만, 이미 다른 값이 메모리를 사용하고 있는 경우, 새로운 위치에 배열이 생성되어야 하고 이는 모든 요소를 옮긴다는 얘기가 됩니다. 또 메모리에 여유공간이 없는 경우 에러가 발생할 수도 있습니다.
• LinkedList: 한 개의 Node는 다른 Node에 대한 참조만 가지고 있습니다. 따라서 공간적 제약을 ArrayList에 비해 받지 않습니다.

2. 새로운 요소 추가

• ArrayList : 새로운 요소를 추가할 때, 여유 공간이 있는 경우엔 O(1)이지만, 여유공간이 없는 경우엔 O(n)이므로 O(n)입니다.
• LinkedList : 새로운 요소를 추가할 때, 항상 O(1)입니다. 왜냐하면, 그냥 마지막 요소에서 다음 참조값을 가지게만 하면 되기 때문입니다.

3. 임의 접근과 순차 접근

• 임의 접근(Random Access) : 어떤 요소에 바로 접근하는 것.
• 순차 접근(Sequential Access) : 어떤 요소에 접근할 때, 차례차례 접근하는 것.
• ArrayList :임의 접근, 바로 접근이 가능하다는 것은 곧 O(1)을 의미한다.
• LinkedList : 순차 접근만 가능, O(n)이 걸리게 됩니다.

4. 새로운 요소 삽입(중간에)

• ArrayList는 해당 요소뒤의 요소들도 전부 옮겨야 합니다.
• LinkedList는 앞 뒤 요소의 값만 바꾸어주면 됩니다.

5. 요소 삭제(중간에)

• ArrayList는 뒤의 요소들을 전부 앞으로 이동시켜야합니다.
• LinkedList의 경우에는 앞 뒤 요소의 값만 바꾸어주면 됩니다.

 

 

스택과 큐의 차이점에 대해서 설명해주세요

- 스택은 후입선출의 구조를 가지고 데이터의 삭제와 삽입이 같은 곳에서 이뤄진다는 특징이 있으며 배열로 구현하면 삭제할 필요없이 인덱스를 조정하면 되기 때문에 배열로 구현하는 것이 좋으며 dfs나 재귀에서 활용합니다.

- 큐는 선입선출의 구조를 가지고 있고 맨 앞 데이터를 삭제해야 하기 때문에 LinkedList로 구현하는 것이 좋습니다. bfs에서 사용됩니다.

 

 

그래프와 트리의 차이에 대해서 설명해주세요

- 그래프는 정점(노드)과 정점들을 연결하는 간선으로 이뤄진 자료구조를 의미하며 트리는 그래프의 한 종류로 방향성이 있는 비순환 그래프를 의미합니다.

 

 

알고리즘

시간복잡도란 무엇인가요?

- 알고리즘의 입력 크기에 따라 실행에 필요한 시간을 나타내는 개념입니다.

 

 

빅오 표기법이 무엇이고 이 표기법이 널리 쓰이는 이유에 대해서 설명해주세요

- 알고리즘의 효율성을 점근적 표현법을 사용하여 표기한 방법으로 최악의 경우에 대한 시간복잡도를 나타냅니다. 빅오 표기법은 단순하게 알고리즘의 효율성을 나타낼 수 있다는 장점이 있고 결국 최선보다는 최악의 경우를 고려해야 하는 것이 더 중요하기 때문에 빅오 표기법을 많이 사용합니다.

 

 

점근적 표현법이란 무엇인가요?

- 임의의 함수가 무한대에 가까워질때 어떠한 형태에 근접해지는지 분석하는 방법으로 단순하게 함수의 형태만을 나타내는 표기법입니다.

 

 

stable sort와 unstable sort에 대해서 설명해주세요

- 동일한 값의 두 요소의 위치가 정렬 전후에 변하지 않는다면 stable sort라고 할 수 있습니다. 예시로는 버블 정렬, 삽입 정렬, 병합 정렬이 있습니다.

- unstable sort의 예시로는 퀵 정렬, 힙 정렬, 선택 정렬 등이 있습니다.

 

 

분할정복 알고리즘이란 무엇인가요?

- 해결하고자 하는 문제를 더 이상 나눌수 없을때까지 나눈 후 각각을 풀어서 다시 합병하여 전체 문제의 답을 얻는 알고리즘을 말합니다. 예시로는 퀵 정렬, 병합 정렬 등이 있습니다.

 

 

퀵 정렬과 병합 정렬의 차이점에 대해서 설명해주세요

- 둘 다 분할정복 기법을 사용한 정렬이지만 퀵 정렬은 배열의 형태일때 병합 정렬은 연결리스트 형태일때 유리하며 일반적으로는 퀵 정렬이 속도가 더 빠르며 병합 정렬은 임시 배열이 필요하다는 단점이 있습니다. 또한 퀵 정렬은 불안정 정렬이고 병합 정렬은 안정 정렬에 해당합니다.

 

 

정렬 알고리즘

- 버블 정렬: 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘, O(n^2)

- 선택 정렬: 각 사이클마다 최소 혹은 최대 값을 찾고 해당 인덱스의 값과 교환하는 방식, O(n^2)

- 삽입 정렬: 자신의 왼쪽에 위치한 원소들과 비교하여 삽입할 위치를 지정한 후, 원소들을 한칸씩 뒤로 옮기고 지정된 자리에 원소를 삽입하여 정렬하는 알고리즘입니다. 이미 정렬된 최선의 경우에 O(n)이며 안정 정렬이다.

- 퀵 정렬: 리스트 중 한 요소를 선택하고 이를 피봇으로 두고 피봇을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 옮기는 과정을 분할정복의 개념을 사용하여 한 개가 남을때까지 반복한다. 최선의 경우는 피봇을 기준으로 반반씩 나누어지는 경우이며 이 경우 시간복잡도는 O(n logn)이 되고(n번 비교를 높이만큼 하기 때문) 최악의 경우는 피봇이 최대, 최소 값인 경우이며 이때는 O(n^2)의 시간복잡도를 가진다.

- 병합 정렬: 퀵 정렬과 마찬가지로 분할 정복의 개념을 도입하였고 요소들을 더 이상 쪼갤수 없을때까지 쪼갠 후 각각을 병합하면서 정렬하는 방식을 사용합니다. 항상 O(n log n)의 시간복잡도를 가집니다.

- 힙 정렬: 힙 자료구조를 기반으로 하는 정렬방식으로 시간 복잡도는 O(n log n)에 해당합니다.

 

 

dfs와 bfs에 대해서 설명해주세요

- 그래프를 완전 탐색하는 방법들로 dfs의 경우 깊이 우선 탐색 방법으로 해당 방향으로 최대한 깊이 탐색한 후 더 이상 탐색할 곳이 없다면 다음 분기로 이동하는 방식이고 bfs의 경우에는 바로 인접한 곳들을 모두 탐색한 후 이후에 다음으로 인접한 모든 방향을 탐색하는 방식입니다. dfs의 경우 스택 또는 재귀함수로 구현을 하고 bfs의 경우 큐를 이용해서 구현합니다. 최단 거리를 구하는 경우 bfs를 이용하는 것이 유리합니다.

 

 

dp에 대해서 설명해주세요

- 동적계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 하나의 문제 해결 패러다임으로 볼 수 있습니다. 재귀와 방식이 비슷하지만 불필요한 반복적인 계산을 피할수 있다는 장점이 있습니다. dp의 사용조건으로는 부분 문제들이 겹침으로써 작은 문제의 답이 재사용될 수 있어야하고 최적 부분 구조를 가져서 작은 문제의 답이 결국 전체 답에도 적용이 되어야 한다는 조건이 필요합니다.

 

 

dp와 분할 정복의 차이점은 무엇인가요?

- 주어진 문제를 쪼개서 하위 문제로 해결하고 이를 통해 큰 문제를 해결하는 점은 같지만 분할 정복의 경우 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 사용한다는 것입니다. 예를 들어, 병합 정렬의 경우 분할된 하위 문제들이 독립적이기 때문에 dp를 사용할 수 없습니다.

 

 

 

참고 자료

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

https://notbusyperson.tistory.com/35

[면접용] 기본 정렬 알고리즘 정리