본문 바로가기

전체보기

 (448)
[448] 약수 학습하기 1. 개념 소개여러분, 약수라는 말을 들어본 적이 있나요? 약수란 어떤 수를 나누어떨어지게 만드는 숫자입니다. 쉽게 말하면, 어떤 수를 나누었을 때 나머지가 0이 되면, 그 숫자는 약수라고 할 수 있습니다. 예를 들어, 12라는 숫자를 생각해 보겠습니다. • 1로 나누면 12 ÷ 1 = 12 (나머지 0, 약수입니다!) • 2로 나누면 12 ÷ 2 = 6 (나머지 0, 약수입니다!) • 3로 나누면 12 ÷ 3 = 4 (나머지 0, 약수입니다!) • 4로 나누면 12 ÷ 4 = 3 (나머지 0, 약수입니다!) 이렇게 12를 나누었을 때 나머지가 0이 되는 숫자들은 모두 12의 약수입니다.2. 실생활 예제 약수는 우리 일상에서도 쉽게 찾아볼 수 있습니다. 예를 들어, 초콜릿 12개가 들어 있는 상자가 있다..
[447] 메르센 수, 메르센 소수 1. 메르센 수\(2^n-1\) 의 꼴의 수를 메르센 수라고 합니다.메르센 수를 이진수로 나타내면 모든 자리가 1인 수입니다.2. 하노이의 탑\(n\)층의 하노이의 탑을 옮기는 횟수를 \(f(n)\)이라고 했을 때, 1층인 하노이의 탑을 옮기는 것은 1회이므로  \(f(1) = 1\)입니다.\(n\)층의 하노이의 탑을 옮기려면 다음과 같은 과정을 거칩니다.맨 밑의 한 개를 제외하고 \(n-1\)층을 일단 옮겨놓습니다. (\(f(n-1)\))맨 밑의 한 개를 옮깁니다. (\(f(1)\))다시 그 위에 \(n-1\)층을 옮겨놓으면 됩니다. (\(f(n-1)\))이 식을 정리하면 다음과 같습니다.\[\begin{aligned}f(n) &= f(n-1) \times 2 + 1 \\     &= \big(f(n-..
[446] 느리게 갱신되는 세그먼트 트리(lazy propagation) 1. 세그먼트 트리 동작 과정세그먼트 트리는 루트 노드에서 리프 노드까지 범위를 나누어 가며 통일된 연산값을 유지해야 합니다.따라서 자식 노드에서 부모 노드로 올라가더라도 더 넓어진 범위에 대해 연산 결과를 유지할 수 있어야합니다.이게 가능한 연산은 최대, 최소, 덧셈, 곱셈 등 일부의 결과로 전체 범위에 적용이 가능한 연산을 세그먼트 트리에 적용할 수 있습니다. 8 크기의 배열에서 3, 2, 5, 3, 5, 2, 3, 4의 값을 가지고 있고, 구간합을 관리하는 세그먼트 트리는 다음과 같습니다. 이 세그먼트 트리에서 2 ~ 8 범위의 구간합을 구하고 싶다면 다음과 같이 구합니다. 찾고자 하는 범위 안에 포함될 때까지 자식으로 내려가며 합을 구하면, 2+8+14로 24라는 것을 알 수 있습니다.다음으로 세..
[445] 다익스트라 알고리즘으로 최단경로의 모든 정점 찾기 1. 다익스트라 알고리즘다익스트라 알고리즘을 순서대로 나타내면 다음과 같습니다.단순한 최단경로 찾기는 위와 같이 풀 수 있습니다.하지만 최단경로 상의 모든 정점을 찾고 싶을 때는 위의 과정 중에 추가적인 알고리즘이 필요합니다.2. 다익스트라 알고리즘으로 최단경로의 정점 찾기우선순위 큐에 다음 정점에 대한 정보를 추가할 때, 가중치를 더 작은 값으로 하는 간선 정보를 저장합니다.최단경로 탐색이 종료되면, 간선 정보를 담은 표를 가지고 역으로 거슬러 올라가며 최단경로 상의 모든 정점을 순서대로 확인할 수 있습니다.
[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..

티스토리툴바