그래프(Graph) 그래프는 어떤 개념들 간의 연결관계를 표현하기 위해 사용하는 자료구조다. '개념들 간의 연결관계'라는 말이 모호하기 때문에 그 관계의 예를 몇 가지 들면, 사람과 사람 간의 관계, 도시와 도시와 연결된 도로들의 관계, 네트워크에서 A컴퓨터, B컴퓨터, C컴퓨터, ... 들 간의 관계 등이다. 즉, 그래프 자료구조에서 주로 포커싱되는 대상은 관계이며, 현실세계나 추상적인 개념의 문제들을 그래프 구조로 맵핑시키고 난 뒤에는 그 관계들을 이용해 다양한 알고리즘을 적용해 문제들을 해결할 수 있다. 1) 기본 개념 자료구조로서 그래프는, 위의 설명에서 개념에 대응하는 정점(Vertex; 노드(Node) - 컴퓨터 과학에서는 주로 노드를 씀)과 관계에 대응되는 간선(Edge)으로 이루어진다. 개..

SOLID란? 객체 지향 프로그래밍에서 항상 등장하는 SOLID원칙은 개발 및 보수를 하는 데 있어, 소스코드를 읽기 쉽고 확장이 원활하도록 만드는 다섯가지 원칙이다. SOLID는 각 원칙의 첫번째 글자를 합친 것으로 각각 Single Responsivility Principle, Open/Closed Principle, Liskov Substitution Principle, Interface Segregation Principle, Dependency Inversion Principle이다. SOLID 원칙을 사용하지 않더라도 객체 지향적인 프로그래밍은 가능하지만, 원칙을 지키면 동료들과의 협업이 원활해지며, 추후 소프트웨어를 확장할 때도 실수를 미연에 방지할 수 있다. 단일 책임 원칙(Single R..

힙(Heap) 힙 자료구조는 일종의 트리다. 힙은 형태 속성과 힙 속성을 만족해야 하는데, 즉 힙은 완전이진트리 구조여야 하며 힙 속성을 가져야 한다. 완전이진트리는 이전 글에서 작성한 것처럼 마지막 레벨을 제외한 모든 노드가 다 채워져 있는 이진 트리이며, 마지막 레벨은 왼쪽에서 오른쪽으로 채워져 있는 트리이다. 힙 속성은 각 노드의 데이터들은 각각의 자식 노드의 데이터보다 크거나 같은 속성을 말한다. 힙 구현하기 힙 자료구조 또한 완전이진트리 형태를 가지고 있으므로 동적 배열로 나타낼 수 있다. 즉, 파이썬에서는 리스트로 힙 자료구조를 표현할 수 있다. 아래는 최대힙을 구현한 코드이다. 간단하게 heapify, heappop, heappush함수를 구현했다. def _swap(arr, index_1,..

분리 집합 (Disjoint Set) 분리 집합은 서로소 집합이라고도 한다. 전체 집합 U에 대해 U의 분리 집합 A, B는 다음 조건을 만족한다. A, B는 U의 부분집합이다 A, B는 서로 공통 원소를 가지지 않는다 A, B의 합집합이 곧 전체집합 U이다. 즉, 전체 집합 U를 겹치는 부분이 발생하지 않도록 모든 원소를 분리시킨 집합을 분리 집합이라고 한다. 분리 집합은 일반적으로 두 원소가 같은 집합에 속하는지 빠르게 여부를 확인하거나, 두 집합을 합치는 등의 연산을 할 때 사용된다. 예를 들면 SNS에서 A라는 사람과 B라는 사람이 친구 관계인지 여부를 확인하거나, 친구를 맺었다면 두 집합을 합치는 연산을 할 수 있다. 분리 집합은 대표적으로 트리 자료 구조와 Union-Find 알고리즘으로 구현..

일반 트리(General Tree) 일반적인 트리는 노드들의 집합으로, 하나의 루트 노드와 서로 겹치지 않는 여러 개의 부분 집합으로 이루어진 나머지 노드들로 구성되어 있다. 트리에서는 노드들 간에 상하관계인 부모-자식 관계가 만들어진다. 즉 부모와 자식 간의 레퍼런스가 있어 서로의 노드를 식별할 수 있다. 일반 트리는 자식 노드 수의 제한이 없기 때문에 무한정 늘어날 수 있는 특징이 있으며, 이로 인해 노드의 수를 파악하기 어려우므로 알고리즘을 적절하게 사용하기 어렵다. 따라서 주로 일반 트리를 이진 트리로 변환해 사용한다. class Node: def __init__(self, data) -> None: self.data = data self.children = [] root = Node(1) nod..

해시 테이블(Hash Table) 해시 테이블은 key-value형태로 데이터를 저장하는 자료구조로, 일반적인 경우 O(1)의 시간복잡도로 값을 탐색할 수 있다. 1. Direct Access Table 우리가 저장할 key-value 쌍들이 있을 때 key값 중 가장 큰 숫자만큼의 배열을 생성한 뒤 해당 인덱스에 value를 저장하면, value에 접근하고 싶을 때 key를 통해 바로 접근할 수 있으므로 O(n)의 시간복잡도를 가진다. 이를 Direct Access Table이라고 한다. data = [(57, "고영희"), (208, "강아지"), (900, "고릴라")] max_index = 0 for key, value in data: if key > max_index: max_index = ke..

큐(Queue) 선입선출(First-In First-Out, FIFO)특징을 가진 자료구조다. 즉, 가장 나중에 들어온 자료가 가장 먼저 나가도록 되어 있다. 커스텀 큐 구현 싱글리 링크드 리스트로 큐를 구현해보자. 스택과 차이점은 한쪽 끝에서 연산이 이루어 지는 게 아니라 양쪽에서 각각 삽입과 인출이 일어난다는 것이다. 따라서 레퍼런스를 front와 rear로 두고 rear측에 새로운 노드가 삽입되고, front측에서 노드가 나가는 형태로 구현을 해야 한다. from typing import Iterable, Optional class Node: """싱글리 링크드 리스트 노드""" def __init__(self, data) -> None: self.data = data self.next = None..

스택(Stack) 후입선출(Last-in First-Out, LIFO)특징을 가진 자료구조다. 즉, 가장 최근에 들어온 자료가 가장 먼저 나가도록 되어 있다. 커스텀 스택구현 파이썬으로 스택을 구현하기 위해선 우선 두 가지 고려할 점이 있다. List? 일반적인 경우 그냥 파이썬 리스트로 스택을 사용해도 된다. 하지만 값이 계속해서 삽입되는 경우 파이썬 리스트는 동적 배열이므로 공간을 자동적으로 확장하면서 O(n)의 시간이 걸릴 때가 가끔 있다. 참고 공간이 작을 땐 문제가 안되겠지만 무지막지하게 큰 경우 시간이 오래 걸릴 수도 있다. Singly Linked List? 어차피 후입선출, 즉 맨끝에서만 자료가 삽입되고 나갈 수 있도록 구현하면 된다 각 자료들이 레퍼런스로만 연결되어 있기 때문에 공간의 확..

데크(Deque) 큐가 양쪽으로 연결된 형태. 따라서 양쪽에서 삽입과 삭제가 가능하다. 이미 파이썬에는 collections모듈에 deque가 구현되어 있다. c/c++로 구현되어 있으며 양쪽에서 삽입과 삭제가 가능해야 하므로 더블리 링크드 리스트로 만들어져 있다. 이로 인해 양쪽에서 삽입과 삭제가 O(1)의 시간이 걸리므로 코딩테스트 파이썬에서 스택이나 큐를 이용할 때 이 데크를 사용하기도 한다. 커스텀 데크 구현 파이썬으로 데크를 구현해 보았다. from typing import Iterable, Optional class Node: """더블리 링크드 리스트의 노드 클래스""" def __init__(self, data) -> None: self.data = data self.prev = None ..

원형 링크드 리스트 (Circular Linked List) 싱글리 링크드 리스트에서 마지막 노드가 다시 첫 노드와 연결되어 있는 자료구조다. 따라서 마지막 노드와 첫번째 노드를 O(1) 시간에 방문할 수 있다는 장점과 리스트가 비어있을 때를 제외하고 모든 노드의 레퍼런스가 None을 가지지 않기 때문에 None 조건에서 조금 자유로울 수 있다는 장점을 가지고 있다. 하지만 싱글리 링크드 리스트로 구현했다면 앞 노드를 방문하기는 쉽지 않다는 단점이 있다. 더블리 링크드 리스트로 구현하면 해결된다. 또한 무한 반복의 우려가 있다. class Node: def __init__(self, data) -> None: self.data = data self.next = None class CircularLinke..