자료구조(data structure)가 무엇인지 설명해주세요?
데이터 저장을 시작으로, 데이터를 어떤 형태로 조직하느냐에 따라 프로그램의 성능, 시간복잡도, 공간복잡도에 지대한 영향을 미치는 존재입니다.
자료구조의 예시로는 링크드 리스트, 어레이 등이 있습니다.
시간 복잡도와 공간 복잡도를 말씀하셨는데 조금 더 구체적으로 설명해주세요.
- 시간 복잡도는 알고리즘이 특정 작업을 완료하는 데 최악의 상황에 걸리는 시간의 양을 나타냅니다.
- 공간 복잡도는 작업을 완료하는 데 필요한
메모리 공간의 양을 나타냅니다. - 이것이 중요한 이유는 개발자가 만든 프로그램이 어떤 환경에서 얼마나 빠르게 작동하고 얼마나 적은 자원을 사용하는지를 예측하고 평가하는 기준이 되기 때문입니다.
어레이과 링크드 리스트의 특징과 다른점 그리고 어떠한 상황에 쓰나요?
-
어레이 같은 타입의 데이터를 메모리상에 연속적으로 할당하여 저장합니다.
인덱스를 통해 아주 빠른 시간(O(1)) 안에 접근할 수 있는 강점이 있습니다.
하지만, 한번 선언된 크기를 변경하는 것은 어렵고, 중간에 데이터를 삽입하거나 삭제할 때 해당 위치 뒤에 데이터를 모두 옮겨야합니다.
예시) [0,1,2,3,4] --2에 해당하는 인덱스 없애고 싶어--> [0,1,3,4] == 2가 사라지면서 3의 인덱스는 3->2 변경, 4의 인덱스는 4->3 변경 -
링크드 리스트는 각 노드가 데이터와 다음 노드의 주소를 가지고는 비연속적인 메모리 공간에 저장됩니다.
어레이처럼 데이터가 차곡차곡 쌇여있는게 아닌, 중구난방으로 데이터가 위치합니다.
차곡차곡 쌓인것이 아니기 때문에 원하는 곳에 노드를 만들어 삽입 혹은 삭제가 간단합니다.
다음 노드의 주소만 바꿔주면 되기 때문입니다.
하지만, 특정 데이터를 찾기 위해서는 처음 노드부터 순차적으로(O(N)) 찾아야하기 때문에 느린 편입니다. -
결론적으로, 크기가 고정적인 경우에는 배열, 삽입/삭제가 빈번하다면 링크드 리스트 사용하는게 좋습니다.
만약 크기가 고정이 아니지만 중간 삽입/삭제가 아니라면 어레이 리스트를 사용하는게 효율적입니다.
개발에서 특히 중요하다고 생각하는 자료구조가 있나요?
모든 자료구조가 중요하다고 생각하지만, 지금 머릿속에 떠오르는 것은 해시 테이블입니다.
키-벨류 형태로 데이터를 저장하고 빠르게 검색, 삽입, 삭제할 수 있어 인증 정보 관리, 캐싱 시스템 구현, API 요청 처리 등 다양한 곳에 활용됩니다.
