[알고리즘] 에라토스테네스의 체

에라토스테네스의 체 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 알고리즘이다. 원리 2 ~ N 까지의 배열을 초기화 합니다. 2는 소수이므로 2는 표시하고, 2의 배수들을 모두 지웁니다. 3도 소수이므로 3은 표시하고, 3의 배수들은 모두 지웁니다. 위 과정의 반복을 통해 지워지지 않은 수를 출력하면 소수를 구할 수 있습니다. 코드 두 수 a와 b를 입력 받은 뒤, a와 b 사이에 존재하는 모든 소수를 출력하는 코드 #include using namespace std; const int MAX = 1000001; int arr[MAX] = { 0, }; int a, b, result = 0; int main() { for (int i = 2; i > b; for (int..

[알고리즘] 유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법 2개의 자연수의 최대 공약수를 구하는 알고리즘의 하나이다. 정의: 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. [출처] : 위키피디아 - 유클리드 호제법 유클리드 호제법 코드 int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); } 유클리드 호제법을 사용해서 최대 공약수(GCD)구하기 두 수를 입력 받아서 최대 공약수(GCD) 출력하기 #include using namespace std; int a, b; int result; int gcd(int x, int y) { if (y == 0) return x;..

[자료구조] 덱 - Deque

덱이란? 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐(Queue)의 종료 덱의 연산 size() : 현재 큐에 들어있는 데이터 원소의 개수를 반환. empty() : 현재 큐가 비어있으면 true, 아닐 경우 false 반환. push_back(x) : 현재 큐의 맨 뒤에 데이터 x를 삽입. push_front(x) : 현재 큐의 맨 앞에 데이터 x를 삽입. pop_back() : 현재 큐의 맨 뒤에 있는 데이터 원소를 제거. pop_front() : 현재 큐의 맨 앞에 있는 데이터 원소를 제거. front() : 현재 큐의 가장 앞에 있는 데이터 원소를 반환. back() : 현재 큐의 가장 뒤에 있는 데이터 원소를 반환. 덱의 구현 #include using namespace std; const int..

[자료구조] 큐 - Queue

큐란? FIFO (First In First Out) 선입선출 특성을 가지는 자료구조 한 쪽으로 자료를 넣고 다른 쪽으로는 자료를 뺄 수 있다 큐의 연산 size() : 현재 큐에 들어있는 데이터 원소의 개수를 반환. empty() : 현재 큐가 비어있으면 true, 아닐 경우 false 반환. push(x) : 현재 큐의 맨 뒤에 데이터 x를 삽입. pop() : 현재 큐의 맨 앞에 있는 데이터 원소를 제거. front() : 현재 큐의 가장 앞에 있는 데이터 원소를 반환. back() : 현재 큐의 가장 뒤에 있는 데이터 원소를 반환. 큐의 구현 #include using namespace std; const int MAX = 1e5; class Queue { private: int data[MAX]..

[자료구조] 스택 - Stack

스택이란? LIFO (Last In First Out) 후입선출 특성을 가지는 자료구조 한 쪽 끝에서만 자료를 넣고 뺄 수 있다 스택의 연산 size() : 현재 스택에 들어있는 데이터 원소의 개수를 반환. empty() : 현재 스택이 비어있으면 true, 아닐 경우 false 반환. push(x) : 현재 스택에 데이터 x를 삽입. pop() : 현재 스택의 가장 위에 있는 데이터 원소를 제거. top() : 현재 스택의 가장 위에 있는 데이터 원소를 반환. 스택의 구현 #include using namespace std; const int MAX = 1e5; class Stack { private: int data[MAX]; int index; public: Stack(); int size(); b..

[알고리즘] 동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍이란? 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 하나의 문제를 단 한 번만 풀도록 하는 알고리즘 기법 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 피보나치수열 아래의 코드는 재귀를 사용해서 n-1번째 수를 구하는 코드입니다 int fibo(int n) { if (n == 0 || n == 1) return n; else return fibo(n-1) + fibo(n-2); } 위 코드를 사용해서 f(5)의 호출 과정을 그림으로 표현하면 아래와 같다 위의 사진을 보면 fibo(2) 함수가 3번 호출되어서 중복된 것을 확인할 수 있다 메모제이션 (Memoziation) 동적..

[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 고르는 알고리즘 기준에 따라 좋은 것을 선택하는 알고리즘 예시 문제 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 2021.12.20 - [알고리즘/백준] - [BOJ] 5585번 거스름돈 [BOJ] 5585번 거스름돈 문제 출처 백준 온라인 저지 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에..