[CS 면접] 자료구조 및 알고리즘 - 3

보초님의 github에 있는 질문들을 보며 답변을 달아본 것입니다.

문제사항, 잘못된점 혹은 궁금한점이 있다면 댓글로 남겨주시면 감사하겠습니다.

이전 글을 읽지 않았다면 먼저 읽어보시면 좋습니다.

→ 보러가기

[CS 면접] 자료구조 및 알고리즘 - 2

Thread Safe 한 자료구조가 있을까요? 없다면, 어떻게 Thread Safe 하게 구성할 수 있을까요?

없습니다. mutex, 세마포어 와 같은 공유자원에 대해 잠금을 통해 Thread Safe 하게 구성할 수 있다.

배열의 길이를 알고 있다면, 조금 더 빠른 Thread Safe 한 연산을 만들 순 없을까요?

가능합니다. 배열의 길이가 고정되어 있으므로 Thread 별로 배열을 나누어 안전하게 작업할 수 있습니다.

사용하고 있는 언어의 자료구조는 Thread Safe 한가요? 그렇지 않다면, Thread Safe 한 Wrapped Data Structure를 제공하고 있나요?

Java : 별도의 Thread Safe 한 자료구조들을 제공합니다. ex) Concurrent ~, Atomic ~

Python : lock, 세마포어와 같은 별도의 동기화 모듈들을 사용해 thread safe 하게 구성해야 합니다.

문자열을 저장하고 처리하는 주요 자료구조 및 알고리즘 (Trie, KMP, Rabin Karp 등) 에 대해 설명해 주세요.

Trie : 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 빠르게 탐색할 수 있지만 공간복잡도가 크다는 단점이 있습니다. 제일 긴 문자열의 길이를 L, 총 문자열의 수를 M 이라고 하면 생성시 시간 복잡도는O(ML) 이고, 탐색은 O(L)입니다.

KMP : prefix==suffix 인 부분을 이용하여 O(NM)의 시간을 O(N+M)으로 줄여서 탐색할 수 있는 알고리즘입니다.

이진탐색이 무엇인지 설명하고, 시간복잡도를 증명해 보세요.

이진탐색은 upper bound 와 lower bound 의 중간값을 기준으로 목표값이 크다면 아래부분을 버리고 작다면 위에 부분을 버려 빠르게 범위를 좁혀가며 탐색할 수 있는 알고리즘입니다. 시간복잡도는 O(logN)입니다.

Lower Bound, Upper Bound 는 무엇이고, 이를 어떻게 구현할 수 있을까요?

경계값입니다. 해당 문제에서 가질 수 있는 가장 작은 값과 큰 값을 초기 값으로 하여 중간값으로 업데이트 하여 범위를 좁혀갑니다.

이진탐색의 논리를 적용하여 삼진탐색을 작성한다고 가정한다면, 시간복잡도는 어떻게 변화할까요?

가지수가 세개가 되면서 범위가 더 빠르게 줄어드므로 O(log3 N) 이 될것입니다. 하지만 각 단계에서 수행해야 하는 비교가 더 많아집니다.

기존 이진탐색 로직에서 부등호의 범위가 바뀐다면, (ex. <= 라면 <로, <이라면 <= 로) 결과가 달라질까요?

종료 조건이 달라지기 때문에 결과가 달라집니다. 예를 들어 배열이 [0,1]에서 1을 찾아야 한다면 mid = 0 이되어 start가 1이 되고 left < right 의 경우라면 값을 찾을 수 없지만 ≤ 의 경우라면 반복문이 한번 더 실행되어 값을 찾을 수 있게됩니다.

암호화 알고리즘에 대해 설명해 주세요.

대표적으로 대칭키 알고리즘과 비대칭키 알고리즘이 있습니다. 대칭키 알고리즘은 암호화와 복호화에 쓰이는 키가 같은 알고리즘으로 속도가 빠르지만 키를 전달하는 과정에서 유출의 우려가 있습니다. 이에 비해 비대칭키 알고리즘은 모두에게 공개된 공개키와 비공개된 개인키가 있습니다. 이를 이용해 공개키로 암호화하고 개인키로 복호화를 진행할 수 있는 알고리즘으로 속도는 느리지만 보안에 우수한 장점이 있습니다.

대칭키 알고리즘의 예시로는 AES, DES 등이 있고 비대칭키 알고리즘의 예시로는 RSA, ECC 등이 있습니다.

그리디 알고리즘과 동적 계획법을 비교해 주세요.

그리디 알고리즘은 순간의 최적해가 최종 최적해의 가까워질 때 사용할 수 있는 알고리즘입니다. 단조 증가 혹은 감소 형태일 때 사용할 수 있습니다. 동적 계획법은 순간의 최적해가 최종 최적해를 보장하지 않을 때 사용하는 방법입니다. 따라서 모든 경우의 수를 계산하여야 하고 시간이 더 오래걸리지만 항상 최적해를 구할 수 있다는 장점이 있습니다.

그렇다면 어떤 경우의 각각의 기법을 사용할 수 있을까요?

그리디 : 앞의 선택이 이후 선택의 영향을 주지 않고, 문제의 최종 해결방법이 부분 문제에 대한 최적 해결방법으로 구성되어 있을 때 사용가능합니다.

DP : 큰 문제를 작은 문제로 나누고, 작은 문제가 중복해서 발견되고 작은 문제에 구한 정답을 큰 문제에서 사용하는 경우에 사용합니다.

동적계획법으로 풀 수 있는 모든 문제는 재귀로 변환하여 풀 수 있나요?

재귀의 경우 문제의 범위에 따라 스택 오버플로우가 발생할 수 있는 여지가 있다.

 

---

출처

• vsfe github - tech interview