태어나 처음으로 스터디 카페라는 곳에 와봤다. 열심히 공부하시는 분들이 많다.
오늘 스터디 할 내용은 기술 면접 스터디이다.
해당 내용들을 정리해보니 코딩 테스트 공부하면서 접했던 내용들이 겹치는 부분이 있다.
데이터 구조와 알고리즘 기술 면접 스터디
💡의도 : 이 카테고리는 데이터를 효과적으로 관리하고 알고리즘을 통해 문제를 해결하는 능력을 평가합니다. 개발자는 다양한 데이터 구조(배열, 리스트, 해시맵 등)을 이해하고, 시간 복잡도와 공간 복잡도를 고려하여 적절한 알고리즘을 선택할 수 있어야 한다. 이 질문들은 실무에서 효율적인 코드 작성과 성능 최적화를 얼마나 잘할 수 있는지 평가하는데 사용된다.
답변에 포함해야 할 키워드
- 스택(Stack), 큐(Queue) : 선입선출/휴입선출 원칙
- 해시맵 : 키-값 쌍으로 데이터를 저장하는 구조
- 트리(Tree), 그래프(Graph) : 계층적 데이터 구조와 네트워크 데이터 구조
- 시간 복잡도(Big-O) : 알고리즘의 효율성 측정
- 정렬 알고리즘 : 퀵 정렬, 병합 정렬 등의 시간 복잡도 비교
- [하] Object의 특성에 따라 사용할 수 있는 데이터 구조에는 어떤 것이 있는지 설명해주세요.
Object의 특성에 따라 순차적 데이터의 경우 배열, 연결리스트가 있으며, 빈번한 삽입/삭제의 경우 연결리스드, 스택, 큐가 적합하다. 검색 속도가 중요한 경우 해시테이블, 이진 탐색 트리를 사용하며, 계층 구조 데이터는 트리가 적합하다. 네트워크나 관계형 데이터는 그래프를 사용하고, 중복을 허용하지 않는 데이터는 Set을 활용한다.
- [중] 스택(Stack)과 큐(Queue)의 차이점과 실제로 사용되는 사례를 설명해주세요.
스택은 LIFO 후입선출 방식으로 동작하며, 재귀 함수나 깊이 우선 탐색에 사용된다. 큐는 FIFO 선입선출 방식으로 동작하며, 네트워크 패킷 처리, 메시지 큐, 너비 우선 탐색에 사용된다.
- [중] 연결 리스트(Linked List)의 구조와 사용 사례를 설명해주세요.
연결리스트는 노드들이 포인터로 연결된 자료 구조로 크기 변경이 자유롭고 삽입/삭제가 빠르다 그래프 구현, 동적 메모리 할당 등에 사용된다.
- [상] 해시맵(HashMap)과 트리(Tree)의 차이점은 무엇이며, 각각 언제 사용하면 좋을지 설명해주세요.
해시맵과 트리는 데이터 저장 방식과 검색 속도에 차이가 있다.
해시맵은 키-값 쌍을 해시함수를 통해 저장하며, 평균적으로 오일 O(1)의속도로 데이터를 검색할 수 있어 매우 빠르지만, 데이터 순서는 보장되지 않는다. 반면 트리는 계층 구조로데이터를 저장하며 형태를 유지할 수 있어 범위검색이나 정렬이 필요할 때 유리하다. 다만 검색 속도가 오로그엔 O(log n)으로 해시맵보다는 상대적으로 느릴 수 있다.
따라서 해시맵은 빠른 조회가 필요한 키-값 데이터 저장에 적합하며, 트리는 범위검색이나 정렬된 데이터 유지가 필요한 경유 적합하다.
- [상] 트리(Tree)와 그래프(Graph)의 차이점을 설명하고, 각각의 장단점을 이야기해주세요.
트리(Tree)는 계층적 구조로, 하나의 루트 노드에서부터 자식 노드로 단방향으로 분기되며, 순서가 정해져 있고 사이클이 없습니다.
그래프(Graph)는 비계층적 구조로, 노드 간에 다양한 방향으로 연결이 가능하고, 사이클도 존재할 수 있어 트리보다 더 자유로운 구조입니다.
트리의 장점은 구조가 단순하고 탐색/삽입/삭제가 효율적입니다. 그러나 구조가 고정적이어서 복잡한 관계나 연결을 표현하기 어렵고, 불균형 트리에서는 성능이 저하될 수 있습니다.
그래프의 장점은 복잡한 관계나 다양한 연결을 표현할 수 있으며, 사이클이나 양방향 관계도 처리 가능합니다. 하지만 구현이 복잡하고, 탐색이나 연산이 상대적으로 비효율적일 수 있습니다.
- [중] 배열(Array)과 연결 리스트(Linked List)의 차이점과 시간 복잡도를 설명해주세요.
배열은 연속된 메모리 공간에 데이터를 저장하며, 인덱스를 통해 빠르게 데이터를 접근할 수 있어 검색이 오일 O(1) 시간 복잡도를 가집니다. 그러나 배열의 중간에 삽입이나 삭제를 할 경우 나머지 요소들을 이동해야 하므로 시간 복잡도는 오엔 O(n)입니다.
번면 연결 리스트는 각 노드가 데이터를 저장하고 포인터로 다른 노드를 가리키는 방식으로 메모리에 비연속적으로 저장됩니다. 따라서 연결 리스트는 랜덤 접근이 불가능하여 검색 시 오엔 O(n) 시간이 걸리며 삽입과 삭제는노드를 찾은 후 오일 O(1)로 빠르게 처리할 수 있습니다.
- [중] 빅오(Big-O) 표기법이란 무엇이며, 자주 사용되는 데이터 구조의 시간 복잡도를 설명해주세요.
빅오 표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 표현하는 방식으로 입력 크기가 커질 때 알고리즘이 얼마나 효과적인지를 나타내는데 빅오는 최악의 경우를 기준으로 성능을 측정
배열은 검색은 오일 삽입/삭제는 오엔 연결 리스트는 검색은 오엔 삽입/삭제는 오일 스택/큐는 삽입/삭제 다 오일 해시맵은 검색/삽입/삭제 다 오일인다 충돌시는 오엔이다 이진 탐색 트리는 검색/삽입/삭제 다 오 로그엔이다
- [상] 이진 탐색(Binary Search) 알고리즘을 설명하고, 시간 복잡도를 이야기해주세요.
이진 탐색 알고리즘은 정렬된 배열에서 원하는 값을 반씩 나누며 찾는 효율적인 검색 방법이다. 배열의 중간 값을 선택하고, 찾고자 하는 값이 중간 값보다 크거나 작은지에 따라 탐색 범위를 반으로 줄여가며 계속 비교합니다.
이진 탐색의 시간 복잡도는 매번 검색 범위를 절반으로 줄여가므로, 탐색 횟수는 배열 크기 n에 대해 로그 비례하여 증가합니다.
- [상] 정렬 알고리즘 중 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)의 차이점을 설명하고, 각각의 시간 복잡도를 이야기해주세요.
두 알고리즘 모두 분할 정복 방식이지만, 퀵 정렬은 피벗을 기준으로 나누고 병합 정렬은 배열을 반으로 나누어 병합하는 방식에 차이가 있습니다.
퀵 정렬은 평균적으로 빠르지만 최악의 경우 시간 복잡도가 오엔제곱이 될 수 있습니다. 인플레이스 정렬이면 메모리 공간을 적게 사용합니다.
병합 정렬은 항상 오엔로그엔 시간 복잡도를 보장하며, 안정적인 정렬을 제공합니다. 그러나 추가적인 메모리 공간이 필요합니다.
- [상] 그래프에서 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 차이점과 사용 사례를 설명해주세요.
DFS는 깊이를 우선적으로 탐색하며, 스택을 이용해 깊이 있는 노드를 먼저 탐색합니다 주로 경로 찾기나 위상 정렬에 사용됩니다. 반면 BFS는 너비를 우선적으로 탐색하며, 큐를 이용해 각 레벌의 노드를 순차적으로 탐색합니다. 최단 경로나 레벨 단위 탐색에 유리합니다.
