Computer Science (42) 썸네일형 리스트형 [DS] Array & Linked List 1. Array 가장 기본적인 자료구조로 메모리 상에 같은 타입의 데이터가 연속적으로 저장되어 있다. 이러한 구조는 첫번째 원소의 위치를 기본 index로 offset을 더하여 이어지는 원소들의 위치를 계산하기에 쉽다. 이때문에 array는 논리적 저장순서와 물리적 저장순서가 일치한다. 따라서 index를 통해서 원소에 랜덤하게 접근이 가능하다. 따라서 검색 time complexity 는 O(1) 이다. 검색과 달리 삭제와 삽입 등의 과정에서는 해당 원소에 접근하여 작업을 완료한 후 빈 공간에 대해서 다른 원소들을 shifting 해줘야 하는 cost가 발생하고 이 경우의 시간 복잡도는 O(N)이 된다. 그렇기 때문에 array 값의 삽입, 삭제의 Time complexity는 O(N) 이다. 2. L.. [DS] 자료구조 개념 및 종류 1. 자료구조란? 자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. 대부분의 언어는 일정 수준의 모듈 개념을 가지고 있으며, 이는 자료구조가 검증된 구현은 감춘 채 인터페이스만을 이용하여 다양한 프로그램에서 사용되는 것을 가능하게 해준다. 2. 자료구조.. 이전 1 ··· 3 4 5 6 다음
