Computer

[C++] value categories

https://en.cppreference.com/w/cpp/language/value_category Value categories - cppreference.com Each C++ expression (an operator with its operands, a literal, a variable name, etc.) is characterized by two independent properties: a type and a value category. Each expression has some non-reference type, and each expression belongs to exactly one of th en.cppreference.com C++의 value는 크게 glvalue와 rva..

[C++] rvalue 참조와 move semantics

안녕하세요, katte입니다. 이번 글에서는 드디어 미루고 미루던 rvalue 참조와 move semantics에 대해 정리해보려고 합니다. 원래 나중에 하려고 계속 미루고 있었는데 이 내용을 알아야 이해할 수 있는 내용이 자꾸 나오길래 그냥 빨리 정리해버리기로 했습니다ㅎㅎ.. rvalue는 우측값, 즉 대입 연산에서 오른쪽에 오는 값으로, 주소를 얻어내기 위해 주소 연산자&를 사용할 수 없는 값을 의미합니다. 예를 들자면 리터럴 상수(C스타일 문자열은 포함X), 레퍼런스가 아닌 함수의 리턴값, x+y와 같은 expression이 있습니다. 반대로 lvalue는 주소를 얻어내기 위해 주소 연산자를 사용할 수 있는 값이며, 이름이 있는 대부분의 객체가 포함됩니다. 가장 흔하게는 변수가 있을 것입니다. 우리..

[백준][C++] 2738 행렬 덧셈

https://www.acmicpc.net/problem/2738 2738번: 행렬 덧셈 첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같 www.acmicpc.net 2차원 배열을 이용하는 문제이다. n과 m의 범위가 100 이하이므로 굳이 동적할당을 할 필요는 없지만 연습을 위해 동적할당을 써 보았다. 2차원 배열은 배열의 배열로 이해할 수 있다는 점을 이용하여 구현할 수 있다. 즉 포인터 배열을 만들고, 각각의 원소들이 또 다른 배열을 가리키도록 하여 구현할 수 있다. (물론 실제 2차원 배열의 메모리는 연속된 주소 값을 갖기 때문에 이렇게 ..

[백준] [C++] 11729 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 재귀를 이용하는 문제다. 단계별 풀기를 하고 있는데, 아직 이 문제를 풀 순서는 아니지만 재귀 배운 김에 풀어봤다. 이 문제의 핵심 포인트는 다음과 같다. n개의 원반을 A에서 C로 옮기기 위해서는 n-1개의 원반을 A에서 B로 옮기고, 가장 밑의 원반을 A에서 C로 옮긴 후, 다시 n-1개의 원반을 B에서 C로 옮겨야 한다. 따라서 재귀로 귀결되는 것이다. 사실 이 문제는 너무 유명..

[알고리즘] 시간복잡도와 공간복잡도, 빅-오(Big-Oh) 표기법

안녕하세요, katte입니다. 이번 글에서는 알고리즘을 평가하는 기준인 시간복잡도와 공간복잡도, 그리고 시간복잡도를 나타내기 위한 방법인 빅-오 표기법에 대해 알아보도록 하겠습니다. 알고리즘을 평가하는 기준으로는 시간복잡도와 공간복잡도 두 가지가 있습니다. 시간복잡도: 어떤 알고리즘이 어떠한 상황에서 더 빠르고 더 느린가? 연산 횟수와 관련 공간복잡도: 어떤 알고리즘이 어떠한 상황에서 더 메모리를 적게 사용하고 많이 사용하는가? 일반적으로는 공간복잡도보다 시간복잡도를 더 우선시합니다. 시간복잡도의 경우에는 데이터 양에 따른 연산 횟수와 관련이 있습니다. 즉, 데이터의 양이 n일 때, 연산횟수 T(n)이 어떤 형태를 띄는가에 관심을 둡니다. 이때 중요한 것은, 데이터 양 n이 증가함에 따라 T(n)이 어느..

[백준] [C++] 9020 골드바흐의 추측

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 두 가지 방법으로 풀었다. 첫 번째 방법은 숫자 n을 받아서 2로 나눈 후 단순하게 소수 판별을 하고, 소수가 아니라면 증감을 시키는 방법을 사용하였다. //개별 수에 대해서 소수 판별을 하는 방법 #include bool prime(int n) //소수 판별 함수 { for (int i = 2; i * i > loop; while (loop--) { int n; std::ci..

[백준] [C++] 4948 베르트랑 공준

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 이 문제는 1929번 문제와 크게 다르지 않다. 범위만 n~2n으로 바뀌었을 뿐 1929번 풀 때는 삽질을 엄청나게 했는데, 1929 풀고 나니 이 문제는 쉽게 풀렸다 https://katteniiki.tistory.com/23 [백준] [C++] 1929 소수 구하기, 에라토스테네스의 체 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에..

[백준] [C++] 1929 소수 구하기, 에라토스테네스의 체

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 처음에는 그냥 무작정 짝수 거르고 루프 돌렸더니 시간초과 뜸 그래서 찾아봤더니 '에라토스테네스의 체'라는 것이 있다카더라 에라토스테네스의 체는 특정 범위가 주어졌을 때 그 범위 내의 소수들을 판별할 수 있는 방법이다. 마치 체로 거르듯 소수들의 배수를 지워나가다보면 남는 것은 소수임을 이용한다. 2부터 수들을 나열한 다음, 2는 소수이므로 남겨두고 2의 배수들을 지운다. 3 역시 소수이므로 남겨두고 3의 배수를 지운다. 이런 방..