자료구조, 알고리즘 면접 질문

시간복잡도와 공간복잡도는 알고리즘의 성능을 측정하는 방법입니다.

시간복잡도

알고리즘이 입력 크기에 따라 실행에 필요한 시간을 나타냅니다. 일반적으로 Big O 표기법을 사용하여 나타냅니다. 예를 들어, O(n)은 입력 크기에 선형으로 비례하는 시간복잡도를 의미합니다.

공간복잡도

알고리즘이 실행 중에 필요로 하는 메모리 공간의 양을 나타냅니다. 마찬가지로 Big O 표기법을 사용하여 표현하며, 예를 들어, O(1)은 상수 크기의 공간을 의미합니다.

시간복잡도가 높은 경우 대처할 수 있는 전략

• 알고리즘 최적화: 알고리즘을 더 효율적으로 구현하거나 다른 알고리즘으로 대체하여 시간복잡도를 낮출 수 있습니다.
• 데이터 구조 최적화: 데이터 구조를 선택적으로 변경하여 알고리즘의 성능을 향상시킬 수 있습니다.
• 병렬 처리 또는 분산 처리: 병렬 컴퓨팅 또는 분산 시스템을 사용하여 계산을 병렬화하고 시간을 절약할 수 있습니다.

공간복잡도가 높은 경우 대처할 수 있는 전략

• 데이터 압축: 데이터를 압축하여 메모리 사용량을 줄일 수 있습니다.
• 메모리 관리 최적화: 메모리 관리 기술을 사용하여 메모리 사용을 최적화할 수 있습니다.
• 외부 메모리 알고리즘: 대용량 데이터 처리 시 외부 메모리 알고리즘을 사용하여 제한된 메모리를 효율적으로 활용할 수 있습니다.

이분탐색(Binary Search)

은 정렬된 배열에서 원하는 값을 찾는 알고리즘입니다. 이 알고리즘은 중간값을 선택하고 찾고자 하는 값과 비교하며, 배열을 절반으로 줄여나가는 방식으로 동작합니다. 시간복잡도는 O(log n)입니다. 이유는 이분탐색이 매 단계에서 현재 배열 크기를 절반으로 줄이기 때문입니다.

스택(Stack)과 큐(Queue):

스택

후입선출(LIFO) 구조를 가지며, 데이터를 삽입(push)하고 삭제(pop)하는데 사용됩니다. 함수 호출 스택, 브라우저의 뒤로 가기 기능 등에서 활용됩니다.

큐

선입선출(FIFO) 구조를 가지며, 데이터를 삽입(enqueue)하고 삭제(dequeue)하는데 사용됩니다. 대기열, 태스크 스케줄링 등에서 활용됩니다.

배열과 링크드 리스트 비교:

배열

고정된 크기를 가지며 연속된 메모리 공간에 요소를 저장합니다. 빠른 접근과 인덱싱이 가능하지만 크기 변경이 어려워요.

링크드 리스트

동적 크기를 가지며 불연속된 메모리 공간에 요소를 저장합니다. 삽입, 삭제가 쉽지만 접근 시간이 더 오래 걸립니다.

해시테이블의 원리와 충돌 해소 전략

해시테이블은 키-값 쌍을 저장하고 검색하기 위한 자료구조로, 해시 함수를 사용하여 키를 해시값으로 변환합니다.

충돌 해소: 다른 키가 같은 해시값을 가질 때 충돌이 발생하며, 이를 해결하기 위한 방법으로는 체이닝, 개방 주소법 등이 있습니다.

우선순위 큐의 시간복잡도

우선순위 큐는 가장 높은 우선순위를 가진 요소를 빠르게 찾기 위한 자료구조입니다.

시간복잡도는 구현 방식에 따라 다를 수 있지만 일반적으로 삽입, 삭제, 최대값 찾기 연산의 시간복잡도는 O(log n)입니다. 이유는 효율적인 데이터 정렬과 관련이 있습니다.