본문 바로가기

알고리즘67

[기초] 자료구조 / 스택(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.

티스토리툴바