넘치게 채우기

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 자기 자신을 계속해서 호출하다가, 일정한 조건이 만족되면 함수를 반환하여 결과를 도출한다. 컴퓨터 내에서 재귀 함수는 스택 자료구조와 동일하다. 함수를 계속 호출했을 때, 마지막으로 호출된 함수가 먼저 종료되어야 첫 함수가 종료된다. 아래는 재귀 함수의 대표적인 예시인 팩토리얼이다. def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n-1) 재귀 함수의 장점은 수학의 점화식을 표현한 코드여서 매우 간결한 표현이 가능하단 것이다. 단, 끝없이 재귀 함수가 반복되지 않도록 함수를 끝낼 수 있도록 조건을 만들어놓아야 한다.

레드블랙트리의 삽입 레드-블랙트리의 삽입에서, 다음과 같은 과정을 거친다: 1.이진 탐색 트리와 같이 노드를 삽입하고, 삽입한 노드의 색은 빨간색으로 한다. 2.트리에 문제가 생기진 않는지 확인해주고, 문제가 있으면 고쳐준다. 레드블랙트리의 삽입에서의 문제 해결은 다음과 같은 경우들이 있다: 삽입되는 노드를 편의상 z라고 가정해보자. 1. z가 루트인 경우 z가 루트인 경우는 쉽다. 루트 노드의 색은 검정색이여야 하므로 빨간색을 검은색으로 칠해주면 된다. 이 경우를 제외한 나머지 경우는 모두 부모 노드가 빨간색이라 Double Red가 생긴 경우이다. 2. z의 삼촌이 빨간색인 경우 z의 삼촌이 빨간색일 땐, 조부모 노드(부모노드의 부모노드)의 색을 빨간색으로 칠해주고, 부모노드와 삼촌노드를 검은색으..

vice versa. 지난 글처럼, 라틴어에서 온 표현이다. 뜻은 그 반대(도 마찬가지이다)라는 뜻이다. 순영어로는"the other way round"라고 할 수 있다. vice는 자리, 위치, versa는 돌다라는 뜻을 가지고 있다. 예시: We can't go forward without her and vice versa. 우린 그녀없이는 나아갈 수 없고, 그녀도 마찬가지야.

영문으로 글을 읽다보면, e.g.와 i.e. 둘 다 많이 봤을 것이다. 뜻부터 말하자면, e.g.는 라틴어 "exempli gratia"에서 따온 말로, 영어로는 "for example", "예를 들어서"의 의미를 가진다. i.e.는 라틴어 "id est"의 약자로, 영어로는 "in other words", "that is to say", "다시 말해서"의 의미를 가진다. 둘 다 소문자로 써야 하며, 자모 사이에 점을, 맨 끝에도 점을 찍어줘야 한다. 예시: Recolouring is the change in colour of the node i.e. if it is red then change it to black and vice versa. 리컬러링은 노드의 색을 바꾸는 것이다. 다시 말해서, 만약 ..

이전에 이진 탐색 트리 편에서, 균형잡힌 트리와, 그렇지 못한 트리를 보았을 것이다. 그래서 이번에는 불균형한 트리를 균형잡힌 트리로 잡아주는 AVL 트리에 대해 알아볼 것이다. AVL트리는 다음의 특징이 있다: 이진 탐색 트리의 속성을 가진다. 왼쪽, 오른쪽 서브트리의 높이 차가 최대 1이다. 높이 차이가 1보다 커지면, 회전을 통해서 균형을 잡는다. 최대높이를 logN으로 유지시켜서 O(logN)으로 유지시킨다. 여기서 회전을 알기 전에, 균형을 아는 수치인 BF값을 알아보자. BF(Balance Factor) BF(k) = height(left(k)) - height(right(k)) 값이 1이면 왼쪽이 한 단계 높은 것이고, 0이면 높이가 같다는 뜻, -1이면 오른쪽이 한 단계 높은 것이다. 만약..

덱 덱(deque)는 double - ended - queue의 줄임말로, 앞뒤로 빼고, 넣는 것이 가능한 자료구조이다. 큐와 스택을 합친 자료구조라고 볼 수도 있다. 파이썬에서는 collections 라는 모듈에서 쉽게 사용할 수 있다. 리스트와 비슷해보이는 연산들이 있지만, 들여다보면 차이가 존재한다. 리스트는 맨 앞 데이터를 빼면, 뒤에 있는 데이터들이 다 앞으로 당겨져서 시간복잡도가 O(n)이 된다. 덱은 이중 연결리스트 기반으로 구현되어, 맨 앞 데이터를 빼더라도 시간복잡도가 O(1)이다. 덱의 연산 appendleft(): 앞쪽으로 데이터 enqueue popleft(): 앞쪽에서 데이터 dequeue append(data): 뒤쪽으로 데이터 enqueue pop(): 뒤쪽에서 데이터 dequ..

지난 2-2 글에서, 내가 구현한 배열을 이용한 큐는, 엄밀히 따지면 파이썬의 리스트를 이용한 것이다. '배열'이랑 구현한 것과 다른 점은, 큐의 크기를 정하지 않는다.(append하면 뒤에 새 칸을 만들고, pop하면, 칸이 줄어든다) pop 했을 때, 뒤 데이터들이 빈 자리를 채우러 앞으로 당겨진다. 그래서, '배열스러운' 큐를 다시 구현해보았다. 큐 - '배열'을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self, size): self.size = size self.arr = [None] * self.size self.first = 0 self.last = 0 def isEmpty(self): #큐가 비어있는지 확인 if self.first >= sel..

큐(Queue) 큐 자료구조는 우리가 평소에 줄을 서듯, 먼저 들어온 사람이 먼저 나가는, 선입선출(先入先出, First in First out)의 형식을 따른다. 큐의 연산 큐의 연산은 다음 5가지가 있다: isEmpty(): 큐가 비어있는지를 판단한다. True 또는 False값으로 반환된다. enqueue(data): 큐에 값을 입력시킨다. dequeue(): 큐의 제일 먼저온 값을 내보낸다. rear(): 큐의 맨 뒤에 있는 값을 반환한다. front(): 큐의 제일 반저온 값을 반환한다(큐에서 pop하지는 않는다) 큐의 구현 - 배열을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self): self.arr = [] def isEmpty(self): #..

스택(Stack) 스택 자료구조는 탄창에 총알을 넣고 빼듯, 먼저 넣은 데이터를 늦게 꺼내는 선입후출(先入後出, FILO(First in Last out)), 후입선출(後入先出, LIFO(Last in First Out))을 따른다. 스택의 연산 스택의 연산은 다음 4가지가 있다: isEmpty() : 스택이 비어있는지를 판단한다. push(data) : 스택의 맨 위에 데이터를 쌓는다 pop() : 스택의 맨 위 데이터를 스택에서 뺀다. top() : 스택의 맨 위의 값을 확인한다. 스택의 구현 - 배열을 이용한 구현(Python) class stack(): #스택 선언 def __init__(self): self.arr = [] def _len_(self): return len(self.arr) de..