자료구조17 [Data Structure] 비선형 - Hash Table(해시 테이블) Hash Table(해시 테이블) 해시 테이블은 '키-값'쌍으로 데이터를 저장하는 자료구조 중 하나로 빠른 검색, 빠른 삽입이 가능하다는 특징을 가진다. 해시 테이블이 빠르게 데이터에 접근할 수 있는 이유는 내부적으로 배열(버킷)을 사용해서 데이터를 저장하기 때문이다. 배열에 저장된 데이터를 데이터 고유의 인덱스로 접근하기 때문에 평균적으로 O(1)의 시간 복잡도로 검색할 수 있다. 고유 인덱스는 데이터의 키 값에 해시 함수(hash function)을 적용해 생성한다. Hash Function 적절한 해시 함수를 사용하는 것은 매우 중요하다. 각각 데이터는 데이터 고유의 인덱스를 가져야 하는데, 어설픈 해시 함수를 사용할 경우 인덱스가 많이 겹치는 경우가 발생할 수 있기 떄문이다. 이 경우를 'coll.. 2023. 2. 21. [Data Structure] 선형 - Queue(큐) Queue (큐) 스택과 반대로 먼저 저장된 것이 제일 먼저 나온다. 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다. 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out) 또는 LILO(Last-In, Last-Out) 방식. Ex) 큐 구현 class Queue { constructor() { this.storage = {}; // 여기에 담는다. this.front = 0; this.rear = 0; } size() { return Object.keys(this.storage).length; } // 큐에 데이터를 추가 할 수 있어야 한다. enqueue(element) { this.storage[this.rear] = element; this.rear += .. 2023. 2. 21. [Data Structure] 선형 - Stack(스택) Stack (스택) 순서가 보존되는 선형 데이터 구조 가장 마지막 요소(가장 최근 요소)부터 처리하는 LIFO (Last In First Out) 또는 FILO(First-In, Last-Out)데이터 관리방식을 따름 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 데이터를 제한적으로 접근할 수 있는 구조 → 실행 취소 → 수학적 표현식을 구문 분석하고 평가 → 재귀 프로그래밍에서 함수 호출을 구현 2023. 2. 21. [Data Structure] 선형 - Linked List(연결 리스트) Linked List (연결 리스트) 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조 동적인 데이터 추가/삭제에 유리하다. 각 요소는 Node 각 Node에는 key와 다음 노드를 가리키는 포인터인 next가 포함 (참조한다) 첫 번째 요소는 Head 마지막 요소는 Tail → Alt + Tab을 사용하여 프로그램 간 전환 → 갤러리 연결 리스트의 장점 리스트 길이가 가변적이라 배열의 단점을 커버 할 수 있다. 연결 리시트의 단점 어떤 노드를 Search하거나 데이터를 변경할때 바로 찾아낼 수 없다. 사용 데이터가 자주 추가되거나 가변적으로 자주 변하게 될 프로그램이면 링크드리스트를 쓰는것이 좋고, 주로 데이터의 변경이나 탐색을 위한것이라면 배열을 쓰는것이 좋다. 2023. 2. 21. [Data Structure] 선형 - Array(배열) Array(배열) 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있다. 인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있다. → 배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용 → 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용 데이터를 나열하고, 각 데이터를 인덱스에 대응해주고 인덱스로 데이터를 접근할 수 있도록 구성된 데이터 구조 파이썬에서는 리스트 타입이 배열기능을 제공 배열이 왜 필요할까? - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 배열의 장점 - 인덱스로 인한 빠른 접근 가능 배열의 단점 - 미리 배열의 크기를 설정해줘야함으로 데.. 2023. 2. 20. [Data Structure] 자료구조란? 자료구조란? (Data Structure) 사전적인 의미는 자료(Data)의 집합의 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이라고 한다. 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료구조라는 이름을 붙였다. 자료구조를 쓰는 목적 이러한 자료구조를 사용하는 목적은 명확하다. 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다. 자료구조의 선택 기준 적은 양의 데이터를 처리할 때는 어떤 자료구조를 사용하든 큰 차이가 없다. 그러나 대량의 데이터를 한 번에 처리함에 있어서 어떤 자료구조를 사용하.. 2023. 2. 20. [Technical Organize] 기술면접_자료구조&알고리즘 문제. 시간복잡도란 알고리즘을 구성하는 명령어들이 몇번이나 실행됬는지 센 결과(frequency count) + 각 명령어의 실행시간(execution time) 을 곱한 합계를 의미함 그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다. 시간의 복잡도는 크게 세가지로 나눌 수 있다. 최상의 경우, 최악의 경우, 평균 => 이래서 표기법도 3개가 존재하는것이다. 시간과 공간은 반비례 하는 경향이 있다. 요즘은 공간보다는 시간이 우선이다! 정의 : 프로그램을 실행시켜 완료하는데 걸리는 시간을 의미한다. 어떤 프로그램의 실행 시간을 추정하기 위해서는 .. 2022. 12. 28. 이전 1 2 다음
