분류 전체보기

[알고리즘] 시간복잡도와 공간복잡도, 빅-오(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의 배수를 지운다. 이런 방..

[백준] [C++] 11653 소인수분해

1일 1백준 시작 C++ 배우느라 미뤄뒀던 백준 다시 시작하기로 함 현재 티어 실버5 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net #include int main() { int num; std::cin >> num; if (num == 1) return 0; for (int i = 2; i

[C++] 함수 포인터 정리

안녕하세요, katte입니다. 이번 글에서는 함수 포인터와 함수 포인터 배열, 함수 포인터 배열의 포인터(...)에 대해 다뤄보겠습니다. 배열 포인터에 관해서는 아래의 글을 참고해주세요. https://katteniiki.tistory.com/19 [C++] 배열 포인터 정리 안녕하세요, katte입니다. 이번 글에서는 배열 포인터에 대해서 간단하게 정리해 보도록 하겠습니다. 배열 포인터는 비슷한 이름 탓에 포인터 배열과 혼동될 수 있지만, 전혀 다른 개념입니다. 포 katteniiki.tistory.com 포인터는 C나 C++의 문법을 보기 껄끄럽게 만드는 요소중 하나입니다. 특히 함수 포인터와 배열 포인터로 여러 차례 꼬인 경우 한눈에 자료형을 파악하기 힘들죠. 물론 이런 경우를 위해 auto라는 키..

[C++] 배열 포인터 정리

안녕하세요, katte입니다. 이번 글에서는 배열 포인터에 대해서 간단하게 정리해 보도록 하겠습니다. 배열 포인터는 비슷한 이름 탓에 포인터 배열과 혼동될 수 있지만, 전혀 다른 개념입니다. 포인터 배열은 말 그대로 배열 각각의 원소가 포인터형인 것을 의미합니다. 다음과 같이 선언하고 사용할 수 있습니다. int a = 2, b = 3, c = 4; int* arr[3] = { &a, &b, &c }; //arr 각각의 원소가 포인터 std::cout

[C++] cout 관련(3) - 출력 형식 지정

안녕하세요, katte입니다. 이번 글에서는 cout의 출력 형식을 지정하는 방법에 대해 알아보겠습니다. 출력 형식은 setf 함수를 통해서도 변경할 수 있지만, 조정자나 다른 간편한 함수를 사용할 수 있는 경우에는 해당 방식을 사용하는 것이 더 간편하니 최대한 활용할 수 있는 만큼 활용하는 것이 좋습니다. 따라서 setf에 대해서는 다음 글에서 알아보도록 하고, 이번 글에서는 출력 형식을 지정할 수 있는 몇가지 조정자와 함수에 대해서 알아보겠습니다. ios_base 클래스는 출력 형식을 관장하는 비트마스크 멤버들을 가지고 있습니다. 이러한 비트들은 조정자 혹은 ios_base의 멤버함수를 사용하여 제어할 수 있습니다. 1) 진법 진법은 setf 함수를 통해 제어할 수 있지만, 좀 더 간편한 방식인 조정..