본문 바로가기
반응형

전체 글96

Union-Find 유니온-파인드(Union-Find)는 집합의 분리와 합병을 효율적으로 수행하기 위한 알고리즘입니다. 이 알고리즘은 상호 배타적인(disjoint) 집합들을 관리하며, 각 집합에 대한 연산을 지원합니다. 유니온-파인드 알고리즘은 대표적으로 다음과 같은 두 가지 연산을 제공합니다: Union(합병) 연산: 두 개의 집합을 합쳐 하나의 집합으로 만듭니다. 즉, 두 개의 원소가 속한 집합을 찾아서 하나의 집합으로 합병합니다. Find(찾기) 연산: 특정 원소가 속한 집합을 찾습니다. 즉, 특정 원소가 어떤 집합에 속해 있는지를 확인합니다. 유니온-파인드 알고리즘은 대표적으로 상호 배타적 집합(disjoint set)을 관리하기 위해 사용됩니다. 상호 배타적 집합은 원소들이 중복되지 않고 하나의 집합에 속하도록 .. 2023. 6. 16.
product 파이썬의 product 함수는 itertools 모듈에 속한 함수로, 주어진 여러 개의 이터러블(iterable) 객체들의 곱집합(cartesian product)을 반환합니다. 곱집합은 각각의 이터러블 객체에서 하나의 원소를 선택하여 조합한 모든 가능한 조합을 의미합니다. product 함수는 다음과 같은 형식으로 사용될 수 있습니다: itertools.product(*iterables, repeat=1) 여기서 iterables는 하나 이상의 이터러블 객체를 나타내며, repeat는 선택적 매개변수로, 각 이터러블 객체를 반복할 횟수를 지정합니다. 기본값은 1입니다. 예를 들어, 다음과 같이 product 함수를 사용할 수 있습니다: import itertools colors = ['red', 'bl.. 2023. 6. 15.
ord ord() 함수는 문자의 유니코드 코드 포인트를 나타내는 정수를 반환합니다. 이 함수는 문자열 내의 각 문자에 대해 호출될 수 있습니다. 예시를 통해 ord() 함수를 이해해 보겠습니다: ch = 'A' code = ord(ch) print(code) # 출력: 65 위 예시에서는 문자 'A'의 유니코드 코드 포인트를 ord() 함수를 통해 얻었습니다. 'A'의 유니코드 코드 포인트는 65입니다. ord() 함수는 다양한 문자에 대해 사용될 수 있으며, 문자열 내의 모든 문자에 대해 코드 포인트를 얻을 수 있습니다. 2023. 6. 15.
DFS(Depth-First Search)와 BFS(Breadth-First Search) DFS(Depth-First Search) DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 깊이를 우선으로 탐색하는 방법입니다. DFS는 한 정점에서 시작하여 이웃한 정점을 방문하고, 해당 정점에서 다시 깊이 우선으로 탐색을 진행합니다. 이러한 방식으로 그래프를 탐색하며, 모든 경로를 탐색하거나 탐색 조건을 만족할 때까지 진행합니다. DFS는 스택(Stack) 또는 재귀 함수를 이용하여 구현할 수 있습니다. 각 정점을 방문했는지 여부를 확인하여 중복 방문을 방지하고, 이웃한 정점 중 아직 방문하지 않은 정점을 선택하여 탐색합니다. DFS는 보통 다음과 같은 순서로 동작합니다: 시작 정점을 방문하고 방문한 정점을 표시합니다. 시작 정점과 이웃한 정점 중에서 방문하지 않은 정점.. 2023. 6. 15.
set set은 파이썬에서 제공하는 데이터 컬렉션 타입 중 하나로, 중복되지 않는 요소들의 집합을 나타내는 자료구조입니다. set은 가변(mutable)하며, 순서가 없기 때문에 인덱스로 요소에 접근할 수 없습니다. set은 중괄호 {}를 사용하여 생성하며, 요소들은 쉼표로 구분하여 나열합니다. 예를 들어, my_set = {1, 2, 3}와 같이 생성할 수 있습니다. 또는 set() 생성자를 사용하여 빈 set을 생성할 수도 있습니다. set의 주요 특징과 기능은 다음과 같습니다: 중복된 요소가 없다: set은 중복된 값을 허용하지 않습니다. 같은 값을 여러 번 추가해도 한 번만 저장됩니다. 순서가 없다: set은 요소의 순서를 보장하지 않습니다. 따라서 인덱스로 요소에 접근할 수 없고, 순서에 의존하는 연산.. 2023. 6. 15.
permutations 과 combinations permutations과 combinations은 itertools 모듈에서 제공하는 함수로서, 주어진 요소들로 가능한 순열과 조합을 생성해주는 기능을 제공합니다. 1. permutations: permutations(iterable, r=None) 함수는 주어진 iterable에서 요소들의 순열을 생성합니다. 순열은 요소들의 순서를 바꿔서 생성하는 것을 의미합니다. 따라서 순서가 다른 경우에는 다른 순열로 취급됩니다. r 매개변수를 사용하여 생성할 순열의 길이를 지정할 수 있습니다. 기본값은 None으로, iterable의 모든 요소들로 가능한 모든 순열을 생성합니다. 반환값은 순열을 나타내는 튜플들로 이루어진 이터레이터입니다. 2. combinations: combinations(iterable, r.. 2023. 6. 15.
소수찾기와 에라토스테네스의 체 Python에서 소수를 찾는 방법은 다양한 방법으로 구현할 수 있습니다. 여기서는 가장 일반적이고 간단한 방법 두 가지를 소개하겠습니다. 소수 판별 함수: 주어진 숫자가 소수인지 판별하는 함수를 작성합니다. 소수는 1과 자기 자신만을 약수로 가지는 수입니다. def is_prime(n): if n < 2: # 0과 1은 소수가 아님 return False for i in range(2, int(n**0.5) + 1): if n % i == 0: # 약수가 존재하면 소수가 아님 return False return True 위의 함수는 주어진 숫자 n이 소수인지를 판별합니다. 2부터 n의 제곱근까지의 숫자로 나누어 떨어지는지 확인하여 소수인지를 결정합니다. 에라토스테네스의 체(Seive of Eratosth.. 2023. 6. 15.
cycle itertools 모듈의 cycle은 반복 가능한 객체의 요소들을 무한히 반복시키는 이터레이터를 생성하는 함수입니다. cycle 함수는 하나의 반복 가능한 객체를 인자로 받습니다. 이 함수를 호출하면 해당 객체의 요소들을 처음부터 끝까지 반복하면서 이터레이터를 생성합니다. 만약 객체의 끝에 도달하면 다시 처음부터 요소들을 반복합니다. 이 과정을 계속 반복하여 무한히 이어지게 됩니다. 예를 들어, 다음과 같이 cycle 함수를 사용하여 리스트의 요소들을 무한히 반복하는 이터레이터를 생성할 수 있습니다: from itertools import cycle my_list = [1, 2, 3] my_cycle = cycle(my_list) for i in range(10): print(next(my_cycle)).. 2023. 6. 15.
cmp_to_key cmp_to_key는 파이썬의 functools 모듈에 있는 함수로, 비교 함수를 키 함수로 변환하는 데 사용됩니다. cmp_to_key 함수를 사용하면 이전에 사용되던 cmp 함수를 쉽게 키 함수로 변환할 수 있습니다. cmp_to_key 함수는 다음과 같은 형태로 사용됩니다: from functools import cmp_to_key def compare_func(a, b): # 비교 로직 작성 # a와 b를 비교하여 -1, 0, 1 중 하나를 반환 key_func = cmp_to_key(compare_func) compare_func는 비교 로직을 작성한 함수로, 두 개의 인자 a와 b를 받아 비교하여 -1, 0, 1 중 하나를 반환해야 합니다. 반환 값이 음수인 경우 a가 b보다 작은 것으로 간주.. 2023. 6. 14.
PriorityQueue PriorityQueue는 우선순위 큐를 구현한 파이썬의 클래스입니다. 우선순위 큐는 요소들을 저장하고 관리하는 자료구조로, 각 요소는 우선순위를 가지며 우선순위에 따라 처리되는 순서가 결정됩니다. PriorityQueue는 일반적으로 힙(heap) 자료구조를 사용하여 구현되며, 우선순위가 가장 높은 요소가 가장 먼저 처리됩니다. PriorityQueue 클래스는 queue 모듈에 정의되어 있습니다. 사용하기 위해서는 queue 모듈을 import해야 합니다: from queue import PriorityQueue PriorityQueue 객체를 생성하고 요소를 추가하려면 다음과 같이 사용합니다: pq = PriorityQueue() pq.put(item) 여기서 item은 추가할 요소이며, 요소는 (.. 2023. 6. 14.
반응형

티스토리툴바