Koo's.Co

1. 이진탐색? - 이진탐색은 정렬되어 있는 선형자료구조에서 사용할 수 있는 탐색 방법이다. - 정렬되지 않은 자료형의 경우 처음부터 차례대로 값을 비교해야하기 때문에 O(N)의 시간복잡도를 갖는다. - 반면 자료가 정렬되어 있는 경우 이진탐색을 통해 O(logN)의 시간복잡도로 값을 찾을 수 있다. - 이진탐색은 범위를 주면 해당 범위 중간값을 기준으로 찾고자 하는 값이 중간값보다 큰지 작은지를 판단하는 방법이다. - ex) 책에서 원하는 페이지 번호를 찾으려 할 때 일단 책을 펴고 찾고자 하는 페이지 번호가 더 작으면 앞부분을, 찾고자 하는 페이지 번호가 더 크면 뒷부분을 보는 것과 같다. 2. 이진탐색 알고리즘 - 찾고자 하는 값을 target이라 한다 - 리스트 nums가 주어지면 가장 작은 인덱..

이진 탐색 트리를 구현하기에 앞서 기본적인 트리의 구현을 해보려 한다. 오늘 구현할 트리는 별도의 기능을 갖지 않고 트리의 순회를 중점적으로 보려 한다. 순회란 트리를 돌면서 어떤 원소가 있는지 확인하는 작업을 말한다. 이 때 어느 원소를 먼저 보는지에 따라 순회의 종류가 달라진다. 트리의 순회는 재귀 방법으로 쉽게 구현할 수 있다. 위의 트리를 코드로 구현해 보자 1. 트리의 구조 class Node(object): def __init__(self, item): self.item = item self.left = self.right = None class BinaryTree(object): def __init__(self): self.root = None - Node class에서 item원소는 루트(..

1. 트리란? - 노드로 구성된 비선형 자료구조로 계층구조를 나타낼 때 사용 - 하나의 루트 노드를 가짐 - 루트 노드는 0개 이상의 자식 노드를 가짐 - 그래프의 한 종류로 사이클을 갖지 않는 그래프 - 나무의 가지처럼 계속 뻗어 나가는 계층구조로 나무를 뒤집은 모습을 생각해보자 - 컴퓨터에서 폴더 안에 폴더와 파일이 있는 구조도 트리 구조 2. 트리 관련 용어 - 간선(Edge): 노드들을 연결하는 선 - 루트 노드(Root Node): 부모 노드가 없는 최상위 노드, 트리는 하나의 루트 노드를 갖는다 - 단말 노드(Leaf Node): 자식이 없는 노드 - 부모 노드(Parent Node): 자식 노드를 갖는 상위 노드 - 자식 노드(Child Node): 부모 노드가 갖는 노드들 - 깊이(dept..

스택과 마찬가지로 파이썬에서는 데큐를 이용하면 큐의 기능을 모두 사용할 수 있다. enqueue 연산은 append로, deque 연산은 popleft를 사용하면 된다. 여기서는 이중 연결리스트를 이용해 큐를 구현해보려 한다. 구현하려는 큐의 추상 데이터 타입은 다음과 같다. empty(): 비었다면 True를, 아닐 경우 False를 반환 enqueue(item): 큐에 rear에 item을 삽입 deque(): 큐에 front에 있는 item을 출력 __len__(): 큐의 크기를 반환 1. 큐 이전에 구현한 이중 연결리스트를 이용해 큐를 구현하려 한다 from LinkedList import DoubleLinkedList class Queue(object): def __init__(self): se..

이중 연결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다 단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다 단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다 이중 연결리스트는 단순 연결리스트와 다르게 이전 노드에 접근이 가능하다는 장점이 있다 이전 노드에 접근할 수 있다는 말은 특정 노드 이전의 값을 삭제하거나 역으로 출력하는 등 추가적인 연산이 가능하다 구현하려는 이중 연결리스트의 추상 데이터 타입은 다음과 같다 empty(): 리스트가 비었다면 True, 아닐 경우 False를 반환 append(data): 리스트의 맨 뒤에 ..

큐란? 큐는 스택과 함께 대표되는 선형 자료구조이다. 큐는 스택과 다르게 들어오는 방향과 나가는 방향이 정해져 있다. 선입선출(FIFO) 자료구조로 큐 안에 먼저 입력된 원소가 큐에서 꺼낼 때도 제일 먼저 출력된다. 계산대에 줄을 선 사람들 (들어온 순서대로 먼저 계산을 하고 나가는 모습) 이나 프린터기에서 먼저 들어온 순서대로 인쇄가 되는 모습을 생각하면 된다. 큐 안에 원소를 집어넣는 enque 연산, 맨 먼저 입력된 원소를 출력하는 deque 연산을 갖고 추가적으로 필요에 따라 가장 앞선 원소를 확인하는 front 연산이나 가장 마지막 원소를 확인하는 rear 연산을 구현할 수 있다. 큐를 배열로 구현할 때는 몇가지 문제점이 존재한다. enqueue를 할 때는 문제가 발생하지 않지만 deque를 할..

정렬 리스트가 주어졌을 때, 해당 원소들을 키값에 따라 오름차순 또는 내림차순으로 배열하는 것을 말한다. 데이터를 정렬하는 이유는 탐색을 위해서이다. 정렬되지 않은 데이터에 대해 선형탐색(순차탐색)을 이용해 처음부터 비교해가며 값을 찾아야만 한다. 하지만 데이터가 정렬되어 있는 경우, 이진탐색을 이용한 빠른 탐색이 가능하다. 안정적 정렬(Stable Sort) 동일한 키값을 갖는 원소가 2개 이상 있을 때, 정렬 후에도 해당 원소들의 순서가 유지되는 것을 말한다 [1, 3, 4, 5, 3, 8, 11] 이라는 리스트가 주어졌을 때, 정렬 후에도 첫번째 3이 두번째 3보다 앞에 올 때 안정적 정렬이라 한다 제자리 정렬(In-place Sort) 입력받은 데이터 메모리 이외에 별도의 저장 공간을 상수개만 사..

파이썬에서 제공하는 리스트를 사용하면 스택의 기능을 모두 사용할 수 있다. push연산은 append, pop연산은 그대로 pop을 이용하면 된다. 여기서는 노드를 이용해 스택을 구현해보려 한다. 구현하려는 스택의 추상 데이터 타입은 다음과 같다. empty() : 비었다면 True를, 아닐 경우 False를 반환 push(item) : 스택에 item을 삽입 pop() : 스택에 마지막으로 들어온 item을 반환, 스택이 비어있는 경우 False를 반환 peek() : 스택에 마지막으로 들어온 item을 반환 __len__() : 스택에 크기를 반환 1. 노드 class Node(object): def __init__(self, item, pointer): self.item = item self.poi..

스택이란? 스택은 원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 선형 자료구조이다. 나중에 들어온 원소가 제일 먼저 나가는 후입선출(LIFO: Last In First Out) 구조를 갖는다. 책을 상자 안에 쌓아서 넣을 때, 나중에 쌓은 책을 먼저 빼는 모양을 생각할 수 있다. 스택 안에 원소를 집어넣는 push연산, 삽입된 원소를 빼내는 pop연산, 제일 위에 있는 원소값을 반환하는 peek연산을 갖는다. 컴퓨터 내부에서 프로그램에 대한 정보를 저장하는 자료구조에도 쓰이는 등 컴퓨터 내부에서도 많이 사용된다. 간단하게 구현가능하면서도 여러 상황에 응용할 수 있어 많이 쓰이는데 힙 영역에 데이터를 저장하거나 재귀함수를 호출하는 과정도 스택 형태로 사용된다.