프로그래밍/자료구조와 알고리즘8 [알고리즘] 삽입 정렬(insertion sort) # insertion sort def insertion_sort(data): for idx1 in range(len(data) - 1): # 처음에 range(idx1 + 1, len(data) - 1)로 적었다. for idx2 in range(idx1 + 1, 0, -1): if data[idx2] < data[idx2 - 1]: # 이 부분은 swap이 아니라 data[idx2] = data[idx2 - 1]로 적었다. data[idx2], data[idx2 - 1] = data[idx2 - 1], data[idx2] else: break return data import random data = random.sample(range(100), 10) print(insertion_sort(data)).. 2021. 6. 21. [알고리즘] 버블 정렬(bubble sort) # bubble sort def bubble_sort(data): for idx1 in range(len(data) - 1): swap = False for idx2 in range(len(data) - 1 - idx1): if data[idx2] > data[idx2 + 1]: data[idx2], data[idx2 + 1] = data[idx2 + 1], data[idx2] swap = True if swap == False: break return data import random data = random.sample(range(100), 15) print(bubble_sort(data)) 2021. 6. 21. [자료구조] 트리(Tree) 노드(Node)와 브랜치(Branch)를 이용해 사이클을 이루지 않도록 구성한 자료구조 선형 구조(순차적 구성)인 큐, 스택 등과 달리 트리는 비선형 구조이다.(계층적으로 구성) 주로 이진 트리(Binary Tree) 형태로 탐색(검색) 알고리즘 구현에 많이 사용된다. 이진 트리: 노드의 최대 브랜치가 2인 트리. 즉, 자식 노드가 최대 2개인 트리 노드(Node): 트리에서 데이터를 저장하는 기본 요소(데이터 + 연결된 노드에 대한 브랜치 정보) 루트 노드(Root Node): 트리에서 가장 위에 있는 노드 레벨(Level): 루트 노드를 기준으로, 하위에 연결된 노드의 깊이 부모 노드(Parent Node): 어떤 노드의 상위 레벨에 연결된 노드 자식 노드(Child Node): 어떤 노드의 다음 레.. 2021. 3. 5. [자료구조] 해시 테이블(Hash Table) 키(Key)에 데이터(Value)를 저장해, 키 값으로 데이터에 직접 접근이 가능한 자료구조 보통 해시 테이블 크기만큼 배열을 생성해 사용한다. Python의 Dictionary가 해시 테이블에 해당한다. 해시(Hash): 임의의 값을 고정 길이로 변환하는 것 해싱 함수(Hashing Function): 산술 연산으로 키를 연산해 데이터의 위치를 찾을 수 있는 함수 해시 값(Hash Value) / 해시 주소(Hash Address): 데이터가 저장된 위치(주소) 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간 해시 테이블의 장단점과 주요 용도 장점: 키를 이용해 데이터를 바로 꺼낼 수 있기 때문에 데이터 저장/읽기 속도가 빠르다. 키에 대응하는 데이터가 저장돼 있는지 바로 확인할 수 있기 때문.. 2021. 3. 4. [자료구조] 연결 리스트(Linked List) 순차적으로 연결된 공간에 데이터를 나열하는 배열과 달리 연결 리스트는 떨어진 곳에 있는 데이터를 연결해 관리하는 자료구조 노드(Node): (데이터값, 포인터)로 구성 포인터(Pointer): 각 노드에서 연결된 노드(next, prev)와의 연결 정보를 가지고 있는 공간 장점: 미리 데이터 공간을 할당하지 않아도 된다. 단점: 연결을 위한 데이터 공간이 추가로 필요하기 때문에 저장공간 효율이 높지 않다. 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다. 중간에 있는 데이터 삭제 시, 앞뒤 데이터 연결을 재구성해야 한다. Python의 List에서 연결 리스트의 기능을 모두 지원한다. Python에서 연결 리스트를 구현할 때는 보통 Class를 활용한다. # 연결 리스트 구현 class Node:.. 2021. 3. 4. 이전 1 2 다음
