본문 바로가기

알고리즘70

C++ 백준 BOJ 10870 피보나치 수 5 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하는 문제입니다. 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include using namespace std; int fibo(int num) { int result = num; if (result == 0) { return 0; } else if (result == 1) { return 1; } else { return fibo(result - 1) + fibo(result - 2); } } int .. 2022. 7. 27.
[기초] 다이나믹 프로그래밍(Dynamic Programming, DP) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 동적 계획법이라고도 합니다. 동적 계획법 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 아래 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있습니다. 1. Overlapping Subproblem : 겹치는 부분 문제 2. Optimal Substructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 Overlapping Subproblem 겹치는 작은 부분 문제로 나눠서 푸는 것이 핵심입니다. 문제 작은 문제 - 작은 문제 (두 작은 문제가 겹쳐야 됨) 먼저 피보나치 수를 예시로 들어 알아보면, - 피보나치 수 - F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2.. 2022. 7. 27.
[기초] 자료구조 / 큐(queue)와 덱(deque), 문자열 큐(queue) 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 합니다. - push : 큐에 자료를 넣는 연산 - pop : 큐에서 자료를 빼는 연산 - front : 큐의 가장 앞에 있는 자료를 보는 연산 - back : 큐의 가장 뒤에 있는 자료를 보는 연산 - empty : 큐가 비어있는지 아닌지를 알아보는 연산 - size : 큐에 저장되어있는 자료의 개수를 알아보는 연산 그림에서 빨간색 1번이 front로 가장 앞에 있는 자료이고 빨간색 3번이 back으로 가장 뒤에 있는 자료입니다. 큐도 스택과 같이 이미 구현된 라이브러리를 사용할 수있습니다. C++의 경우 STL의 queue .. 2022. 7. 26.
[기초] 자료구조 / 스택(stack) 스택(stack) 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO) 라고도 합니다. - push : 스택에 자료를 넣는 연산 - pop : 스택에서 자료를 빼는 연산 - top : 스택의 가장 위에 있는 자료를 보는 연산 - empty : 스택이 비어있는지 아닌지를 알아보는 연산 - size : 스택에 저장되어있는 자료의 개수를 알아보는 연산 그림에서 top은 6이고 4가 push 되면 top은 4가 됩니다. 빨간색 숫자가 자료가 들어온 순서를 나타냅니다. 스택은 이미 구현된 라이브러리를 사용할 수있습니다. C++의 경우 STL의 stack JAVA의 경우 java.util.Stack 직접 구현할 경우 배열을 이용해.. 2022. 7. 26.
C++ 백준 BOJ 9012 괄호 입력받은 문자열이 바르게 구성된 괄호 문자열(VPS)인지 판단하는 문제입니다. 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net #include #include using namespace std; void checkVPS(string p){ stack checkP; for(int i = 0; i < p.size(); i++){ if(p[i]=='('){ checkP.push('('); } else{ if(checkP.empty()){ checkP.push(')'); } else .. 2022. 7. 25.
[기초] 알고리즘과 입출력 (+시간 복잡도) 알고리즘이란? 어떠한 문제를 해결하기 위한 여러 동작들의 모임, 절차입니다. 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 ko.wikipedia.org '시간 복잡도' 시간 복잡도를 이용하면 작성한 코드가 시간이 얼마나 걸릴지 예상할 수 있다. 표기법으로 대문자 O를 사용한다. 영어로는 Big O Notation 입력의 크기에 대해서 시간이 얼마나 걸릴지 나타내는 방법 최악의 경우에 시간이 얼마나 걸릴지 나타내야한다. 만약 1부터 N까지의 합을 계산하면, 시간 복잡도: O(N) int sum = 0; for.. 2022. 7. 25.
C++ 백준 BOJ 2960 에라토스테네스의 체 에라토스테네스의 체는 소수를 찾는 유명한 알고리즘입니다. 에라토스테네스의 체 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 아주 큰 범위에서 소수를 판별하는 문제는 코딩테스트에서도 자주 나오는 문제인데 이때 사용하는 알고리즘입니다. 1929번 소수 구하기 문제를 풀기 전 먼저 알아야 합니다. 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net #include using namespace std; bool arr[1001]; int main() { int N, K, val = 0, count = 0; //count 는 k번째 수를 판별 for (int i = 0;.. 2022. 4. 30.

티스토리툴바