1. 시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?
- 시간복잡도 : 알고리즘이 문제를 해결하는 데 걸리는 시간입니다. 입력 데이터의 크기에 따른 연산 횟수로 표현되며, 보통 빅오(O) 표기법을 사용하여 최악의 경우 시간 복잡도를 나타냅니다.
- 공간복잡도 : 알고리즘이 문제를 해결하는 데 필요한 총 저장 공간을 나타냅니다. 이는 알고리즘에 필요한 임시 공간과 입력 데이터 공간을 포함하여 계산됩니다. 마찬가지로 빅오 표기법을 사용하여 표현합니다.
2. 재미있게 공부한 알고리즘이 있다면 설명해주실 수 있을까요?
3. 포트폴리오에서 시간복잡도를 낮춘 사례가 있다면 설명해주실 수 있을까요?
데이터베이스 조회 시간을 줄이기 위해 Redis를 이용하여 캐시를 도입한 경험이 있습니다. 데이터베이스 대신 빠른 접근이 가능한 캐시에서 데이터를 가져옴으로써 응답 시간을 단축시켜 결과적으로 시간 복잡도를 낮추는 효과를 얻었습니다.
4. 이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?
이분탐색은 정렬된 배열에서 특정 값을 찾는 알고리즘으로 배열의 중간 값을 선택하여 찾고자 하는 값과 비교한 후 탐색 범위를 반으로 줄여가면서 찾습니다.
이분탐색의 시간복잡도는 O(logn) 입니다. 그 이유는 탐색 범위가 절반 씩 줄어들기 때문입니다. 전체 데이터를 n개라 가정했을 때 k번째 탐색 후 데이터 수는 (1/2)^k x n 개가 됩니다. 최악의 경우 생각하고 계산해보면 k값은 logn인 것을 알 수 있습니다.
5. 시간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?
6. 공간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?
