알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory)3

• 

  Karatsuba 알고리즘 Karatsuba 알고리즘이란?Karatsuba 알고리즘은 큰 수의 곱셈을 더 효율적으로 수행하기 위한 알고리즘입니다. 이 알고리즘은 1960년에 안넨카롤로스 Karatsuba에 의해 처음 개발되었으며, 전통적인 곱셈 방법보다 계산 복잡도가 낮습니다.1. 전통적인 곱셈의 문제점일반적으로 두 자리수가 각각 n자리수일 때, 이들을 곱하기 위해서는 O(n^2)의 시간이 소요됩니다. 예를 들어, 두 개의 4자리수를 곱할 때는 각 자리수마다 곱셈과 덧셈을 반복하는 방식으로 총 16번의 곱셈을 수행하게 됩니다. 이 방식은 숫자가 커질수록 연산량이 급격히 증가하여 비효율적입니다.2. Karatsuba 알고리즘의 기본 개념Karatsuba 알고리즘은 '분할 정복(Divide and Conquer)' 접근 방식을 사용하.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2024. 8. 13.

• 

  무한히 큰 수 두 개의 사칙연산 처리 방법과 파이썬 예제 무한히 큰 수를 다루는 것은 암호화, 금융 계산, 과학적 시뮬레이션 등 여러 분야에서 중요한 역할을 합니다. 하지만 단순히 큰 수의 사칙연산을 처리하는 것뿐만 아니라, 이러한 연산을 효율적으로 수행하는 알고리즘과 방법이 필요합니다. 이 글에서는 무한히 큰 수를 다루는 방법과 효율적인 사칙연산 알고리즘을 소개하고, 파이썬 예제 코드도 함께 살펴보겠습니다.1. 무한히 큰 수의 개념무한히 큰 수는 컴퓨터의 기본 데이터 타입으로 표현할 수 없는 크기의 숫자를 의미합니다. 컴퓨터에서는 메모리와 시간 복잡도 제한 때문에 무한히 큰 수를 다루기 위해서는 특별한 방법이 필요합니다. 특히, 단순한 연산 이상의 복잡한 알고리즘이 필요할 때가 많습니다.2. 무한히 큰 수의 사칙연산 처리무한히 큰 수의 사칙연산은 기본적인 덧.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2024. 8. 13.

• 

  그래프(Graph), 그리고 DFS와 BFS - 1. 그래프에 관하여 DFS와 BFS는 탐색 알고리즘의 한 종류이다. 이 알고리즘은 그래프를 알고 있어야 이해할 수 있는 알고리즘이다. 그래서 그래프부터 다루고자 한다. 그래프란 점(정점)과 선(간선)으로 이루어진 자료구조를 의미한다. 별개 아니다. 그냥 숫자(인덱스)가 붙은 점들과 그 점들 간의 관계를 선으로 표시한 것 뿐이다. 단순한 점과 선들의 조합인 그래프를 활용해 마크주커버그가 페이스북을 만들었다. 이 페이스북을 사례로 그래프를 설명할 것이다. 자고로 본인은 페이스북 안한지 100만년된 듯 싶다. 각 점을 사람으로 간주하고 각 선을 팔로우하여 관계를 표시하면 그것이 그래프다. 눈치 챈 사람도 있겠지만 A가 B를 팔로우하였다. B가 A를 맞팔로우하였다와 같이 (간)선들은 일종의 방향성을 가질 수 있다. 이와 같은 방향.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2022. 2. 22.