코르시카's Blog

■ 이진 탐색트리 1) 정의 : > Linked list - O(1) 삽입 / 삭제 - O(N) 탐색 복잡도 > Binary Search - 자료구조가 sorting되어있는 상태에서 시행 - O(logN) 탐색 복잡도 ※ 위 두개의 장점을 합친 방식으로 자료구조를 짠 것이 '이진 탐색 트리' 2) 이진탐색 트리 특징 (a) 각 노드의 자식이 2개 이하 (b) 완전이진트리 구조는 아님!! - 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 같거나 큼 (c) 중복노드 많은 경우 - 다른 자료구조 사용하는 것이 효율적 (d) 평균시간복잡도 O(log(N)) 편향 트리인 경우 O(N)에 가까워 짐 → 트리가 왼쪽 / 오른쪽으로 쏠려있는 경우 3) 트리 변경의 3가지 case 자식이 없는 leaf ..

■ Heap 1) 정의 : 연관된 데이터에서 최대값 / 최소값을 빠르게 찾기 위해 고안된 "완전 이진 트리" ※ 완전이진트리 : 노드 삽입시 최하단 왼쪽 노드부터 차례로 삽입하는 트리 2) 사용 이유 : - array( and python list)에서 배열 길이만큼 index searching시간 소요 O(N) - heap에 데이터를 넣으면 O(log N) 평균시간이 걸림 - 최대 최소를 빠르게 찾아야 하는 경우 유용 ( PS 문제에 최소/최대 이용하여 문제 빠르게 해결하는 경우 있었음 ) 3) 종류 (1) min heap - 정의 : (a) 각 노드의 값은 해당 노드의 자식 값보다 작음 (b) 완전 이진트리 형태를 가짐 - python 기본 heapq library 경우 min heap으로 구성 ■ ..

■ Queue 1) 정의 : First In First Out - FIFO 구조 > 들어가는 곳과 자료가 나오는 부분이 다른 구조 > array( 파이썬에서는 deque library써서 입출력 속도 높여서 사용 ) > queue는 mmutable이라 access 가능하면 변경시 다른 곳에서 참조해도 변경사항이 반영 추가 참조 : ledgku.tistory.com/54 [Python 변수] mutable과 immutable의 차이 [Python 변수] mutable과 immutable의 차이 변수 변수는 객체를 가리킨다. $$ num = 10 $$ 컴퓨터 메모리에 10이라는 값이 저장되고 num은 10이 저장된 메모리의 위치를 가리킨다. 10이라는 정수형 객체를 num이 ledgku.tistory.com..

■ Stack 1) 정의 : First In Last Out - FIFO 구조 > 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 > array로 이루어진 자료구조 사용 2) 대표 활용 : > 컴퓨터 내부 프로세스 , 함수 콜 스택 등에 사용 > PS 중에 동적계획법에 사용되는 경우도 있음 3) 코드 > 재귀함수 stack # 재귀 함수 # 재귀 깊이 설정 import sys sys.setrecursionlimit(10000) # -> 공간 미리 확보해둔 것임!, in the system # 재귀함수는 stack으로 process가 진행된다 def recursive(data): if data < 0: print ("ended") else: print(data) recursive(data - 1) print..

■ Array 참조 : korshika.tistory.com/86 (1) Array - 배열 ■ 배열 - 연관된 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 - Python에서는 list가 배열 기능을 제공 ※ List는 배열 구조이면서 데이터가 index에 따라서 빈틈 없이 korshika.tistory.com > 고정 size의 arrray를 선언하고 이를 사용 - 연속된 메모리 공간 - 데이터 최대 사이즈를 모르거나 데이터가 계속 늘어나는 경우 부적합 > 데이터 삽입 삭제가 느림 - 중간 index에 값을 추가하는 경우, 다음 index부터 뒤로 밀어내며 덮어쓰이는 등의 이유 > item 사이의 빈 공간(null) 등이 있을 수 있음 > index로 빠르게 값을 찾는 것이..

■ Linked list 구조 1) 정의 : 연속된 메모리 위치에 저장되지 않는 선형 데이터 구조 > 포인터를 사용하여 연결 된다 > 용량 / 전기적 이유로 HDD / SSD에서 읽어와서 memory에 올려서 메모리 포인터의 값을 프로그래밍 언어가 사용 > 다음과 같은 구조를 가짐 2) 사용 이유 : (1) array의 단점 - 배열 크기가 미리고정되어있어 유동적으로 데이터 사이즈에 따른 자료구조 변경이 어려움 - 새로운 요소를 삽입하는 것에 비용이 많이 소모( 공간을 만들고, 기존 요소 전부 이동시켜야 함 ) > 요즘 언어들은 array에 대한 push pop (2) Linked list의 장점 동적 크기 삽입/삭제 용이 (3) Linked list의 단점 임의 access허용 불가능, 노드 앞단부터 ..

■ 배열 - 연관된 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 - Python에서는 list가 배열 기능을 제공 ※ List는 배열 구조이면서 데이터가 index에 따라서 빈틈 없이 연속적으로 위치하는 데이터 구조를 의미 ( 배열과 비슷하지만 다른 점이 있음 ) ■ 배열이 필요한 이유 1) 같은 종류의 데이터를 효율적으로 관리하기 위함 ( 필요에 의해 묶어둔 연관된 혹은 같은 type의 데이터 ) 2) 같인 종류의 데이터를 순차적으로 관리 ■ 배열의 장단점 1) 장점 - 빠른 접근이 가능 2) 단점 - 배열의 size를 미리 설정해야 한다. Python은 자유로움 - 추가되는 데이터가 있으면 데이터 주소를 연결하여 데이터가 추가되어야 하는데, 데이터 길이보다 array siz..