설명

힙(Heap)은 트리(Tree)의 일종으로 우선순위 큐로 활용이 가능하다.

만약 트리에 대해 처음 보거나 익숙하지 않은 상태라면 해당 링크를 통해 이해한 뒤 학습해야 이해가 될 것이다.

https://khsung0.tistory.com/24

힙은 최대 힙(Max Heap), 최소 힙(Min Heap) 두 가지가 있다.

이진 탐색 트리(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 in range(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 in range(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도 쉽고 함수도 어렵지 않아서 한 두 번 보면 쉽게 익힐 수 있을 것이다.

이를 코테에 활용하면 보다 쉽게 통과할 수 있을 것이다.

설명

자료구조는 크게 선형 구조, 비선형 구조로 나눠진다.

선형 구조는 Data를 차례대로 나열시킨 형태를 뜻하고 비선형 구조는 선형 구조가 아닌 모든 형태를 말한다.

즉, 노드와 간선으로 이루어진 그래프(Graph), 그래프 중에서도 순환(Cycle)이 없는 그래프가 나무를 뒤집은 형태로 구성되어있다 해서 이름 붙여진 트리(Tree)가 비선형 구조이다.

그중에서도 이번 강의엔 트리를 설명하겠다.

트리 (Tree)

트리(Tree)란 앞서 말한 대로 나무가 뒤집어진 형태와 비슷해서 트리라 이름 붙어졌다.

트리에 대한 여러 명칭이 있는데 그림을 통해 설명하면 이해가 될 것이다.

해당 그림은 직접 작성한 "쉽게 풀어쓴 자료구조와 알고리즘 기본 가이드"에서 제작한 그림과 유사하게 다시 만들었다.

먼저 저 숫자가 들어간 동그라미는 노드(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)는 모든 노드가 왼쪽 혹은 오른쪽 자식만 갖고 있는 형태이다.

완전 이진 트리(Complete Binary Tree)는 마지막 Level을 제외한 모든 Level의 노드가 완전히 채워져 있으며 마지막 Level의 노드들은 왼쪽부터 채워져 있는 형태이다.

포화 이진 트리(Full Binary Tree)는 완전 이진 트리에서 마지막 Level의 노드들도 채워져 있는, 즉 이진 트리가 보유할 수 있는 최대 노드를 가진 형태가 포화 이진 트리다.

이진 트리 순회 (Binary Tree Traversal)

이진 트리의 순회는 총 4가지가 있다.

1. 전위 순회 (Pre-order)
2. 중위 순회 (In-order)
3. 후위 순회 (Post-order)
4. 레벨 순회 (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번째 인덱스는 오른쪽 자식의 값을 뜻한다.

이때 자식 노드가 없는 것을 표현하기 위해 '*'로 선언하여 숫자가 존재할 때만 해당 자식 노드로 이동하도록 구현하면 된다.

전체 코드를 통해 설명하겠다.

def preorder(root):
    print(root,end=" ")                     #현재 노드 출력
    if binary_tree[root][0]!="*":           #왼쪽 자식 노드가 존재하면 이동
        preorder(binary_tree[root][0])
    if binary_tree[root][1]!="*":           #오른쪽 자식 노드가 존재하면 이동
        preorder(binary_tree[root][1])

def inorder(root):
    if binary_tree[root][0]!="*":
        inorder(binary_tree[root][0])
    print(root,end=" ")
    if binary_tree[root][1]!="*":
        inorder(binary_tree[root][1])

def postorder(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)라고 하며 삽입과 삭제에 여러 가지 조건이 붙기 때문이다.

또한 트리도 사람마다 편한 방식이 다르기 때문에 다양한 구현 방법과 이진 탐색 트리의 작동 방식을 다음 포스팅에서 학습하도록 하겠다.

https://khsung0.tistory.com/26

설명

자료구조(Data Structure)를 공부할 때 가장 처음 접하는 것은 스택(Stack)과 큐(Queue)다.

그전에 자료구조란 Data를 효율적으로 저장하고 접근하여 사용하는 방법을 뜻한다.

적합한 상황에 적절한 자료구조를 사용하면 아주 효율적인 알고리즘을 사용할 수 있는 장점이 있다.

이번 시간에 가장 기본 중에 기본인 스택과 큐에 대해 알아보겠다.

스택 (Stack)

먼저 스택은 나중에 들어오는 Data가 먼저 나가는 LIFO(Last In First Out) 형태이다.

통에다가 블록을 넣고 빼는 방식을 연상하면 이해가 쉬울 것이다.

Data를 넣는 연산은 Push라고 한다.

반대로 Data를 빼는 연산은 Pop이라고 한다.

그림을 통해 쉽게 이해할 수 있듯이 나중에 들어간 Data가 먼저 나오고 먼저 들어간 Data가 나중에 나오는 자료구조를 스택이라고 표현한다.

만약 C 같이 다른 언어였다면 구조체를 선언하여 현재 얼마나 Data가 들어왔는지 판단하는 Top이란 변수를 통해 구현하겠지만 Python은 그럴 필요가 없다.

보통 라이브러리를 사용하는 경우를 제외하면 구현의 편의성을 위해 배열을 미리 선언(정적 할당)하고 잘못된 인덱스로 접근하는 Index Error를 방지하기 위해 Top이란 변수를 선언하여 오류를 방지한다.

또한 필요하다면 배열의 크기를 변경하는 복잡한 과정을 거쳐야 한다.

하지만 Python은 배열이 아닌 리스트를 지원하기 때문에 비교적 Data 추가 삭제에 대한 고민을 덜 수 있다.

큐 (Queue)

다음은 큐다.

큐는 먼저 들어온 Data가 먼저 나가는 FIFO(First In First Out) 형태이다.

즉, 차례대로 줄을 서서 기다리는 형태를 생각하면 된다.

큐에서 Data를 넣는 연산은 Enqueue라고 한다.

Data를 빼는 연산은 Dequeue라고 한다.

스택과는 다르게 먼저 들어간 Data가 먼저 빠지는 것을 확인할 수 있다.

구현

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가 가능하다.

파이썬의 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)

처음 보면 모듈 선언이 다소 어려울 수 있겠지만 익숙해진다면 그냥 리스트로 구현하는 것보다 시간 복잡도적으로 유리한 구현이 가능해진다.

스택과 큐를 연습할 수 있는 문제를 추천하며 마무리 짓겠다.

https://www.acmicpc.net/problem/10828

https://www.acmicpc.net/problem/10845

개발자로 취업하기 위해선 중요한 요소들이 몇 가지 있습니다.

보통 IT 직무의 채용 절차는 다음과 같습니다.

코딩 테스트 -> 필기 테스트 -> 역량 면접 -> 인성 면접 -> 건강검진 -> 입사

각각

1. 알고리즘 구현 능력
2. CS(Computer Science) 지식 (전공 이론 지식)
3. 실무 적응 가능성
4. 회사 및 직무 적합도
5. 건강 이상

위의 요소가 중요합니다.

이 중 가장 처음으로 접하는 테스트인 알고리즘 구현 능력은 주어진 문제를 해결하는 과정을 평가하므로 적절한 상황에 적합한 알고리즘을 적용하기 위해 자료구조와 알고리즘 학습이 필수입니다.

따라서 이 책은 취업 준비를 위해 자료구조와 알고리즘을 복습, 독학하는 과정에서 프로그래밍 언어에 대한 자료는 많이 있지만 자료구조와 알고리즘을 같이 묶은 집약된 자료를 찾기 어려웠고 국비지원 강의를 들을 때 비전공자 분들과 협업한 경험을 통해 프로그래밍 자체에 어려움을 겪는다는 것을 알게 되어 도움이 되고자 작성하게 되었습니다.

이 부분에 착안하여 고등학교 수리 과외 경험을 살려 언어만 알고 있다면 비전공자도 최대한 쉽게 이해할 수 있도록 작성한 PDF 형태의 전자책입니다.

언어는 가장 기본으로 여겨지는 C와 이해가 쉬운 Python을 기반으로 작성하였으며 목차에서 목록을 클릭하면 해당 본문 페이지로, 본문 페이지의 제목을 클릭하면 다시 목차로 넘어올 수 있도록 만들었기에 전자책의 편의성을 극대화하였습니다.

공부가 주목적이라 마케팅이 전혀 없었기에 몇 권 팔리진 않았지만 지인을 포함한 구매하신 분들 전부 좋은 자료라는 호평이 이어졌습니다.

관심 있으신 분들은 한 번 구경하셔도 좋을 것 같습니다!!

https://kmong.com/gig/290286