muntari Log muntari Log

최단 경로 (Shortest Path) 두 노드 사이에 존재할 수 있는 모든 경로 중 거리가 가장 짧은 경로를 말한다. 비가중치 그래프에서는 경로 중 엣지의 수가 가장 적은 것이 최단 경로이며 가중치 그래프에서는 보통 엣지의 가중치의 합이 가장 적은 경로가 최단 경로가 된다. 최단 경로 알고리즘 주어진 그래프에서 두 노드 사이에 가장 짧은 경로를 구하는 방법을 최단 경로 알고리즘이라 부른다. 이 최단 경로 알고리즘은 단 하나의 방법으로 구성되어 있지 않고 여러 방법이 존재한다. 엣지의 방향이 있는지, 가중치가 있는지, 음수 엣지가 존재하는지, 싸이클이 존재하는 지 등등 다양한 그래프 특징에 ㅏ따라 많은 방법이 존재한다. 대표적으로 두 개의 최단 경로 알고리즘인 BFS와 Dijksatr 알고리즘을 알아보자..

그래프 탐색 보통 탐색은 주어진 조건에 맞는 데이터를 찾는 것을 의미 하지만 그래프에서의 탐색은 하나의 노드를 시작점으로 연결된 노드들을 모두 찾는 것을 탐색이라고 말한다. 자료구조 안에 저장된 모든 데이터를 도는 것을 순회라고 하는데 따라서, 그래프에서의 탐색도 하나의 노드에서 연결된 모든 노드를 돌기 때문에 그래프 순회라고도 부르기도 한다. (그래프 탐색과 그래프 순회는 같은 말이다.) 그래프를 탐색하며 알 수 있는 정보 그래프를 탐색하면 그래프의 구조에 대해 의미 있는 정보들을 알아낼 수 있다. 1. 주어진 두 노드가 경로를 통해 연결되어있는지 여부 2. 주어진 두 노드 사이의 최단 경로를 알아낼 수 있다. 대표적으로 두가지 정도가 있으나 정렬 등 많은 문제에서 그래프 탐색을 사용하여 문제를 해결할..

그래프 그래프는 연결 관계에 있는 데이터를 저장하는 자료구조이다. 그래프는 노드라는 가장 작은 단위의 데이터로 이루어져 있는데, 각 노드들의 관계가 동등한 위치에 있을 경우 그래프를 적용하여도 무방할 것 같다. 자료구조를 공부해야 하는 이유는 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위해서이다. 데이터 사이에 어떤 관계가 있는지 파악하고 그에 맞는 적절한 자료구조를 사용하기 위함이다. 앞, 뒤와 같은 순서 데이터를 저장하기 위해서는 배열, 링크드 리스트 같은 선형 자료구조를 상, 하 관계와 같은 계층 데이터를 저장하기 위해서는 트리와 같은 계층 자료구조를 사용하면 된다. 그렇다면 그래프는 언제 사용하는 걸까? 그래프는 연결 관계에 있는 데이터를 저장한다고 하였는데 이는 실제로 우리 생활에서 무궁무..

이진 탐색 트리와 해시 테이블 해시 테이블로 구현하는 딕셔너리와 세트 자료형을 이진 탐색 트리로 구현할 수 있다. 노드 인스턴스를 딕셔너리와 세트의 인스턴스로 지정하여 구현할 수 있다고 한다. 먼저 왜 이진 탐색 트리로 딕셔너리와 세트 자료형을 구현해서 사용하는 이유를 알아보자. 딕셔너리와 세트 자료형은 파이썬 내부적으로 해시 테이블로 구현되어 있다.(해시 테이블 포스팅 참고) 굳이 이진 탐색 트리로 구현하는 이유는 뭘까? 해시 테이블의 경우 데이터의 순서 관계를 저장하지 않는 자료구조이다. 반면에, 이진 탐색 트리의 경우 데이터 사이에 순서를 저장하는 역할 하는 자료구조이며 in-order 방식으로 노드를 순회하면 트리 안에 있는 데이터를 순차적으로 출력할 수 있다. 결국, 세트의 데이터나 딕셔너리의 ..

이진 탐색 트리 트리의 일종으로 이진 트리이면서 이진 탐색 트리의 속성을 만족하는 트리를 이진 탐색 트리라고 부른다. 영어로는 Binary Search Tree 라고 부른다. 이진 탐색 트리를 사용하면 저장한 데이터를 쉽게 찾아 올 수 있다. 이진 트리는 각 노드가 최대 2개의 자식 노드만 가질 수 있는 트리를 말한다. 이진 트리에서는 모든 노드가 2개, 1개, 0개의 자식 노드만 가지고 있다. 여기서 이진 탐색 트리의 속성은 아래와 같다. 1. 특정 노드를 기준으로, 특정 노드의 왼쪽 부분 트리에 있는 모든 노드는 특정 노드의 데이터보다 작아야 한다. 2. 특정 노드를 기준으로, 특정 노드의 오른쪽 부분 트리에 있는 모든 노드는 특정 노드의 데이터보다 커야 한다. 루트 노드가 아닌 모든 루트에 적용되는..

힙을 활용하는 대표적인 2가지 방법 1. 정렬 2. 우선순위 큐를 구현하는 법 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 많이 사용된다! 정렬 알고리즘 데이터를 재배치하는 구체적인 방법을 정렬 알고리즘이라 한다. 삽입 정렬, 선택 정렬, 퀵 정렬, 합병 정렬 + 힙 정렬 등이 있다. 보통 정렬 알고리즘의 경우 O(n logn) 정도만 되도 효율이 좋은 측에 속한다 하니 아래의 시간 복잡도를 서로 비교해보자. 힙 정렬 Tree = [None, 14, 8, 12, 5, 4, 10, 6, 2, 1, 3] 위 예시로 힙 정렬 알고리즘의 방법은 아래와 같이 정리 할 수 있다. 1. 힙을 만든다. (이때 최댓값을 구하고 싶으면 max heap을 반대의 경우 min ..

힙 완전 이진 트리를 기 이진 트리를 기본으로 하는 자료구조로 트리의 일종이며 아래 두개의 조건을 만족하는 트리이다. 최댓값 , 최솟값을 쉽게 추출 할 수 있는 자료구조이다. 이러한 힙은 힙_2에서 설명할 우선순위 큐를 위하여 만들어진 자료구조라 한다. 1. 형태 속성 : 힙은 완전 이진 트리여야 한다. 2. 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 작아야 한다. - Heap은 부모 노드가 항상 자식 노드보다 크거나 같아야 하는 경우(max heap)와 부모 노드가 항상 자식 노드보다 작거나 같아야 하는 경우(min heap)로 나눌 수 있다. 최댓값을 추출하고자 할때는 부모 노드가 자식 노드보다 항상 큰 max heap으로 최솟값을 추출하고자 할때는 부모 노드가 자식 노드보다 ..

데이터의 계층 관계를 저장하는 자료구조이다. 여기서 계층은 상 - 하 관계에 해당 하는 데이터이다. 트리는 앞선 배열, 링크드리스트와 같은 선형 자료구조가 아닌 비선형 자료구조이다. (트리를 순회하는 과정에서 선형 자료구조와 같이 데이터를 출력할 수 도 있다.) 링크드리스트와 같이 노드 라는 객체 단위의 데이터를 사용하여 관계를 저장한다. 트리에서의 노드는 하위 관계가 있는 노드들을 가르키는 레퍼런스를 갖는다. class Node: """트리 노드를 나타내는 클래스""" def __init__(self, data): """트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다""" self.data = data self.left_child = None self.right_child = None 트리..