분류 전체보기

[Algorithm] 분할정복(1) - Master Theorem과 일반해

🤔 Divide And Conquer 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 포스트에서는 분할정복을 Master Theorem의 일반해를 구하는 방법을 자세하게 알아보겠습니다. 🔎 Master Theorem Master Theorem에서 Input Size가 $n$일때 분할정복 알고리즘의 일반적인 패턴은 아래와 같습니다. 상수 $a > 0, b > 1, d ≥ 0$에 대하여 1. 문제를 size가 $\frac{n}{b}$인 $a$개의 subproblem으로 나눈다. (recursivel..

[Algorithm] 알고리즘 기본(2) - Basic Arithmetic

🤔 Basic Arithmethic 덧셈, 뺄셈, 곱셈, 나눗셈 즉 기본연산(사칙연산)을 Basic Arithmethic이라고 합니다. n-bit를 가지고 있는 기본적인 bit 연산에 대해 알아보도록 하겠습니다. 이전에 모든 계산에 있어 단일 bit에 대해 기본적인 bit 연산에 $O(1)$시간이 소모된다고 가정하겠습니다. 🔎 두 n-bit 이진수의 덧셈 $53$과 $35$의 이진수인 "1 1 0 1 0 1"과 "1 0 0 0 1 1"을 예시로 더해보겠습니다. 위와 같이 6bit 연산에서 최상위 비트에서의 Carry가 발생하여 7bit가 결과값으로 출력되었습니다. 두 개의 n-bit 짜리 이진수가 주어졌을 때 n 번의 덧셈이 반복되면서 일어나는 것을 알 수 있습니다. 즉 두 n-bit 이진수의 덧셈의 시..

[TW] 2022-09-25

배드민턴 교류전을 잘 마무리하고 대회 준비를 했다. 👉 TODAY'S WORKS → 배드민텬 교류전 → 콜라톤 대회준비 → → 🔎 TOMORROW'S WORKS → 시스템 프로그래밍 정리 완료 → 알고리즘 복습 + 정리 끝내기 → 📃 POST → → →

[시스템 프로그래밍] 실수의 표현 및 처리

🤔 실수의 표현 및 처리 이전 포스팅에서는 정수의 표현 및 처리에 대해 공부했습니다. 이번에는 실수의 표현 및 처리에 대해 학습하겠습니다. 2진소수 , 인코딩, 정규화 등에 대해 배워보겠습니다. 🔎 2진 소수 이진 소수의 각 자리를 $a_k$라고 했을 때 아래와 같이 나타낼 수 있습니다. $$b_ib_{i-1} ... b_2b_1b_0.b_{-1}b_{-2} ... b_{-j}$$ 분수로 나타내어진 수를 2진 소수로 표시할 때 해당 분수의 분모가 2의 거듭제곱꼴로 나타난 경우 쉽게 이진 소수로 표시 할 수 있습니다. $$5와 3/4 = 101.11_2$$ $$63/64 = 0.111111_2$$ 하지만 모든 분수의 분모가 2의 거듭제곱꼴이 아니기 때문에 우리는 ɛ 기호를 통해 해당 값을 나타냅니다. 예를..

[시스템 프로그래밍] 정수의 표현 방법

🤔 정수의 표현 방법 컴퓨터에서는 정수를 어떤 방법으로 표현하는지 알아보도록 하겠습니다. 크게 부호가 없는 정수, BCD코드, 부호를 갖는 정수를 주로 알아보겠습니다. 결론부터 말하자면 컴퓨터는 2의 보수를 통해 부호형 정수를 표시하기로 정했습니다. 비부호형 수에서 2의 보수형 정수로 변환하는 것입니다. 쉽게말해 비트를 모두 뒤집고 1을 더하면 됩니다. 아래에서 조금 더 자세하게 알아보겠습니다. 🔎 정수의 인코딩 비부호형 정수와 부호형 정수는 간단하게 수식으로 나타낼 수 있습니다. 비부호형 정수는 $B2U(X)$라고도 하는데 아래와 같이 나타낼 수 있습니다. 부호형 정수(2의 보수)는 아래와 같이 나타낼 수 있습니다. 이를 통해 길이가 W비트인 정수의 표현 가능한 범위를 추측해볼 수 있습니다. 비부호형 ..