자료구조3 배열(Array) 출처: https://blog.encrypted.gg/725?category=773649 배열은 메모리 상에 원소를 연속하게 배치한 구조입니다. 1. 장점 다른 자료구조와 달리 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리 양이 거의 없다는 점 2. 단점 반드시 메모리상에 연속한 구간을 잡아야하기 때문에 할당에 다시 제약이 걸린다는 점이 단점. 배열을 사용하는 경우 1. 인덱스에 해당하는 원소를 빠르게 접근해야 할 때 2. 아카이브처럼 데이터를 자주 바꾸거나 확인하는 일 없이 쌓아두고 싶을 때 (만약 데이터의 삽입/삭제가 빈번한 상황이라면 배열은 비효율적) 배열연산 시간복잡도 1. 임의의 위치에 있는 원소를 확인/변경 : 원소가 연속하게 배치되어 있으므로, 임의의 위치의 원소를 O(1)에 확인/변.. 2020. 5. 15. 해시 테이블 출처:https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ 이 포스팅은 Interview에 대한 대답 용도로 핵심부분만 요약해서 올린 포스팅입니다. 그러므로 자세한 부분은 다루지 않았고, 잘못된 부분에 대한 지적은 감사히 받겠습니다. 1. 정의 해시 테이블에 대해 설명을 하기 전에 몇 가지 단어에 대한 개념을 정리하겠습니다. Hashing: key를 해시값에 매핑하는 과정 자체를 의미합니다. Hash function: 데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 Hash Table: 해시 함수를 이용하여 key를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소로 삼아 데이터의 값을 .. 2019. 11. 4. 트리 이 포스팅은 Interview에 대한 대답 용도로 핵심부분만 요약해서 올린 포스팅입니다. 그러므로 자세한 부분은 다루지 않았고, 잘못된 부분에 대한 지적은 감사히 받겠습니다. 1. 정의 노드와 간선들로 이루어진 비선형 자료구조로 계층적 관계를 표현합니다. 2. 특징 / 특이사항 트리의 주목적은 탐색입니다. 트리는 계층적 관계에 있는 원소들을 나타내기에 편리한 추상데이터 타입입니다. 자식 노드의 개수는 트리의 주요 특징 중 하나입니다. 하나의 노드가 가질 수 있는 자식노드의 최대숫자가 2보다 큰 B-tree나, 자식노드의 최대숫자를 2개로 한정한 이진트리가 대표적인 예시입니다. 3. 접근시간 트리가 균형을 이룬 경우, 최대 트리의 높이만큼 탐색이 이뤄지므로 O(logN)의 시간복잡도. 트리가 편향된 경우,.. 2019. 11. 4. 이전 1 다음
