기술면접 예상질문 -알고리즘-

시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?

시간 복잡도(Time Complexity)는 입력 크기에 따라 알고리즘이 실행되는 시간이 어떻게 변화하는지를 나타냅니다. 입력 크기가 커짐에 따라 실행 시간이 얼마나 증가하는지를 의미합니다.

공간 복잡도(Space Complexity)는 입력 크기에 따라 알고리즘이 사용하는 메모리 공간이 어떻게 변화하는지를 나타냅니다. 입력 크기가 커짐에 따라 사용되는 메모리 공간이 얼마나 증가하는지를 의미합니다.

 

 

재미있게 공부한 알고리즘이 있다면 설명해주실 수 있을까요?

동적 계획법(Dynamic Programming)입니다. 동적 계획법은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 이미 계산된 하위 문제의 해답을 저장하여 중복 계산을 피하는 방식입니다. 예를 들어, 피보나치 수열을 계산하는 문제에서 동적 계획법을 적용하면 효율적으로 해결할 수 있습니다.

 

포트폴리오에서 시간복잡도를 낮춘 사례가 있다면 설명해주실 수 있을까요?

포트폴리오에서 시간 복잡도를 개선한 사례로는 "N개의 정수를 정렬하는 문제"가 있습니다. 처음에는 버블 정렬(O(n^2))을 사용했지만, 이후에 합병 정렬(O(n log n))로 변경하여 시간 복잡도를 개선했습니다. 대용량 데이터에 대해서는 시간 복잡도가 낮은 알고리즘을 선택하는 것이 중요합니다.

 

이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 중간 값과 찾고자 하는 값을 비교하여 탐색 범위를 절반씩 줄여나가는 방식으로 동작합니다. 시간 복잡도는 O(log n)입니다. 이는 탐색 범위가 절반씩 줄어들기 때문에 최악의 경우에도 log n 단계만에 답을 찾을 수 있기 때문입니다.

 

시간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?

더 효율적인 알고리즘을 찾아 사용합니다. 예를 들어, O(n^2)의 시간 복잡도를 가지는 알고리즘 대신 O(n log n)의 시간 복잡도를 가지는 알고리즘을 사용할 수 있습니다.

입력 데이터의 크기를 줄입니다. 데이터의 일부만 처리하거나 압축하여 데이터 크기를 줄일 수 있습니다.

분할 정복(Divide and Conquer) 기법을 활용하여 문제를 더 작은 부분 문제로 나누어 해결합니다. 이를 통해 전체 문제의 시간 복잡도를 낮출 수 있습니다.