컴공생의 개인공부일지

트리 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드 집합 재귀로 정의된 자기 참조 자료구조(여러 개의 트리가 쌓아 올려져 큰 트리가 됨) 트리의 각 명칭 루트 : 자식 노드를 가지며, 간선으로 연결되어 있는 것 차수 : 자식 노드의 개수 높이 : 현재 위치에서부터 리프까지의 거리 깊이 : 루트에서부터 현재 노드까지의 거리 그래프 vs 트리 트리는 순환 구조를 갖지 않지만 그래프는 순환 구조를 가지고 있다. (a) 같은 경우는 순환 구조를 가지고 있지 않기에 트리지만 (b) 같은 경우는 A-B-C-F 순환 구조를 가지고 있기에 그래프이다. 이진 트리 모든 차수가 2 이하 일때를 말한다. 왼쪽, 오른쪽 최대 2개의 자식을 갖는..

그래프 수학에서, 좀 더 구체적으로 그래프 이론에서 그래프란 객채의 일부 쌍들이 연관되어 있는 객체 집합 구조를 말한다 정점, 간선으로 이루어져 있고 모든 정점의 쌍 반드시 간선으로 연결 되는 것은 아니다 하나의 간선은 두 개의 정점을 연결한다 오일러 경로 그래프에 존재하는 모든 정점이 한 번씩만 방문하는 경로(한붓그리기,시작과 끝이 같아야한다) 모든 정점이 짝수 개의 차수를 갖지 않으면 오일러 경로가 아니다 오일러 경로를 가진 그래프를 오일러 그래프라고 한다 해밀턴 경로 각 정점을 한번 씩 방문하는 무향 또는 유향 그래프 경로를 말한다(시작과 끝이 같아야한다) 해밀턴 경로를 가진 그래프를 해밀턴 그래프라고 한다 오일러 경로와의 차이는 오일러는 간선기준, 해밀턴 경로는 정점을 기준으로 한다는 것이다 그래..

해시테이블 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 추상 자료형(ADT)를 구현하는 자료구조이다. 대부분 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 데이터 양에 관계 없이 빠른 성능을 가진다. 해시 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 해싱 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라 하며, 해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법이다. 체크섬, 손실 압축, 무작위화 함수, 암호 등에 쓰이고 서로 혼용되기도 한다. 성능 좋은 해시 함수들은 다음의 특징을 가진다. 해시 함수 값 충돌의 최소화 쉽고 빠른 연산 해시 테이블 전체에 해시 값이 고르..

연결 리스트 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적 순서대로 저장되지 않는 것을 말한다. 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형(ADT) 구현의 기반이 된다. 새로운 노드를 삽입, 삭제가 편리하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리하기 편하다. 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러 가지 방법으로 다양하게 활용이 가능하다. 탐색에는 O(n)이 소요되고 추가, 삭제, 추출 작업에는 O(1) 소요 런너 기법 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나, 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 다음과 같이 빠른 런..

배열 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다. 어느 위치에서나 O(1)에 조회가 가능하다는 장점이 있다. 자료구조는 크게 메모리 공간 기반의 연속 방식, 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. 연결 방식의 기본이 되는 자료형은 연결 리스트이다. 추상 자료형(ADT)의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다. Ex.) 스택을 연결 리스트로 구현, 큐는 배열로 구현 파이썬에서는 정적 배열 x, 동적 배열인 리스트만 제공된다. 동적 배열의 원리 : 초깃값을 작게 잡아 배열생성 -> 데이터 추가되면서 채워지면 늘려지고 복사하는 방식(더블링이라고함) 이러한 재할당 비율을 그로스 팩터(G..