컴공생의 개인공부일지

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

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

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

데크 더블 엔디드 큐의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다. 스택과 큐의 특징 모두 가지고 있으며 이중 연결 리스트로 구현하는 편이 가장 잘 어울린다. 이중 연결 리스트로 구성시 양쪽으로 head, tail 포인터를 갖고 있다가 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결시켜 준다. 파이썬의 경우, 데크 자료형을 collections 모듈에서 deque라는 이름으로 지원한다. import collections a = collections.deque() type(a) # # collection.deque도 이중 연결 리스트로 구현되어 있다 우선순위 큐 큐 또는 스택과 유사하지만 추가로 각 요소의 우선순위와 연관되어 있다. 어떠한 특정 ..

스택 다음과 같이 2가지 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다(LIFO 형태) push() : 요소에 컬렉션을 추가한다. pop() : 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다. 거의 모든 애플리케이션을 만들 때 사용되는 자료구조, 컴퓨터 서브루틴에 대한 정보를 저장하는 자료구조 연결 리스트를 이용한 스택 ADT 구현 다음 그림은 스택 추상 자료형을 연결 리스트로 구현한 것이다. ADT는 스택의 연산을 지원하기 위해 1~5까지 각 요소를 쌓겠지만 실제로 연결 리스트로 구현하게 되면 물리 메모리 상에는 순서 관계없이 무작위로 배치되고 포인터로 가리키게 된다. 다음과 같이 연결 리스트를 담을 Node 클래스부터 정의한다. class Node: def __init__(sel..

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

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

문자열 슬라이싱 문자열 슬라이싱은 편리한 기능 제공과 동시에 내부에서 매우 빠르게 수행된다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아낸다. 문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조에는 좋은 방법이지만, 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요하므로 전체적인 속도에서 손해를 보게 된다. 알고리즘 실행 시간 슬라이싱을 1로 했을 때의 비율 슬라이싱 0.499μs 1 리스트 reverse() 2.46μs 5 reversed() + join() 2.49μs 6 for 반복 5.5μs 12 while 반복 9.4μs 21 재귀 24.3μs 24 슬라이싱을 기준으로 한 파이썬 문자열 처리 실행시간(μs는 마이크로 초를 의..

리스트 언어 동적배열 파이썬 list() C++ std::vector 자바 ArrayList 순서대로 저장하는 시퀀스이자 변경 가능한 목록, 입력 순서가 유지되며 내부적으로 동적 배열로 구현되어 있다. 파이썬 리스트는 다양한 기능 제공하고 O(1)에 실행 가능한 연산들도 몇 가지 있다. 리스트 마지막에 요소를 .append()로 추가, pop()으로 추출, 인덱스의 요소 조회는 모두 O(1)이다. 다음 표는 리스트의 주요 연산 및 시간 복잡도이다. 연산 시간 복잡도 설명 len(a) O(1) 전체 요소 개수 리턴한다 a[i] O(1) 인덱스의 i 요소를 가져온다 a[i:j] O(K) i부터 j까지 슬라이스 길이만큼의 k개 요소를 가져온다 elem in a O(n) elem 요소가 존재하는지 확인, 처음부..

매핑 키와 자료형으로 구성된 복합 자료형(파이썬에 내장된 유일한 매핑 자료형은 딕셔너리) 집합 set이라고 쓰고 중복된 값을 갖지 않는 자료형 딕셔너리와의 차이점은 딕셔너리는 키/값 형태이지만 집합은 값만 선언한다 입력 순서가 유지되지 않으며, 중복된 값이 있을 경우 하나의 값만 유지한다 시퀀스 특정 대상의 순서 있는 나열 파이썬에서는 list라는 시퀀스 타입이 배열의 역할을 수행한다 불변, 가변으로 구분 가능하고 불변은 값 변경이 X(str, tuple, bytes) 원시타입 C나 자바 같은 프로그래밍 언어는 기본적으로 원시 타입을 제공하지만 파이썬의 경우 제공하지 않는다. 원시 타입은 메모리에 정확하게 타입 크기만큼의 공간을 할당하고 그 공간으로 값으로 채워넣는다. 원시 타입을 제공함으로써 C나 자바..