1. 배열을 이용한 이진 트리 표현 루트의 번호를 1로 하고 레벨 n에 대하여 왼쪽부터 오른쪽으로 $2^{n}$부터 시작하여 번호를 부여 노드 번호를 index로 해서 배열에 노드 정보를 저장 완전 이진트리일때만 가능할듯 아니라면 빈 부분은 0으로 채우고 데이터를 넣으면 될것 같은데 조금 복잡해질것 같고 높이 h가 주어진다면.. h의 노드 최대개수는 $2^{h+1}-1$개니까 [0]*$2^{h+1}-1$으로 초기화 노드 개수 n개가 주어진다면 뭐 [0]*(n+1)로 초기화하면 될듯 라고 생각했는데.. 이게 아니야 왜 그런지는 뒤에 쓴다 1-1) 노드 번호의 특징 완전이진트리처럼 번호를 붙이는 방식인 1번부터 n번까지를 왼쪽부터 오른쪽으로 차례대로 붙일때만 성립함 1)레벨 n의 시작 노드 번호는 $2^{n..
1. 이진트리 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 모든 노드들이 자식 노드를 "최대" 2개까지만 가질 수 있는 트리 각 자식 노드를 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node) 이진 트리 예시 4가지.. 모든 노드가 자식 노드를 "최대" 2개만 가지면 이진 트리가 된다 자식 노드가 아예 없어도 된다는 소리 2. 특징 레벨 i에서(높이 i에서) 노드의 최대 개수는 $2^{i}$개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개 최대 개수는 $2^{h+1}-1$개 3. 종류 이진트리의 종류에 따라 저장, 표현, 알고리즘 등이 달라질 수 있으므로 잘 구분해야한다 3-1) 포화 이진 트리(full binary tree..
1. 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조 ############### 선형구조와 비선형구조 간단히 ################################# 2. 트리의 정의 1개 이상의 노드로 이루어진 유한 집합 즉, 노드가 1개만 있어도 트리 최상위 노드를 root라고 부른다 루트 이외의 나머지 노드들은 n개의 부분집합 $T_{1}, T_{2}, T_{3},... , T_{n}$으로 분리 가능하다 그림과 같이 $T_{1}, T_{2}, T_{3},... , T_{n}$도 하나의 트리가 되며, 루트의 부 트리(subtree)가 된다 그러니까 어떤 tree의 일..
서로소 집합 알고리즘(disjoint set) 그래프 내에서 여러개의 node가 존재할 때 2개의 node를 선택해서 이 node가 서로 같은 node에 속하는지 판별하는 알고리즘 예를 들어 다음과 같이 8개의 node가 존재한다면 이런 경우는 부모 node가 자기 자신인 경우이다 이제 1과 2가 연결되었다고 생각해보자 이런 경우 2의 부모 node는 1이 된다 이렇게 합쳐나가는 과정을 union알고리즘이라고 부른다 이번엔 2와 3도 연결되었다고 가정해본다면 그러면 3의 부모 node는 2가 되는데 3과 1이 연결되었다는 것은 어떻게 아는가? 3의 부모 node는 2이고 2의 부모 node는 1이라서 부모 node만 보고서는 판단할 수가 없다 그렇지만 재귀함수를 사용하면 3의 부모 node가 2를 가리키..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수=가장 맵지 않은 음식의 스코빌 지수+(두 번째로 맵지 않은 음식의 스코빌..
최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리 트리는 root node에서 밑으로 가지를 뻗어나가는 형태의 자료구조로 binary tree인 이진 트리는 최대 2개까지만 자식 노드를 가진다 최소힙은 부모 node가 자식 node보다 항상 작은 binary tree 최대힙은 부모 node가 자식 node보다 항상 큰 binary tree heap은 배열로 구현되며 파이썬에서는 list로 만들어진다 import heapq를 통해 파이썬에서 heapq 관련 함수 사용가능 기존 리스트를 heapq로 만들려면 heapify()를 이용 heap2 = [50,10,20] heapq.heapify(heap2) print(heap2) [10,50,20] 혹은 빈 리스트를 생생한 후에 heappush..
