개구리의 개발 블로그 개구리의 개발 블로그

Red-Black 노드는 모든 경로의 Black 노드의 개수를 동일하게 유지한다. Red-Black Tree는 일반적인 이진 탐색 트리와 다르게 Black 노드의 개수를 통해 균형을 유지한다. Tree에 새로운 노드를 삽입하는 경우를 생각해보자. Black 노드를 삽입이 불가능한 것은 아니다. 중요한 것은 Red-Black 트리의 조건에 맞게 모든 경로에 대하여 동일한 Black Depth를 갖도록 균형을 맞춰주는 것이다. Black 노드를 삽입하면, 언제나 균형이 깨진다. 새로운 노드가 추가되는 경로에만 Black 노드의 개수가 1개 증가하기 때문이다. 반면에 Red 노드를 삽입하는 경우에는 균형이 유지되는 경우가 존재한다. 리프 노드의 부모가 Black 노드인 경우에는 Red-Black 노드의 조건과..

1. O(n²) 정렬 1.1 선택 정렬 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택 1번째 인덱스부터 배열을 탐색하여 1번째로 작은 값을 1번째에 위치 → 2번째 인덱스부터 탐색 & 2번째에 위치 → 3번째부터 탐색 & 3번째에 위치 → … → 총 (n-1)번 반복 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도 시간 복잡도 1번째 루프에서 비교 : n-1 2번째 루프에서 비교 : n-2 (n-1)+(n-2)+…+1 = n(n-1)/2 최선, 최악, 평군 모두 O(n²) def selection_sort(L): for i in range(N): #해당 위치 i에 들어갈 원소를 선택 minVal_idx = i for j in range(i+1,N): if L[j] < ..

가장 기본적인 자료구조인 스택과 큐를 python 코드를 이용해 구현해보겠습니다. Stack 후입선출 특성의 자료구조(Last In First Out) 1. 배열을 이용한 구현 스택을 위한 배열 선언(최대 크기 설정) / index = 0 index가 선언한 배열의 크기 이상이면 stack 꽉 찬 상태 / index = 0 이면 비어있는 상태 push() : index 자리에 값 추가, index+=1 pop() : index에 위치한 값 리턴, index-=1 모든 연산의 시간 복잡도 : O(1) class arrayStack: def __init__(self): self.array = [] #maxSize 설정. self.top = -1 def isEmpty(self): if self.top==-1:..