본문 바로가기

전체보기

 (460)
[444] 부동소수점의 오차 이야기 1. 부동소수점(浮動小數点)부동소수점 방식은 고정소수점 방식과 함께 컴퓨터로 소수(小數)를 나타내기 위한 방법입니다.부동소수점의 부는 不(아닐 부)가 아니라 浮(뜰 부)입니다.고정되어 있지 않고 움직인다는 뜻입니다.부동자세에서 부동은 움직이지 않는다는 뜻인데, 부동소수점의 부동은 움직인다는 뜻입니다.(연패처럼...) 십진수 \(14.2\)를 \(1.42 \times 10^1\) 처럼 나타내는 방식입니다.같은 방식으로 이진수 \(101.01\)를 부동소수점 방식으로 나타내면 \(1.0101 \times 2^2\)  입니다.https://ko.wikipedia.org/wiki/부동소수점 부동소수점 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 초기의 전기기계식 프로그래밍 가능한 컴퓨터..
[443] 순열, 조합, 중복순열, 중복조합 구현하기(파이썬 코드) - itertools 없이 1. 순열arr = [1, 2, 3]used = [False] * len(arr)def perm(arr, r): for i in range(len(arr)): if not used[i]: used[i] = True if r == 1: yield [arr[i]] else: for nxt in perm(arr, r-1): yield [arr[i]] + nxt used[i] = False print(*perm(arr, 3), sep="\n")# [1, 2, 3]# [1, 3, 2]# [2, 1, 3]# [2,..
[442] 백준 1979번 - 극적인 곱셈 1.  문제https://www.acmicpc.net/problem/19792. 문제 이해n, k 가 주어졌을 때, 위 그림과 같이 k로 끝나는 어떤 수에 n을 곱한 결과가 그 어떤 수를 오른쪽으로 한 칸씩만 옮겨진 수와 같은 결과가 되도록 하는 어떤 수를 구하는 문제입니다.3. 해결 방법찾고자 하는 수의 일의 자리 숫자는 무조건 k입니다.따라서 n을 곱한 값의 일의 자리 숫자는 (k*n)%10이고, 구하고자 하는 어떤 수의 십의 자리도 (k*n)%10이 됩니다.이제 구한 수를 a라고 하면 n을 곱한 값의 십의 자리 숫자는 (a*n)%10 에 (k*n)//10을 더한 값이 됩니다.그리고 그 수는 구하고자 하는 수의 백의 자리 값이 됩니다.이제는 이 과정을, 곱한 값에 다시 k가 나올 때까지 반복합니다.4..
[441] PS에서 C++의 빠른 입출력 방법 빠른 입출력 코드// 1#include using namespace std; // 2int main() { ios_base::sync_with_stdio(false); // 3 (중요) cin.tie(nullptr); // 4 (중요) int a, b; cin >> a >> b; cout 1. #include C++에서 #을 사용하는 키워드를 전처리기 지시문(Preprocessor Directives)이라고 합니다.전처리기 지시문은 컴파일 되기 전에 수행할 작업들을 정의합니다.#include는 파이썬의 import와 같은 역할을 합니다.그리고 파이썬에서 import의 대상을 모듈이라고 했던 것과 비슷하게, C++에서는 #include의 대상을 헤더파일이라고 합니다. iostre..
[440] 조합(combination) 큰 수 계산하기(모듈러) - 파이썬 1. 조합 계산 코드(파이썬)n = 1000000r = 500000MOD = 1000000007facto = [1]*(n+1)inv_facto = [1]*(n+1)for i in range(2, n+1): facto[i] = facto[i-1] * i % MODinv_facto[n] = pow(facto[n], MOD-2, MOD) # 페르마의 소정리for i in range(n-1, -1, -1): inv_facto[i] = inv_facto[i+1] * (i+1) % MODdef nCr(n, r): return facto[n] * inv_facto[r] % MOD * inv_facto[n-r] % MODprint(nCr(5, 3))# 10print(nCr(10, 4))# 210prin..
[439] 모듈러 연산의 나눗셈(확장 유클리드 알고리즘, 페르마 소정리) 1. 모듈러 연산의 기초예전에  모듈러 연산과 관련된 포스팅을 올린 적이 있습니다.모듈러 연산의 분배 법칙을 알아보았지만, 나눗셈의 분배 법칙은 키워드 정도만 안내하고 넘어갔습니다.\((a+b) \text{ mod } c  = \big((a \text{ mod }{c}) + (b \text{ mod }{c})\big) \text{ mod }{c} \)\((a-b) \text{ mod }{ c } = \big((a \text{ mod }{c}) - (b \text{ mod }{c})\big) \text{ mod }{c} \)\((a \times b) \text{ mod }{ c } = \big((a \text{ mod }{c}) \times (b \text{ mod }{c})\big) \text{ mod ..
[438] 팰린드롬 부분 문자열(Manacher's algorithm)(파이썬 코드) 1. Manacher's algorithm우리말로는 마나커, 마나허, 매내처 등으로 불리는 알고리즘입니다.어떤 문자열에서 팰린드롬인 모든 부분 문자열을 \(\mathbf{O(n)}\)만에 찾을 수 있는 알고리즘입니다.코드는 다음과 같습니다.def manacher(S: str): S = "*"+ "".join([c+"*" for c in S]) length = len(S) radius = [0] * length old_center = 0 old_radius = 0 for center in range(length): if old_center+old_radius = 0 and \ center+radius[center]+1 2. 동작 원리먼저 팰린..
[437] 팰린드롬 판별 & 부분 문자열 중 팰린드롬 찾기 1. 팰린드롬?팰린드롬(palindrome)은 우리말로 회문(回文)이라고도 합니다.거꾸로 읽어도 바르게 읽은 것과 같은 문장이나 단어를 뜻합니다.팰린드롬과 관련된 다양한 알고리즘을 알아봅시다.2. 팰린드롬 판별하기(문자열 비교)문자열을 거꾸로 만들어 원래의 문자열과 비교합니다.단순하고 직관적인 방법입니다.파이썬으로 문자열을 거꾸로 만들 때는 slicing의 step을 -1로 사용하면 쉽습니다.def is_palin(S): if S == S[::-1]: return True return Falseprint(is_palin("abcda"))# Falseprint(is_palin("abcba"))# True 조금 더 생각해보면 굳이 문자열 전체를 비교할 필요가 없다는 것을 알 수 있습니..

티스토리툴바