알고리즘 문제에 종종 등장하는 내용이기 때문에 따로 정리해둡니다.​▶ n진수 -> 10진수파이썬에서 기본적으로 제공하는 int()함수를 사용하면 됩니다.int(string, base)로 사용할 수 있습니다. string에는 변경하고자 하는 n진수를 문자열 형태로, base에는 string에 해당하는 진법을 넣으면 됩니다.print(int('1010',2))print(int('2020',3))print(int('3030',4))print(int('4040',5))print(int('5050',6))print(int('ACFD',16))// 결과창1060204520111044285  ​▶ 10진수 -> 2, 8, 16진수bin(), oct(), hex() 함수를 이용하면 됩니다.print(bin(10))pr..

▶ 이진 트리(Binary Tree)란?이진 트리는 트리 자료구조 중에서 가장 간단한 형태의 트리입니다. 일반적인 이진 탐색 트리는 아래 그림과 같은 구조를 갖습니다. 모든 트리가 다 이진 트리는 아니며, 이진 탐색 트리는 아래와 같은 두 가지의 특징을 가집니다.- 부모 노드보다 왼쪽 자식 노드가 작습니다.- 부모 노드보다 오른쪽 자식 노드가 작습니다.수식으로 표현하자면 왼쪽 자식 노드 가 성립해야지만 이진 트리라고 할 수 있는 것입니다.​보통 이진 트리는 파이썬의 클래스를 이용해 표현합니다. 위 그림의 이진트리를 파이썬 코드를 이용해 나타내보겠습니다.class Node: ## 각 노드의 값과 왼쪽 노드와 오른쪽 노드의 정보 저장 def __init__(self, item): sel..

소수란, 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..

- 크루스칼(Kruskal) 알고리즘이란? 크루스칼 알고리즘에 대해 설명하기 전, 서로소 집합 연산과 신장 트리에 대해 알아야 합니다! 그럼 각각에 대한 개념을 설명하겠습니다. ​ 1) 서로소 집합 서로소 집합이란! 수학적 의미 그대로 공통 원소가 없는 두 집합을 의미합니다. 두 개의 집합이 주어졌을 때 겹치는 요소들이 하나도 없어야 합니다. 두 집합이 서로소인지 판별하는 알고리즘은 다음과 같습니다. 1. 합집합 연산(union)을 통해 서로 연결된 두 노드 A와 B를 확인합니다. => A와 B의 루트 노드 A'과 B'을 각각 찾습니다. => A'를 B'의 부모 노드로 설정해줍니다. 2. 모든 합집합 연산을 처리할 때까지 1번 과정을 계속 반복해줍니다. 이 서로소 집합 연산을 이용한다면 무방향 그래프에서..