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

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

시간 복잡도 (Time Complexity)
시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타냅니다. 이것은 입력 크기에 대한 함수로 표현되며, 일반적으로 "빅 오" 표기법을 사용하여 나타냅니다. 예를 들어, O(n)은 입력 크기에 대해 선형적으로 증가한다는 것을 의미하며, O(log n)은 로그 시간에 비례한다는 것을 의미합니다. 좋은 알고리즘은 작은 입력에서도 빠르게 실행되고, 입력이 커져도 효율적으로 처리할 수 있어야 합니다.

공간 복잡도 (Space Complexity)
공간 복잡도는 알고리즘이 실행되는 동안 사용되는 메모리 양을 나타냅니다. 이것도 입력 크기에 대한 함수로 표현되며, 빅 오 표기법을 사용하여 표현됩니다. 공간 복잡도를 최소화하는 것은 메모리를 효율적으로 활용하는 중요한 부분입니다. 좋은 알고리즘은 적은 메모리를 사용하여 원하는 결과를 얻을 수 있어야 합니다.

간단히 말하면, 시간 복잡도는 실행 시간에 대한 것이고, 공간 복잡도는 메모리 사용에 대한 것입니다.

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

이분탐색은 주로 정렬된 데이터에서 사용되며, 데이터를 정렬하는 데에는 추가적인 시간이 소요되지만 탐색에서 얻는 이점이 더 크기 때문에 정렬된 데이터에서 매우 유용합니다.

이분탐색의 원리
배열의 중간 값과 찾고자 하는 값을 비교합니다.
찾고자 하는 값이 중간 값보다 작으면 중간 값의 왼쪽 반을 대상으로 이진 탐색을 수행합니다.
찾고자 하는 값이 중간 값보다 크면 중간 값의 오른쪽 반을 대상으로 이진 탐색을 수행합니다.
찾고자 하는 값이 중간 값과 일치하면 원하는 값을 찾은 것이므로 알고리즘을 종료합니다.

시간 복잡도
이분탐색의 시간 복잡도는 O(log n)입니다. 이는 탐색 범위를 반으로 나누기 때문에 탐색 시간이 로그의 형태로 감소하기 때문입니다. 이는 선형 탐색의 O(n)과 비교하면 훨씬 효율적입니다. 이러한 특성으로 인해 이분탐색은 대량의 데이터에서 빠르게 특정 값을 찾을 수 있는 강력한 알고리즘으로 사용됩니다.

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

1. 다이나믹 프로그래밍 활용
중복되는 계산을 피하고 중간 결과를 저장하여 계산 속도를 향상시키는 방법입니다.
큰 문제를 작은 부분으로 나누어 푸는데, 한번 푼 작은 문제의 해결책을 기억하고 재활용함으로써 중복 계산을 줄입니다.

2. 그리디 알고리즘 사용
그리디 알고리즘은 각 단계에서 가장 최선의 선택을 하는 방법입니다.
주어진 문제에 대해 항상 현재 상태에서 가장 최선의 선택을 하는 그리디 전략을 적용하면, 전체적으로 최적의 해를 찾을 수 있습니다.

3. 데이터 구조 최적화
적절한 데이터 구조와 선택은 알고리즘 성능에 큰 영향을 미칩니다.
특정 작업에 효율적인 자료 구조를 사용하면 알고리즘의 성능을 향상시킬 수 있습니다. 예를 들어, 해시 테이블이나 힙 같은 자료 구조를 적절히 사용하면 일부 문제에서 빠른 속도를 얻을 수 있습니다.

상황에 따라 조합하여 사용하는 것이 중요하며, 코드의 가독성과 유지보수성을 고려하여 최적화를 진행하는 것이 좋습니다.

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

1. 데이터 압축 활용
데이터를 압축하여 저장하면 메모리를 효과적으로 활용할 수 있습니다.
예를 들어, 특정 형식의 데이터에서 중복되는 부분을 찾아내고 이를 압축하여 저장함으로써 메모리 사용을 최소화할 수 있습니다.

2. 데이터 구조 최적화
적절한 데이터 구조의 선택은 공간 복잡도에 큰 영향을 미칩니다.
필요한 기능을 수행하는데 최소한의 메모리를 사용할 수 있는 자료 구조를 선택하는 것이 중요합니다. 예를 들어, 트리나 해시맵은 특정 상황에서 메모리를 효율적으로 활용할 수 있는 자료 구조입니다.

3. 비트 연산 활용
비트 연산을 통해 데이터를 효과적으로 압축하거나 표현할 수 있습니다.
비트 연산을 사용하여 여러 가지 정보를 하나의 변수에 효과적으로 저장하면 공간을 절약할 수 있습니다. 이는 특히 대량의 데이터를 다룰 때 유용합니다.