나의 공부 기록

Heap 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조 1. 최대 힙(Max heap) 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리 부모 노드의 키값 > 자식 노드의 키값 루트 노드 : 키값이 가장 큰 노드 2. 최소 힙(Min heap) 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리 부모 노드의 키값 < 자식 노드의 키값 루트 노드 : 키값이 가장 작은 노드 삽입 연산 최대힙이기 때문에 정렬이 필요할 경우 해야함. 삭제 연산 1. 힙에서는 루트 노드의 원소만을 삭제할 수 있음 2. 루트 노드의 원소만을 삭제하여 반환 3. 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있음. 이를 이용하여 우선순위 큐를 힙으로 구현할 수 있음. ..

Binary search Tree 1. 탐색작업을 효율적으로 하기 위한 자료구조 2. 모든 원소는 서로 다른 유일한 키를 가짐 3. key(왼쪽 서브트리) 루트 노드의 키값 : 루트 노드의 오른쪽 서브트리에 대해서 탐색 연산 수행 3. 서브트리에 대해서 순환적으로 탐색 연산 반복 삽입 연산 1. 먼..

이진 트리 모든 노드들이 2개의 서브트리를 갖는 트리 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리 레벨 i에서의 노드의 최대 개수는 2^i개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1)-1)개 1. 포화 이진 트리(Full Binary Tree) 모든 레벨에 노드가 포화상태로 차 있는 이진 트리 2. 완전 이진 트리(Complete binary Tree) 높이가 h이고 노드 수가 n개일 때(단, 2^h

트리 비선형 구조로 원소들 간에 계층관계를 가짐 루트(Root) 노드 중 최상위 노드 노드(node) 트리의 원소 A, B, C, D, E, F, G, H, I, J, K 간선(edge) 노드를 연결하는 선 차수 노드에 연결된 자식 노드의 수 B의 차수는 2 트리의 차수 트리에 있는 노드의 차수 중에서 가장 큰 값 A=3 단말 노드(리프 노드) 차수가 0인 노드 E, G, H, I, J, K 노드의 높이 = 노드의 레벨 노드에서 루트까지의 거리 트리의 높이 트리에 있는 노드의 높이 중에서 가장 큰 값 최대 레벨 트리 T의 높이 = 3 by SW expert academy

병합 정렬 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬되 집합으로 만드는 방식 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻음. Top-Down 방식 O(n log n) def merge(left, right): result=[] # 두 개의 분할된 리스트를 병합하여 result 만듦 while len(left) > 0 and len(right) > 0 : # 양쪽 리스트에 원소가 남아있는 경우 # 두 서브 리스트의 첫 원소들을 비교하여 작은 것부터 result에 추가 if left[0] 0 : # 왼쪽 리스트에 원소가 남아있는 경우 result.extend(left) if len(right) > 0 : # 오른쪽 리스트에 원소가 남아있는 경우 result.exten..

삽입 정렬 자료 배열의 모든 원소들을 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성 o(n^2) 삽입 정렬의 정렬 과정 정렬할 자료를 두 개의 부분집합 S와 U로 가정 - 부분집합 S : 정렬된 앞부분의 원소들 - 부분집합 U : 아직 정렬되지 않은 나머지 원소들 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입 (반복) 삽입정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소 부분집합 U가 공집합이 되면 삽입정렬이 완성 # 삽입 정렬 lst=list(map(int, input().split())) # 정렬되지 않은 리스트 for i in range(1..

List 1. 순서를 가진 데이터의 묶음 - 같은 데이터의 중복 저장 가능 2. 시퀀스 자료형 - 인덱싱, 슬라이싱, 연산자, 메서드 사용 가능 3. 크기제한 없음, 타입제한 없음 크기 데이터의 타입 배열 변경 불가 선언된 한가지 타입만 저장가능 리스트 변경 가능 다양한 데이터 타입 저장가능 순차 리스트 : 배열을 기반으로 구현된 리스트 연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트 파이썬의 리스트는 동적 배열로 작성된 순차 리스트. 원소의 개수가 많고 삽입/삭제 연산이 빈번한 작업은 소요되는 시간이 크게 증가 리스트 복사 (아래로 갈수록 수행시간이 길다) 코드 설명 1 new_list=old_list 주소의 복사, 얕은 복사 2 new_list=old_list[:] 슬라이싱, 깊은 복사 3..

BFS(Breadth First Search, 너비 우선 탐색) 큐 활용 시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문 인접한 정점들을 탐색한 후, 차례로 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐 활용 인접 리스트로 구현했을 때 O(|V| + |E|), 인접 행렬로 구현했을 때 O(|V^2|)의 시간복잡도를 가진다. 인접 리스트는 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장 인접 행렬은 2차원 배열을 이용해 그래프의 간선 정보를 저장 🌿 인접 리스트와 인접 행렬의 예시 🐋 BFS 코드 예시 from collections import deque def BFS(G, v) : # 그래프 G, 탐색 시작점 v ..

우선순위 큐 우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나감 ex) 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제의 태스크 스케줄링 구현 리스트를 이용한 우선순위 큐 1. 리스트를 이용하여 자료 저장 2. 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조 3. 가장 앞에 최고 우선순위의 원소가 위치 문제점 리스트를 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생 소요되는 시간이 많이 걸림 해결 PriorityQueue(maxsize)클래스 사용 힙 자료구조 사용 우선순위 큐 라이브러리 사용 기본 연산 삽입 : enQueue 우선순위에 맞게 삽입 삭제 : deQueue 가장 높은 우선순위부터 삭제 버퍼 : 데이터..

1차원 리스트를 이용한 큐 큐의 크기 = 리스트 크기 front 저장된 첫 번째 원소의 인덱스 rear 저장된 마지막 원소의 인덱스 초기 상태 : front = rear = -1 공백 상태 : front = rear 포화 상태 : rear = n-1 (n : 리스트 크기, n-1 : 리스트의 마지막 인덱스) ✨ 선형 큐의 구현 1. 초기 createQueue() 초기 공백큐 생성 크기가 n인 1차원 리스트 생성 front = rear = -1 2. 삽입 : enQueue(item) 마지막 원소 뒤에 새로운 원소를 삽입하기 위해 rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련 그 인덱스에 해당하는 리스트원소 Q[rear]에 item을 저장 3. 삭제 deQueue() 가장 앞에 있는 원소를 ..