# Foundation/자료구조 (16) # Foundation/자료구조 스택 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 스택 ADT 접시를 쌓고 빼는 것 처럼,나중에 삽입한 데이터가 먼저 빠져나오는 자료구조 인터페이스. Last-In First-Out (LIFO)First-In Last-Out (FILO) 스택 ADT의 특성 나중에 삽입한 데이터가 먼저 빠져나옴. (LIFO or FILO)스택의 TOP에서만 조회/삽입/삭제가 일어남. 구현에 따른 스택의 성능 스택의 TOP에서만 끝에서만 동작이 이루어지기 때문에,마지막 또는 첫번째 위치에서 효율적으로 동작하는 구현을 사용하는 것이 좋다. 배열?마지막 지점을 TOP으로 잡으면 성능이 좋다.노드기반이 아니라.. 2019. 2. 3. 21:12 # Foundation/자료구조 해시 테이블 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 해시 테이블 ADT 키-값 형식의 딕셔너리 구조체로,해시 함수의 입력으로 값을 넣고, 결과값을 키로 사용하는 자료구조 인터페이스. 배열을 미리 할당한 뒤,키에 대응되는 인덱스에 데이터를 저장한다.이때, 해시함수의 범위는 [0, 배열의 크기)로 정한다. (인덱스가 배열을 넘어가면 안되기 때문.) 해시 함수 값을 인자로 받아 키로 매핑하는 함수.해시 함수의 범위는 배열의 크기를 벗어나지 말아야 한다. 또한 해시 함수가 너무 복잡하거나 (해시 함수의 시간 복잡도가 너무 크거나), 너무 간단하면 (해시 함수의 결과 범위가 너무 작거나).해시 .. 2019. 2. 3. 20:32 # Foundation/자료구조 스킵 리스트 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 연결 리스트의 특성과 한계 어떤 위치든 O(1)시간만에 삽입/삭제가 가능.O(n)보다 빠르게 검색이 불가능함. (이분검색 불가능, eg.)중간범위를 점프하기 어려움. 스킵 리스트 정렬된 연결 리스트에 이분검색 이론을 접합시킨 유사 연결 리스트.추가적인 메모리를 지불하고, 평균 O(log n)에 해당하는 검색속도를 얻을 수 있다. 스킵 리스트의 특성 정렬된 상태의 연결 리스트에서만 사용가능탐색범위를 절반씩 줄이기 위해, log(n)개의 레벨을 갖음.각 레벨마다 헤더/센티넬 노드를 갖음. 각 데이터 노드는 유동적으로 최대 log(n)개의 .. 2019. 2. 3. 12:04 # Foundation/자료구조 벡터 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 벡터 배열처럼 인덱스를 통한 임의접근이 가능하고,연결 리스트처럼 논리적 수용량에 제한이 없는 고수준 배열(List).여러개의 배열(청크)이 모여 하나의 벡터를 이룬다. 꽉 찬 상태에서 데이터 삽입을 시도하면,새로운 메모리(청크)를 할당받아 뒤에 덧붙인다. 배열에서는 기존보다 더 큰, 아예 새로운 배열을 만들어야 했다. 벡터의 특성 여러개의 독립적인 배열(청크)을 접합한 것 이다.논리적 수용량의 제한이 없다.어느 위치에서든 데이터를 가져오는 것은 빠르다. (상수시간)램덤 액세스로 데이터를 가져올 때, 인덱스 계산으로 인한 약간의 오버헤드.. 2019. 2. 2. 23:57 # Foundation/자료구조 이중 연결 리스트 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 이중 연결 리스트 이전 노드의 정보도 갖고있는 연결 리스트. 원형 이중 연결 리스트 맨 마지막 노드가 다시 첫 노드를 가르킨다. 이중 연결 리스트의 특성 데이터가 메모리 위에서 인접하지 않는다.논리적 수용량의 제한이 없다.어느 위치든 데이터를 빠르게 삽입/삭제할 수 있다. (상수시간)중간에 위치한 데이터를 가져오는 것은 느리다. (선형시간)처음이나 마지막 위치에서 데이터를 가져오는 것은 빠르다. (상수시간) 이중 연결 리스트로 구현한 인터페이스의 특성 중간지점의 데이터를 조회하는데 시간이 오래 걸린다.처음 또는 마지막 부분만 조회할 것.. 2019. 1. 31. 19:54 # Foundation/자료구조 단일 연결 리스트 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/단일 연결 리스트데이터가 노드라는 작은객체에 저장되며, 다음 노드의 주소를 가지고 있지만,이전 노드의 주소는 가지고 있지 않은 저장방식. 원형 단일 연결 리스트맨 마지막 노드가 다시 첫 노드를 가르킨다. 단일 연결 리스트의 특성데이터가 메모리 위에서 인접하지 않는다.논리적 수용량의 제한이 없다.어느 위치든 데이터를 빠르게 삽입/제거할 수 있다. (상수시간)중간이나 마지막 위치의 데이터를 얻는것은 느리다. (선형시간)처음 위치에서 데이터를 얻는것은 빠르다. (상수시간) 단일 연결 리스트로 구현한 인터페이스의 특성 마지막 데이터를 조회하는데.. 2019. 1. 31. 19:45 # Foundation/자료구조 배열 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/배열 여기서 배열은 고정배열을 의미한다.동적이든 정적이든 생성되는 시점에서 크기가 고정된 배열을 의미한다. 배열의 특성 메모리 위에서 일렬로 인접하게 저장된다.한번 정해진 데이터의 수용량을 확장하기 힘들다.어떤 위치든 빠르게 데이터를 얻을 수 있다. (상수시간)처음이나 중간에 데이터를 삽입하려면 데이터를 한칸씩 뒤로 밀어내야 한다. (선형시간)처음이나 중간에 데이터를 삭제하려면 데이터를 한칸씩 앞으로 당겨야 한다. (선형시간)마지막 위치에서 데이터를 삽입/삭제하는 것은 빠르다. (상수시간) 배열로 구현한 인터페이스의 특성중간지점의 데이터.. 2019. 1. 31. 19:18 # Foundation/자료구조 자료구조와 추상적 자료형 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/자료구조란? (What is Data Strcture?) 큐, 스택, 링크드 리스트 같은 추상적 자료형에서의 효율적인 동작(알고리즘_)을 위해,메모리 내에서 다수의 정보를 어떻게 저장할지에 대한 방법. 자료구조의 연산 (Operation)접근 (access / Indexing)데이터의 값을 얻어오는 연산.자료구조마다 앞부분, 중간부분, 뒷부분의 접근 성능이 다를 수 있다.인덱스 번호를 통해 데이터의 값을 얻어오는 연산은 Indexing 이라고 한다.검색 (search)주어진 조건(최대, 최소, 등가 eg.)을 만족하는 데이터의 값을 얻어.. 2019. 1. 31. 18:58 이전 1 2 다음
