개발/자료구조 (2) 썸네일형 리스트형 [자료구조] List - 배열로 구현하기 "리스트를 배열로 구현한다"는 무슨 말일까? 리스트는 ADT(Abstract Data Type)이다. 즉, 리스트 자체는 인터페이스와 같은 추상적인 것이고 제시된 명세서에 따라 내부 구현은 각각 다를 수 있다. 이때 구현 과정을 배열로 하느냐, 링크드 리스트로 하느냐에 따라 내부적으로 다르게 구현된다. 리스트에서 명시한(구현해야 하는) 기능들이 있는데, 그 기능을 배열로 어떻게 구현하는지 설명하겠다. Add(index, data) 특정 구간에 삽입 - Big-O: O(N) 배열로 구현하였을 때, 특정 구간에 데이터를 삽입하는데 O(N)의 시간 복잡도를 가지게 된다. 특정 구간에 넣어줘야 할 때, 모든 요소를 한 칸씩 다 옮겨줘야 하는 경우가 최악의 경우 N이기 때문이다. remove(index) 특정 인.. [자료구조] Cache 자료구조(Data Structure)란? 사전적인 의미로는 자료(Data)의 집합을 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다. 자료구조를 사용하는 목적은 자료를 더 효율적으로 저장하고, 관리하기 위해 사용한다. 지난 학기 OS 수업 시간에 메모리 구성과 동작 과정에 대해 간단하게만 언급해주셨던 기억이 있다. 그 당시에는 LRU라던지 레지스터 등과 같은 개념을 사전적 정의로만 들어서 제대로 와닿지가 않았다. 지금은 메모리를 단계별로 구성하여 설명하겠다. CPU가 메모리에 접근하는 방식 CPU가 메모리에 접근하는 방식은 그림과 같다. 1. Cache에 접근하고자 하는 데이터(주소)가 있는지 확인한다. 2. 캐.. 이전 1 다음
