AI개발세발

02-10 그래프의 표현 드디어 자료구조의 마지막 파트입니다. 자료구조 이야기하다가 뜬금없이 그래프 얘기가 나와서 처음엔 '....?' 싶었습니다. 그게 우리가 아는 그래프랑 조금 다른 개념까지 포괄하는 것을 깨닫는 데는 단 5분도 걸리지 않았습니다... 애초에 그래프 자료구조를 얘기하기는 것이기도 했고 말이죠. 딥러닝 분야에는 GCN(Graph Convolutional Network)라는 학습 알고리즘이 따로 존재할 정도니 이번 파트도 잘 배워보죠. 그래프 def) 그래프 (Graph): 사물을 정점(vertex 또는 node)과 간선(edge)으로 나타내기 위한 도구 그래프를 수치적으로 나타나는 데에는 크게 2가지 방식이 있습니다. 인접 행렬(adjacency matrix): 2차원 배열을 사용하는 ..

02-09 우선순위 큐 우선순위 큐는 다양한 알고리즘 및 프로그램에서 사용 빈도가 높은 중요한 구조입니다. 이번 포스트에서는 우선순위 큐에 대한 일반적인 얘기를 먼저 한 뒤, 우선순위 큐의 가장 대표적인 예시인 힙(heap)을 알아보겠습니다. 우선순위 큐 def) 우선순위 큐 (Priority Queue): 우선순위에 따라서 데이터를 추출하는 자료구조 우선순위 큐는 큐(queue) 자료구조의 변형 형태로 볼 수 있으며, 컴퓨터 운영체제(OS)나 온라인 게임 매칭 등에 사용되는 구조입니다. 운영체제의 경우, 우리가 음악을 들으면서 문서 작업을 하는 등 한 컴퓨터에서 여러 작업을 동시에 작동시키는 경우가 많습니다. 당장 저만 해도 블로그 정리할 때 항상 유튜브 브금을 깔아놓습니다 이 때 프로그램의 우선순위를..

02-08 이진 탐색 트리 이진 탐색 트리는 다수의 데이터를 관리하는 데 적합한 트리(tree) 자료구조의 기본이 되는 구조이기 때문에 반드시 짚고 넘어가야 합니다. 트리 def) 트리 (tree): 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 루트 노드 (root node): 부모가 없는 최상위 노드 리프 노드 (leaf node): 자식이 없는 노드 깊이 (depth): 루트 노드에서의 길이(length, 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수) 높이 (height): 루트 노드에서 가장 깊은 리프 노드까지의 길이 그럼 먼저 트리 구조가 뭔지 간단하게 알아보겠습니다. 다음과 같이 나무를 뒤집어놓은 듯한 자료구조인 트리는 최상위 노드인 루트와 더 이상 자식이 없는 리프(단말) 노드..

02-07 덱 덱은 스택과 큐의 장점만 버무려놓은 자료구조로, 스택과 큐 대신에 덱만 사용해도 괜찮을 정도라고 합니다. 이번 포스트에서는 덱의 특성을 알아보고 파이썬에서의 구현을 해보겠습니다. 덱의 특성 def) 덱 (deque, double-ended queue의 약자): 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조 덱의 특성이라 하면 스택과 큐의 기능을 모두 가지고 있다는 점입니다. 다만, 스택이나 큐와 달리 포인터 변수가 더 많이 필요하기 때문에, 메모리는 상대적으로 더 많이 필요로 합니다. 파이썬에서는 큐의 기능이 필요할 때 간단히 덱 라이브러리를 사용하곤 합니다(다만, 큐 라이브러리도 따로 구현되어 있기는 합니다). 이에 대해서는 아래에서 다시 알아보겠습니다. 덱 연산 예제 덱에 여러 개의 ..

02-06 큐 def) 큐 (Queue): 먼저 삽입된 데이터가 먼저 추출되는 자료구조 선입선출 스택이 먼저 삽입된 데이터가 나중에 추출되는 자료구조였다면, 큐는 반대로 먼저 들어온 데이터가 먼저 추출되는 구조입니다. 큐도 게임 좋아하시는 분들이, 특히 온라인 게임을 즐겨하시는 분들이 많이 들어보셨을 용어입니다. 게임에서 큐라고 하면 흔히 매칭 대기 순서를 뜻하고, 먼저 대기한 사람이 먼저 매칭되는 구조를 갖는 거죠. 큐의 예시 스택에서와 마찬가지로 큐에 여러 개의 데이터를 삽입, 삭제하는 예시를 보겠습니다. 전체 연산은 아래와 같고, 지난 포스트에서 다룬 스택에서 썼던 예시 연산과 동일합니다. 삽입 3 - 삽입 5 - 삭제 - 삽입 7 - 삭제 - 삽입 8 - 삭제 - 삽입 2 - 삽입 9 큐와 다른 ..

02-05 스택 def) 스택 (Stack): 먼저 들어온 데이터가 나중에 나가는 자료구조 게임을 즐겨 하신 분들은 스택이라는 용어에 익숙하실지도 모르겠습니다. 공식 번역 등에서는 '중첩'이라고도 하는 스택을 쌓으면 능력치가 오르는 몇몇 스킬, 아이템들이 있죠.롤에서 볼 수 있는 메자이라든가 이와 비슷하게 상자를 쌓아올리듯이 데이터를 쌓는 자료구조를 스택(stack)이라고 합니다. 스택 자료구조의 특징으로는 먼저 들어온 데이터가 나중에 나간다는 점입니다. 우리가 박스를 쌓은 뒤에 꺼낼 때는, 가장 마지막에 올렸던 박스부터 꺼내고 그 위의 있는 다른 박스들까지 다 꺼내고 나서야 처음 쌓은 박스를 꺼낼 수 있죠. 반대로 가장 마지막에 들어온 데이터/박스가 가장 먼저 나갑니다. 스택 예제 스택에 여러 개의 데..

02-04 파이썬에서의 리스트 저번 포스트까지 배열과 연결 리스트에 대해 설명하는 것과 동시에 파이썬의 리스트 자료형과 비교해보았습니다. 아무래도 ML과 딥러닝 분야에서 파이썬이 주력 툴로 사용되기 때문에 그런 것이겠죠. 이번 포스트에서는 이전 시간까지의 내용에 연계하여 파이썬의 리스트 자료형을 알아보겠습니다. 파이썬의 리스트 자료형 함수 이해하기 저번 포스트에서 파이썬의 리스트(list)는 배열과 연결 리스트의 두 자료형 모두의 특성을 가지고 있다는 것을 알아봤습니다. 이를 위해 두 개의 파이썬 클래스를 정의해 연결 리스트에 대한 함수를 사용해봤는데요. 아래 표를 보시면 실제 파이썬에 구현되어 있는 리스트 관련 함수들을 알아볼 수 있습니다. 연산 시간 복잡도 사용 예제 설명 1 Indexing $O\l..

02-03 연결 리스트 def) 연결 리스트 (Linked List): 각 노드가 한 줄로 연결되어 있는 자료구조 지난 시간에 배열을 설명하면서 곁다리로 언급했던 연결 리스트에 대해 좀 더 자세히 알아보겠습니다. 각 노드는 (데이터, 포인터)의 한 쌍으로 묶여 있으며, 이러한 각 노드가 한 줄로 연결되어 있는 것이 연결 리스트입니다. 여기서 포인터는 다음 노드의 메모리 주소를 가리키는 역할을 합니다. 각 노드의 포인터가 다음 혹은 이전 노드를 가리키는 것을 연결성이라고 합니다. 연결 리스트를 이용하면 앞으로 배울 스택, 큐 등 다양한 자료구조를 구현할 수 있습니다. 다만, 우리가 데이터 사이언스와 ML 분야에서 주로 사용하는 파이썬은 연결 리스트를 활용하는 자료구조인 리스트(list)를 자체적으로 제공합..

02-02 배열 가장 기본적인 선형 자료구조로 배열(array)를 먼저 살펴보겠습니다. 배열은 일종의 표와 같이 여러 개의 변수를 담는 공간이자, 0부터 시작되는 인덱스(index)가 존재합니다. (인덱스는 순서 개념으로 보시면 되겠습니다. 파이썬을 다뤄보신 분들은 인덱스가 0부터 시작되는 것에 익숙하실 겁니다.) 아래 표에서 각각의 값마다 인덱스가 할당된 것을 볼 수 있습니다. 배열 자료는 자신이 원하는 특정한 인덱스에 직접적으로 접근할 수 있으며, 수행 시간을 시간 복잡도로 표현하면 $O\left(1\right)$입니다. 인덱스 0 1 2 3 4 5 6 7 8 값 25 75 83 59 24 72 55 17 42 배열의 특징 컴퓨터 부품 중 램(RAM)은 메인 메모리로써 저장장치 중에서는 읽고 쓰는 속..

Chapter 2. 딥러닝을 위한 자료구조 통계와 관련된 이론은 지난 포스트에서 끝났고, 오늘부터는 컴퓨터공학과 관련된 내용이 주를 이룹니다. 개인적으로 머신러닝을 깊게 파고들기 시작하면서 가장 아쉬웠던 부분이, 학부 당시 수업에서 머신러닝 기법과 그 적용 위주로만 수업을 들은 탓에 정작 그 기법으로 다뤄야 하는 데이터가 어떤 특성을 가지고, 그래서 어떻게 다루는 것이 더 효율적이고 올바른지를 전혀 알려주지 않았다는 겁니다(데이터 전처리(preprocessing)가 아니라 오늘부터 다룰 자료구조, 그 외에는 데이터베이스 등의 정보를 말하는 겁니다). 그래서 더더욱 이 챕터가 저에게 중요하게 다가오는 것 같네요. 저한테 왜 그랬어요 02-01 Data Structure 개요 자료구조 def) 자료구조 (D..