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

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

• 시간복잡도: 알고리즘이 문제를 해결하기 위해 필요한 시간을 나타내는 척도입니다. 이를 통해 데이터 크기에 따른 알고리즘의 실행 시간 증가율을 대략적으로 예측할 수 있습니다. 시간복잡도는 종종 Big O 표기법으로 표현되며, 주로 입력 크기에 따른 최악의 경우를 기준으로 합니다.

• 공간복잡도: 알고리즘이 문제를 해결하는 데 필요한 메모리 양을 나타내는 척도입니다. 시간복잡도와 마찬가지로 Big O 표기법으로 표현되며, 필요한 저장 공간의 증가율을 예측하는 데 사용됩니다.

Big 0 표기법이란?

• Big O 표기법 (Big O notation)은 알고리즘의 성능을 설명하는데 사용되는 수학적 표기법입니다. 이 표기법은 알고리즘의 최악의 경우에 대한 시간 복잡도나 공간 복잡도를 나타내는 데 주로 사용됩니다.

• Big O 표기법의 핵심 아이디어는 입력 크기가 증가함에 따라 어떻게 알고리즘의 실행 시간이 증가하는지를 간략하게 표현하는 것입니다. 이를 통해 알고리즘이 얼마나 "효율적"인지를 대략적으로 알 수 있습니다.

• O(1): 상수 시간 (Constant Time) - 입력 크기와 상관없이 일정한 시간이 걸립니다.

• O(log n): 로그 시간 (Logarithmic Time) - 이진 탐색처럼 입력 크기가 두 배로 증가할 때마다 실행 시간이 일정한 단위로 증가합니다.

• O(n): 선형 시간 (Linear Time) - 입력 크기에 비례해서 실행 시간이 증가합니다. 예를 들어, 단순 검색에서 리스트의 모든 요소를 확인해야 할 때 발생합니다.

• O(n log n): 선형 로그 시간 (Linearithmic Time) - 흔히 사용되는 정렬 알고리즘 중 몇몇이 이 시간 복잡도를 가집니다 (예: 병합 정렬).

• O(n^2), O(n^3), ...: 다항 시간 (Polynomial Time) - 중첩 루프와 같은 구조를 사용할 때 발생하는 시간 복잡도입니다. 예를 들어, 버블 정렬은 O(n^2)의 시간 복잡도를 가집니다.

• O(2^n): 지수 시간 (Exponential Time) - 알고리즘의 실행 시간이 입력 크기에 따라 지수적으로 증가합니다. 재귀적인 문제 해결 전략에서 흔히 볼 수 있습니다, 예를 들어 순수한 형태의 피보나치 수열 계산에서 발생합니다.

• O(n!): 팩토리얼 시간 (Factorial Time) - 순열 문제 같은 경우에 발생하는 시간 복잡도입니다.

Big O 표기법은 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라, 입력 크기가 증가함에 따라 실행 시간이 어떻게 증가하는지에 대한 상대적인 증가율을 나타냅니다.

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

• 그리디 알고리즘은 매 순간 최적이라고 생각되는 것을 선택하는 방법으로 문제를 해결하는 알고리즘입니다. 그리디 알고리즘은 모든 경우를 고려하지 않기 때문에, 실행 시간이 다른 알고리즘에 비해 빠르다는 장점이 있습니다. 하지만, 이로 인해 항상 최적의 해를 구할 수 있는 것은 아닙니다.

• 제가 그리디 알고리즘을 통해 흥미로운 경험을 한 예는 "거스름돈 문제"입니다. 상점에서 물건을 사고 거스름돈을 받을 때, 적은 수의 동전과 지폐로 거슬러 줘야 하는 문제입니다. 이 문제에서 그리디 알고리즘은 매 순간 가장 가치가 큰 동전이나 지폐를 최대한 많이 거슬러 주는 방식으로 문제를 해결합니다.

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

• 데이터 구조의 최적화: 적절한 자료구조의 선택은 알고리즘의 성능을 크게 향상시킬 수 있습니다. 예를 들어, 배열에서 요소를 찾는 데 O(n)의 시간이 걸리는 반면, 해시맵에서는 O(1)의 시간이 걸립니다.

• 알고리즘 최적화: 종종 더 효율적인 알고리즘을 찾거나 현재의 알고리즘을 최적화하여 성능을 향상시킬 수 있습니다.

• 메모이제이션: 이미 계산된 결과를 저장해 두고 나중에 재사용하는 기법으로, 동적 프로그래밍에서 주로 사용됩니다.

• 병렬 처리: 멀티 코어나 분산 시스템을 활용하여 여러 작업을 동시에 처리하도록 설계하여 시간을 절약할 수 있습니다.

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

• 이분 탐색은 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘이며, 매 단계에서 배열의 중앙값을 대상 값과 비교합니다. 일치하면 위치를 반환하고, 그렇지 않으면 대상 값을 초과하면 오른쪽 하위 배열에서, 미만이면 왼쪽 하위 배열에서 탐색을 계속합니다. 시간복잡도는 O(log n)입니다. 이유는 배열을 절반씩 줄여나가며 탐색하기 때문에 로그 시간에 원하는 값을 찾을 수 있기 때문입니다.

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

• 코드 최적화: 불필요한 연산을 제거하거나 효율적인 알고리즘을 선택합니다.
• 메모이제이션: 이전에 계산한 결과를 저장해 불필요한 계산을 줄입니다.
• 병렬 처리: 여러 처리 유닛을 활용하여 작업을 동시에 수행합니다.

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

• 데이터 구조 최적화: 필요한 데이터만 저장하며, 메모리 효율이 좋은 자료구조를 사용합니다.
• 메모리 풀링: 객체를 재사용하여 메모리 할당과 해제를 줄입니다.
• 압축 기술: 데이터를 압축하여 메모리 사용량을 줄입니다.