728x90 반응형 Algorithm/Basic9 알고리즘 기초 - 이진 트리(Binary Tree) ▶ 이진 트리(Binary Tree)란? 이진 트리는 트리 자료구조 중에서 가장 간단한 형태의 트리입니다. 일반적인 이진 탐색 트리는 아래 그림과 같은 구조를 갖습니다. 모든 트리가 다 이진 트리는 아니며, 이진 탐색 트리는 아래와 같은 두 가지의 특징을 가집니다. - 부모 노드보다 왼쪽 자식 노드가 작습니다. - 부모 노드보다 오른쪽 자식 노드가 작습니다. 수식으로 표현하자면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립해야지만 이진 트리라고 할 수 있는 것입니다. 보통 이진 트리는 파이썬의 클래스를 이용해 표현합니다. 위 그림의 이진트리를 파이썬 코드를 이용해 나타내보겠습니다. class Node: ## 각 노드의 값과 왼쪽 노드와 오른쪽 노드의 정보 저장 def __init__(s.. 2023. 1. 29. 알고리즘 기초 - 소수의 판별(에라토스테네스의 체) 소수란, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말합니다. 어떤 자연수 n이 소수인지 판별하는 가장 기초적인 함수 코드는 아래와 같이 작성할 수 있습니다. def is_prime(n): for i in range(2, n): if n%i==0: return False ## 소수 아님 return True 2부터 n-1까지의 모든 수로 n을 나누어보는 방법입니다. 만약 나누어 떨어지는 수가 있다면 소수가 아닌게 되겠죠? 그럼 False를 리턴합니다. 그러나 이런 방법은 n까지의 모든 수를 확인해야 하기 때문에 시간복잡도는 O(n)입니다. 따라서, n이 매우 크다면 비효율적이게 됩니다. 좀 더 개선된 방법을 적용한 코드는 아래와 같이 작성할 수 있습니다. import math d.. 2023. 1. 28. 알고리즘 기초 - 크루스칼 알고리즘(최소 신장 트리) - 크루스칼(Kruskal) 알고리즘이란? 크루스칼 알고리즘에 대해 설명하기 전, 서로소 집합 연산과 신장 트리에 대해 알아야 합니다! 그럼 각각에 대한 개념을 설명하겠습니다. 1) 서로소 집합 서로소 집합이란! 수학적 의미 그대로 공통 원소가 없는 두 집합을 의미합니다. 두 개의 집합이 주어졌을 때 겹치는 요소들이 하나도 없어야 합니다. 두 집합이 서로소인지 판별하는 알고리즘은 다음과 같습니다. 1. 합집합 연산(union)을 통해 서로 연결된 두 노드 A와 B를 확인합니다. => A와 B의 루트 노드 A'과 B'을 각각 찾습니다. => A'를 B'의 부모 노드로 설정해줍니다. 2. 모든 합집합 연산을 처리할 때까지 1번 과정을 계속 반복해줍니다. 이 서로소 집합 연산을 이용한다면 무방향 그래프에서.. 2023. 1. 28. 알고리즘 기초 - 최단 경로(플로이드-워셜, 벨만-포드) 이번 포스팅에서는 플로이드-워셜, 벨만-포드 알고리즘에 대해 설명하겠습니다. - 플로이드 워셜 알고리즘(Floyd-Warshall) 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구하고 싶을 떄 사용하는 알고리즘입니다. 각 단계마다 해당 노드를 거쳐가는 경우를 고려해야 합니다. 예를 들어, 1번 노드에 있을때는 1번 노드를 거쳐가는 모든 경우를 고려하면 됩니다. A->1->B인 경우의 비용을 확인 후 최단 거리를 갱신해주어야 합니다. 이를 점화식으로 나타내면, 아래와 같습니다! min 함수를 사용해 바로 이동하는 거리와 특정한 노드를 거쳐서 이동하는 거리를 이용해 짧은 것으로 갱신될 수 있도록 해줍니다. 다익스트라 알고리즘은 매번 최단 거리를 검색하지만 이 알고리즘은 그럴 필요가 없다는 점이 장점.. 2023. 1. 24. 이전 1 2 3 다음 728x90 반응형
