이진 탐색 트리(Binary Search Tree)란 왼쪽 서브 트리는 자신보다 작은 수들만 존재하고 오른쪽 서브 트리는 자신보다 큰 수들만 존재하는 이진트리를 뜻한다.
단순한 이진트리는 원하는 값의 존재 여부를 확인하려면 트리 전체를 탐색해야 한다.
따라서 자료구조로써의 효율이 떨어진다.
그래서 나온 것이 이진 탐색 트리이며 왼쪽은 작은 수, 오른쪽은 큰 수를 유지함으로써 탐색하는데 O(logn)의 효율적인 시간 복잡도를 가질 수 있다.
또한 모든 원소들은 서로 다른 값을 가진다는 조건이 붙어있다.
삽입과 삭제 과정을 그림을 통해 보면 이해가 쉬울 것이다.
이진 탐색 트리의 삽입 연산
먼저 트리는 항상 루트부터 시작한다.
기존의 트리에서 4를 추가하기 위해 루트 원소를 살펴보니 6으로 4가 더 작기 때문에 왼쪽 자식 노드로 내려간다.
다시 비교해보니 추가하려는 원소가 더 크기 때문에 오른쪽으로 내려가야 되는데 더 이상 자식 노드가 없으므로 오른쪽 자식 노드로 추가한다.
그다음 8을 추가하기 위해 다시 루트 노드부터 탐색을 시작한다.
6보다 크니 오른쪽 자식 노드로 내려가고 9보다 작으니 왼쪽 자식 노드, 7보다 크니 오른쪽 자식 노드로 내려가는데 이때 오른쪽 자식 노드가 없으므로 오른쪽에 노드를 추가하면 된다.
루트에서 시작해서 매번 범위를 절반씩 줄여 나가므로 삽입 시 O(logn)의 시간 복잡도가 걸린다.
삽입 연산이 크기 비교만을 통해 탐색 후 추가하는 거라 상당히 단순하기 때문에 삽입에 비해서 삭제 연산은 다소 복잡하게 느껴질 수 있다.
하지만 케이스를 나눠 순서를 따라가면 이해할 수 있을 것이다.
케이스는 크게 2가지로 삭제할 노드가 단말 노드인 경우, 자식 노드가 존재하는 경우로 나눠서 생각하면 된다.
단말 노드일 때 삭제 연산
삭제 노드를 찾기 위한 탐색은 삽입 연산과 동일하다.
먼저 가장 간단한 경우인 삭제할 노드가 단말 노드인 경우는 그냥 해당 노드와 부모 노드의 관계를 끊어주고 삭제하면 된다.
자식 노드가 존재할 경우 삭제 연산
두 번째는 자식 노드가 존재할 경우이다.
통상 이진 탐색 트리의 삭제는 단말 노드인 경우, 자식 노드가 한 개인 경우, 자식 노드가 두 개인 경우 이렇게 나누는데 자식 노드가 하나나 둘이어도 원리는 같은 방식이니 굳이 구분 짓진 않겠다.
기억해야 할 중요한 점은 삭제할 노드와 가장 차이가 적게 차이나는 노드로 교체한다는 것이다.
이것과 이진 탐색 트리의 특성을 기억한다면 방식을 까먹을 일은 없다.
즉, 삭제할 노드의 왼쪽 자식(왼쪽 서브 트리)으로 내려갔다면 가장 차이가 적게 나는 값을 찾기 위해 최대한 오른쪽 자식 노드(오른쪽 서브 트리)로 이동해야 값을 찾을 수 있을 것이고, 반대로 오른쪽 자식 노드로 내려갔다면 가장 차이가 적게 나는 값을 찾기 위해 최대한 왼쪽 자식 노드로 이동해야 값을 찾을 수 있을 것이다.
가장 차이가 적게 나는 노드를 찾았다면 원래 삭제할 노드와 값을 교환하고 단말 노드의 삭제를 하면 된다.
그림을 보면 삭제할 9를 찾기 위해 루트 노드의 오른쪽 자식으로 이동하여 삭제할 노드를 찾았고, 왼쪽 자식이 있으므로 왼쪽으로 이동 후 오른쪽 자식 노드가 존재하지 않을 때까지 오른쪽 자식 노드로 이동하였다.
결국 8을 찾았고 이를 9와 교체한 뒤 삭제하면 된다.
전체적으로 보면 알겠지만 삽입과 삭제 과정에서도 꾸준히 이진 탐색 트리의 특성을 유지하는 것을 알 수 있다.
구현
이진 트리를 구현하는 3가지 방법을 소개하겠다.
리스트(배열)로 구현
딕셔너리로 구현
구조체로 구현
보통 리스트로 구현하는 방법은 낭비되는 공간이 많으므로(공간 복잡도가 비효율적이므로) 구조체로 구현하는 방법을 많이 쓴다.
또한 파이썬은 키, 값을 갖는 딕셔너리로도 구현이 가능하기 때문에 상황에 맞게 자신이 편한 방식대로 구현하면 된다. (필자는 딕셔너리가 가장 편하고 쉬우며 효율적이기에 자주 쓴다.)
이진 탐색 트리(Binary Search Tree)를 기반으로 최대 힙은 항상 루트 노드가 가장 큰 원소임을, 최소 힙은 항상 루트 노드가 가장 작은 원소임을 보장하는 자료구조가 힙이다.
여기서 중요한 점은 항상 루트 노드를 보장한다는 점이다.
즉, 루트 노드를 제외한 나머지 노드는 정렬되어 있지 않기 때문에 리스트의 정렬이 필요한 상황이 아닌, 최솟값 혹은 최댓값이 필요한 상황에서 사용 가능하다.
물론 삽입과 삭제가 발생해도 갱신을 통해 항상 루트 노드는 특성을 유지하며 갱신 과정에서 범위를 절반씩 줄이기 때문에 O(logn)의 아주 효율적인 시간 복잡도가 걸린다.
만약 N개의 Data가 있는 리스트에서 최댓값 혹은 최솟값을 매번 찾아야 한다면 O(n)의 시간 복잡도가 걸리는 선형 탐색보다 힙을 사용하는 게 훨씬 효율적이다.
예시는 그림을 통해 최대 힙으로 설명할 것이며 최소 힙도 같은 원리로 작동한다.
최대 힙의 삽입 연산
먼저 최대 힙의 삽입 연산이다.
가장 끝 부분에 원소를 넣는다.
그리고 힙의 특성을 유지하기 위한 갱신 과정을 거치는데 이 과정을 Heapify라고 한다.
따라서 최대 힙이기에 삽입된 6과 부모 노드인 5를 비교해봤을 때 부모 노드가 더 작으므로 서로 교환해준다.
그다음 교환한 부모 노드로 가서 다시 해당 노드와 부모 노드를 비교해주는데 여기선 부모 노드가 더 크므로 힙의 특성을 지키고 있기 때문에 갱신 과정은 종료된다.
최대 힙의 삭제 연산
다음은 최대 힙의 삭제 연산이다.
삭제는 항상 루트 노드를 제거함으로써 최댓값의 반환을 보장하고 마지막 원소를 루트 노드로 가져온다.
여기부터 힙의 특성을 유지하기 위한 Heapify가 진행되는데 자식 노드와 비교해서 자신보다 큰 원소가 있다면 교환을 하고 해당 자식 노드로 넘어간다.
이때 자식 노드가 하나만 있다면 그 하나와 비교를 하고 두 개가 있다면 그중 아무거나 자신보다 큰 원소와 교환을 한다.
물론 둘 다 교환할 필요가 없다면 갱신 과정은 종료되지만 해당 그림에선 6과 7 둘 다 현재 노드보다 크므로 왼쪽 노드인 7과 교환을 한 후 왼쪽 노드로 내려가겠다.
왼쪽으로 내려간 현재 노드와 자식 노드들을 비교했을 때 오른쪽 자식인 6이 더 크므로 오른쪽 자식과 교환을 한 후 내려갔지만 더 이상 자식 노드가 없으므로 여기서 갱신 과정은 종료된다.
갱신 과정을 보다 보면 알겠지만 항상 부모 노드와 자식 노드와의 관계에서 힙 특성을 유지하게끔 변경하는 과정이 일어나는 것을 알 수 있다.
이를 통해 갱신 과정은 범위가 절반씩 줄어드므로 O(logn)의 시간 복잡도가 걸리는 것을 알 수 있고 이진 탐색 트리(Binary Search Tree)와는 다르게 형제 노드끼리의 크기 차이는 신경 쓸 필요가 없다는 것도 확인할 수 있다.
구현
물론 이 힙의 삽입, 삭제 과정을 구현하는 것은 어렵진 않지만 고려할 요소들과 실수 가능성을 생각하면 시간제한이 있는 코딩 테스트에서 직접 구현하는 것은 상당히 비효율적이다.
다행히 다양한 이름으로 라이브러리가 있는데 파이썬에서는 heapq라는 모듈을 사용하면 된다.
따라서 해당 포스팅에서는 heapq의 사용방법을 익히도록 하겠다.
import heapq
data_list=[]
input_data=[5,9,3,1]
print("최소 힙 초기 원소 :",data_list)
for i in input_data:
print(i,"추가")
heapq.heappush(data_list,i)
print(data_list)
print("\n최소 힙 루트 노드의 원소 :",data_list[0],end="\n\n")
for i inrange(len(input_data)):
print(heapq.heappop(data_list),"삭제")
print(data_list)
print("\n기존 input 리스트 :",input_data)
heapq.heapify(input_data)
print("Heapify 후 input 리스트 :",input_data)
print("\n최대 힙 초기 원소 :",data_list)
for i in input_data:
print(i,"추가")
heapq.heappush(data_list,(-i,i))
print(data_list)
print("\n최대 힙 루트 노드의 원소 :",data_list[0][1],end="\n\n")
for i inrange(len(input_data)):
print(heapq.heappop(data_list)[1],"삭제")
print(data_list)
파이썬에서는 힙 구조를 만들 때 새로운 자료구조를 취급하는 게 아니라 기존의 리스트에 heapq란 모듈을 통해 힙의 특성을 가지며 heapq는 크게 3가지 함수가 있다.
원소를 넣는 heappush(), 원소를 삭제하는 heappop(), 리스트를 힙의 형태로 변환하는 heapify()다.
또한 heapq는 기본적으로 최소 힙의 특성을 가진다.
첫 번째 반복문을 통해 input_data의 원소를 하나씩 삽입하면서 최소 힙을 유지하는 것을 알 수 있다.
두 번째 반복문은 heappop()을 통해 루트 노드를 제거하면서도 최소 힙의 특성을 유지하는 것을 알 수 있다.
또한 18번째 줄을 통해 기존의 리스트를 힙의 형태로 변환하는 것도 확인할 수 있다.
3번째 반복문에서는 기본적으로 최소 힙의 특성을 갖는 heapq를 최대 힙으로 활용하기 위해서 튜플로 원소를 삽입한 것을 알 수 있다.
기존의 원소에 -1을 곱하여 음수로 만들고 해당 음수 값과 양수 값을 같이 넣으면 음수 값을 통해 최소 힙으로 정렬된다.
음수 값을 통해 최소 힙으로 정렬이 되므로 같이 들어간 양수 값은 자동적으로 최대 힙으로 정렬이 되는 원리를 이용한 것이고 튜플로 넣었기 때문에 pop() 할 때 인덱스 1로 접근한 것을 30번째 줄에서 확인할 수 있다.
결과 화면
모듈 import도 쉽고 함수도 어렵지 않아서 한 두 번 보면 쉽게 익힐 수 있을 것이다.
먼저 저 숫자가 들어간 동그라미는 노드(Node)라고 하며 노드를 잇는 선은 간선(Edge)라고 한다.
노드는 Data를 뜻하며 간선은 Data끼리의 연결을 뜻한다.
트리에서의 첫 시작 노드는 뿌리라 해서 루트 노드(Root Node)라 한다.
모든 시작은 이 루트 노드에서 이루어지며 연결 리스트(Linked List)를 알고 있다면 더미 노드(Dummy Node)와 같은 역할이다. (물론 루트 노드는 Data를 갖고 있다는 점이 다르긴 하다.)
연결된 노드를 기준으로 상위에 있는 노드는 부모 노드(Parent Node), 하위에 있는 노드는 자식 노드(Child Node)라 한다.
즉, 루트 노드는 부모 노드가 없고 대부분의 노드는 서로 부모 노드, 자식 노드가 될 수 있으며 제일 끝단의 자식 노드가 없는 노드들은 단말 노드(Leaf Node, 리프 노드)라 한다.
그림에서도 알 수 있듯이 루트 노드를 제외한 모든 노드들은 단 하나의 부모 노드만 가질 수 있고 이 때문에 Cycle이 생기지 않으면서 모든 노드가 연결된다.
또한 하나의 노드에서 자식 노드로 뻗어나가는 간선의 수를 차수(Degree)라고 한다.
각 노드마다 차수는 다를 수 있으며 최대 차수는 하나의 노드가 가지는 최대 간선의 수를 뜻한다.
따라서 해당 그림에서는 루트 노드가 3개의 간선을 가지므로 이 트리는 Degree가 3인 트리라고 할 수 있다.
깊이는 루트 노드에서 해당 노드까지 도달하는데 경유한 간선의 개수를 뜻한다.
또한 Level은 깊이가 동일한 노드들의 집합이다.
Level이 같은 노드들을 형제 노드(Sibling Node)라고 하며 루트 노드의 Level을 정의하는데 다소 차이가 있는 것 같다.
어떤 자료에서는 Level 0부터 시작하고 어떤 자료에서는 Level 1부터 시작하는데 깊이가 기준이 되기 때문에 큰 차이는 없을 것 같다.
다만 Level 1부터 시작한다면 각 노드는 Depth+1=Level이기 때문에 보다 쉬운 이해를 위해 Level 0부터 시작하여 Depth=Level로 맞춰서 글을 작성하였다.
루트 노드를 제외하고 나머지 노드들을 루트 노드로 생각한다면 기존의 트리에서 일부분을 트리로 생각할 수 있다.
이것을 서브 트리(Sub Tree)라고 하며 보통 이진 트리(Binary Tree)에서 왼쪽 서브 트리(Left Sub Tree), 오른쪽 서브 트리(Right Sub Tree)로 구분 짓는다.
보통 알고리즘 문제나 필기 문제로 이진 트리가 나오므로 이진 트리에 대해 설명하겠다.
이진 트리 (Binary Tree)
트리에 대해서 이해가 잘 됐다면 이진 트리는 별거 없다.
이름에서도 알 수 있듯이 트리에서 최대 차수가 2인 트리를 이진 트리라고 하기 때문이다.
물론 이진 트리도 형태에 따라 3가지로 분류한다.
편향 이진 트리, 완전 이진 트리, 포화 이진 트리
편향 트리(Skewed Binary Tree)는 모든 노드가 왼쪽 혹은 오른쪽 자식만 갖고 있는 형태이다.
완전 이진 트리(CompleteBinary Tree)는 마지막 Level을 제외한 모든 Level의 노드가 완전히 채워져 있으며 마지막 Level의 노드들은 왼쪽부터 채워져 있는 형태이다.
포화 이진 트리(Full Binary Tree)는 완전 이진 트리에서 마지막 Level의 노드들도 채워져 있는, 즉 이진 트리가 보유할 수 있는 최대 노드를 가진 형태가 포화 이진 트리다.
이진 트리 순회 (Binary Tree Traversal)
이진 트리의 순회는 총 4가지가 있다.
전위 순회 (Pre-order)
중위 순회 (In-order)
후위 순회 (Post-order)
레벨 순회 (Level-order)
1번부터 3번까지는 왼쪽 서브 트리, 현재 노드, 오른쪽 서브 트리 중에 현재 노드를 언제 탐색하느냐에 따라 이름이 바뀌는 방식이고 레벨 순회는 루트 노드부터 같은 레벨인 노드를 차례로 탐색하는 방식이므로 너비 우선 순회(Breadth-first Traversal)라고도 한다.
따라서 전위 순회는 현재 -> 왼쪽 -> 오른쪽, 중위 순회는 왼쪽 -> 현재 -> 오른쪽, 후위 순회는 왼쪽 -> 오른쪽 -> 현재 순서로 방문하는 방식으로 단순하게 어느 지점에서 현재 노드를 출력하느냐의 차이일 뿐이다.
또한 레벨 순회는 그래프 탐색의 BFS(Breadth First Search)와 같이 큐를 사용하는 방법이므로 굳이 다루진 않겠다.
이진 트리
오른쪽과 같은 이진 트리를 예시로 들어보자.
순회를 하기 전에 조금 더 구체적인 설명을 하자면 루트인 3인 노드를 기준으로 왼쪽으로 내려가면 현재 노드가 1인 서브 트리, 오른쪽으로 내려가면 현재 노드가 5인 서브 트리로 생각할 수 있다.
각 서브 트리에서 다시 서브 트리로 내려갈 수 있는 구조이다.
즉, 전위 순회는 3->1->0->2->5->4->6, 중위 순회는 0->1->2->3->4->5->6, 후위 순회는 0->2->1->4->6->5->3 순으로 탐색하게 된다.
순회 구현
트리를 구현하는 방법은 다양하지만 자세한 건 이진 탐색 트리 포스팅에서 다루도록 하겠다.
이번 포스팅에서는 딕셔너리를 이용하여 구현했다.
딕셔너리의 키(Key)는 현재 노드의 값을 뜻하고 값(Value)은 길이가 2인 리스트로 선언하여 0번째 인덱스는 왼쪽 자식의 값, 1번째 인덱스는 오른쪽 자식의 값을 뜻한다.
이때 자식 노드가 없는 것을 표현하기 위해 '*'로 선언하여 숫자가 존재할 때만 해당 자식 노드로 이동하도록 구현하면 된다.
전체 코드를 통해 설명하겠다.
defpreorder(root):print(root,end=" ") #현재 노드 출력if binary_tree[root][0]!="*": #왼쪽 자식 노드가 존재하면 이동
preorder(binary_tree[root][0])
if binary_tree[root][1]!="*": #오른쪽 자식 노드가 존재하면 이동
preorder(binary_tree[root][1])
definorder(root):if binary_tree[root][0]!="*":
inorder(binary_tree[root][0])
print(root,end=" ")
if binary_tree[root][1]!="*":
inorder(binary_tree[root][1])
defpostorder(root):if binary_tree[root][0]!="*":
postorder(binary_tree[root][0])
if binary_tree[root][1]!="*":
postorder(binary_tree[root][1])
print(root,end=" ")
root=3
binary_tree={3:[1,5],1:[0,2],0:['*','*'],2:['*','*'],5:[4,6],4:['*','*'],6:['*','*']}
print("전위 순회시작")
preorder(root)
print("\n\n중위 순회시작")
inorder(root)
print("\n\n전위 순회시작")
postorder(root)
구성을 보면 상당히 간단하단 것을 알 수 있다.
단순히 현재 노드의 값을 출력하는 부분이 어디에 위치하느냐에 따라 구분된다는 것을 알 수 있다.
따라서 한 가지를 이해하면 다른 것도 쉽기 때문에 Preorder로 설명하겠다.
시작은 루트부터 출발하여 각 함수의 매개변수로 넘겨준다.
해당 노드를 출력하고 만약 해당 노드의 왼쪽 자식 노드가 존재한다면 왼쪽 자식 노드의 값을 매개변수로 넘기고 재귀 호출한다.
그다음 오른쪽 자식 노드가 존재한다면 오른쪽 자식 노드의 값을 매개변수로 넘기고 재귀 호출한다면 알아서 반복하게 된다.
순회의 결과
여기까지가 이진 트리에 대한 이론이지만 이를 실제 적용하기엔 다소 제한이 있다.
이진 트리를 직접 구현하여 사용하는 것은 이진 탐색 트리(Binary Search Tree)라고 하며 삽입과 삭제에 여러 가지 조건이 붙기 때문이다.
또한 트리도 사람마다 편한 방식이 다르기 때문에 다양한 구현 방법과 이진 탐색 트리의 작동 방식을 다음 포스팅에서 학습하도록 하겠다.
자료구조(Data Structure)를 공부할 때 가장 처음 접하는 것은 스택(Stack)과 큐(Queue)다.
그전에 자료구조란 Data를 효율적으로 저장하고 접근하여 사용하는 방법을 뜻한다.
적합한 상황에 적절한 자료구조를 사용하면 아주 효율적인 알고리즘을 사용할 수 있는 장점이 있다.
이번 시간에 가장 기본 중에 기본인 스택과 큐에 대해 알아보겠다.
스택 (Stack)
먼저 스택은 나중에 들어오는 Data가 먼저 나가는 LIFO(Last In First Out) 형태이다.
통에다가 블록을 넣고 빼는 방식을 연상하면 이해가 쉬울 것이다.
Data를 넣는 연산은 Push라고 한다.
Push 연산 결과
반대로 Data를 빼는 연산은 Pop이라고 한다.
Pop 연산 결과
그림을 통해 쉽게 이해할 수 있듯이 나중에 들어간 Data가 먼저 나오고 먼저 들어간 Data가 나중에 나오는 자료구조를 스택이라고 표현한다.
만약 C 같이 다른 언어였다면 구조체를 선언하여 현재 얼마나 Data가 들어왔는지 판단하는 Top이란 변수를 통해 구현하겠지만 Python은 그럴 필요가 없다.
보통 라이브러리를 사용하는 경우를 제외하면 구현의 편의성을 위해 배열을 미리 선언(정적 할당)하고 잘못된 인덱스로 접근하는 Index Error를 방지하기 위해 Top이란 변수를 선언하여 오류를 방지한다.
또한 필요하다면 배열의 크기를 변경하는 복잡한 과정을 거쳐야 한다.
하지만 Python은 배열이 아닌 리스트를 지원하기 때문에 비교적 Data 추가 삭제에 대한 고민을 덜 수 있다.
큐 (Queue)
다음은 큐다.
큐는 먼저 들어온 Data가 먼저 나가는 FIFO(First In First Out) 형태이다.
즉, 차례대로 줄을 서서 기다리는 형태를 생각하면 된다.
큐에서 Data를 넣는 연산은 Enqueue라고 한다.
Enqueue 연산 결과
Data를 빼는 연산은 Dequeue라고 한다.
스택과는 다르게 먼저 들어간 Data가 먼저 빠지는 것을 확인할 수 있다.
Dequeue 연산 결과
구현
Python은 앞서 말한 대로 배열이 아닌 리스트를 지원하기 때문에 리스트와 관련되어 지원하는 함수들로 아주 쉽게 스택과 큐를 구현 가능하다.
여러 가지 함수들이 있지만 구현하는데 필요한 함수는 append()와 pop()이다.
각각 뒤에 원소를 추가하고 빼는 함수인데 pop(x)처럼 안에 인자를 넣으면 x번째 원소를 반환하고 제거한다는 의미이다.
이를 이용하여 x에 0을 넣으면 0번째 원소를 제거하므로 쉽게 큐를 구현할 수 있다.
다음은 앞서 설명한 과정을 그대로 구현한 전체 코드이다.
stack=[] #스택 선언print("현재 스택 :",stack)
stack.append(1) # 1 추가print("현재 스택 :",stack)
stack.append(2) # 2 추가print("현재 스택 :",stack)
stack.pop() #끝 원소 하나 제거print("현재 스택 :",stack)
stack.pop() #끝 원소 하나 제거print("현재 스택 :",stack, end="\n\n")
queue=[] #큐 선언print("현재 큐 :",queue)
queue.append(1) # 1 추가print("현재 큐 :",queue)
queue.append(2) # 2 추가print("현재 큐 :",queue)
queue.pop(0) #첫 원소 하나 제거print("현재 큐 :",queue)
queue.pop(0) #첫 원소 하나 제거print("현재 큐 :",queue)
결과 화면
복잡한 과정 없이 함수 두 개로 간단하게 구현하였으며 보통 그래프 탐색에서 스택은 깊이 우선 탐색(DFS), 큐는 너비 우선 탐색(BFS)에 자주 쓰인다.
따라서 코테준비를 위해 상당히 자주 사용할 문법이므로 알아야 한다.
데크 (Deque)
사실 큐는 구현 방법에 따라 다양한 이름이 있는데 가장 단순한 큐(Queue), 배열의 비효율성을 개선하기 위한 원형 큐(Circular Queue), 앞과 뒤 둘 다 Data를 넣고 뺄 수 있는 데크(Deque), 자료구조 중 하나인 힙(Heap)을 이용한 우선순위 큐(Priority Queue) 이런 식으로 장단점을 개선한 방식이 존재한다.
Python의 특성 상 원형 큐는 구현할 필요가 없고 우선순위 큐는 파이썬의 모듈 중 하나인 heapq를 사용하면 된다.
이번에 추가적으로 설명할 자료구조는 데크다.
데크 혹은 덱이라 부르는데 이 자료구조는 앞과 뒤에서 Enqueue와 Dequeue가 가능하다.
Deque 연산
파이썬의 pop()은 O(1)의 시간 복잡도가 들지만 첫 번째 원소를 제거하기 위해 pop(0)을 사용하게 되면 끝에서부터 원소를 찾기에 O(n)의 시간 복잡도가 걸린다.
따라서 Input이 너무 큰 상황이라면 효율을 위해 데크를 사용하여 시간 복잡도를 줄일 수 있다.
주요 함수는 append(), appendleft(), pop(), popleft()이고 left가 붙으면 첫 번째에, 붙지 않으면 마지막에 적용된다.
데크 구현
다음은 데크의 연산 과정을 확인할 수 있는 전체 코드이다.
from collections import deque #데크 모듈 선언
deque=deque()
print("현재 데크 :",deque)
deque.append(1) #오른쪽에 1 추가print("현재 데크 :",deque)
deque.appendleft(2) #왼쪽에 2 추가print("현재 데크 :",deque)
deque.popleft() #첫 번째 원소 제거print("현재 데크 :",deque)
deque.pop() #끝 원소 제거print("현재 데크 :",deque)
결과 화면
처음 보면 모듈 선언이 다소 어려울 수 있겠지만 익숙해진다면 그냥 리스트로 구현하는 것보다 시간 복잡도적으로 유리한 구현이 가능해진다.
이 중 가장 처음으로 접하는 테스트인 알고리즘 구현 능력은 주어진 문제를 해결하는 과정을 평가하므로 적절한 상황에 적합한 알고리즘을 적용하기 위해 자료구조와 알고리즘 학습이 필수입니다.
따라서 이 책은 취업 준비를 위해 자료구조와 알고리즘을 복습, 독학하는 과정에서 프로그래밍 언어에 대한 자료는 많이 있지만 자료구조와 알고리즘을 같이 묶은 집약된 자료를 찾기 어려웠고 국비지원 강의를 들을 때 비전공자 분들과 협업한 경험을 통해 프로그래밍 자체에 어려움을 겪는다는 것을 알게 되어 도움이 되고자 작성하게 되었습니다.
이 부분에 착안하여 고등학교 수리 과외 경험을 살려 언어만 알고 있다면비전공자도 최대한 쉽게 이해할 수 있도록 작성한 PDF 형태의 전자책입니다.
언어는 가장 기본으로 여겨지는 C와 이해가 쉬운 Python을 기반으로 작성하였으며 목차에서 목록을 클릭하면 해당 본문 페이지로, 본문 페이지의 제목을 클릭하면 다시 목차로 넘어올 수 있도록 만들었기에전자책의 편의성을극대화하였습니다.
공부가 주목적이라 마케팅이 전혀 없었기에 몇 권 팔리진 않았지만 지인을 포함한 구매하신 분들 전부 좋은 자료라는 호평이 이어졌습니다.
![data=[1,2,4,5,6,8,9]](https://blog.kakaocdn.net/dn/Dq4Jk/btrmK0xgMr0/KbsYQmG4kYb8n1a8m9Nsv0/img.jpg)
