궤도

문제 풀이 이중 for문을 쓰면 아주 쉬운데...시간제한때문에 시간복잡도를 줄여야한다. 이 문제를 푸는 아이디어는 오큰수를 구하지 못한 수를 스택에 저장하는 것이다. 더 자세하게 말하자면 오큰수를 구하지 못한 수의 인덱스를 스택에 저장하면 되겠다. 오큰수를 구하지 못한 수(A)를 스택에 저장하고, 그 뒤로 입력되는 수(B)에 대해 B가 A의 오큰수가 될 수 있는지 확인한다. 될 수 있다면 배열의 A 인덱스 값을 B로 바꿔준다. 마지막까지 스택에 남아있는 수는 오큰수를 구하지 못한 것이므로 -1로 바꿔준다. 소스코드 #include #include using namespace std; int num_arr[1000000]; void oaken(int length) { stack index; //오큰수를 구..

문제 풀이 스택과 만들어야할 수열이다. 스택에는 1~8까지 순서대로 들어올 것이다. 1 2 3 4를 순서대로 스택에 쌓다보니 수열의 첫번째 숫자인 4를 만났다. pop 해주자. 마침 그 다음이 3이니 한번 더 pop해주자. 다시 5부터 push하자. 6을 만나서 pop했다. 입력 예제 2번은 직접 해보시길 1 2 5까지만 만들어질 것이다. 소스코드 #include #include #include using namespace std; void isStack(vector arr) { int index = 1; stack s; vector pm; for (int i = 0; i < arr.size(); i++) { while (index input; arr.push_back(input); } isStack(a..

문제 풀이 myunji.tistory.com/236 [백준] 9012번 : 괄호 문제 풀이 스택 문제에는 나혼자 정했지만 아마 일반화도 가능할 듯한 네임드 문제 2개가 있다. 후위표기법 사칙연산과 괄호 맞추기다. 유명한 문제들이니만큼 풀이법도 세뇌수준으로 들어서 myunji.tistory.com 이 문제의 응용판이다. 사실 이 문제에서 제일 어려운건 입력을 처리하는 것이다. 괄호야 뭐...왼쪽 괄호 나오면 스택에 쌓고 오른쪽 괄호 나오면 짝 맞는지 확인해서 pop하면 그만이다. 그럼 띄어쓰기가 있는 입력을 어떻게 처리할지 살펴보자. 소스코드 #include #include #include using namespace std; void bracket(string input, int length) { sta..

문제 풀이 스택 문제에는 나혼자 정했지만 아마 일반화도 가능할 듯한 네임드 문제 2개가 있다. 후위표기법 사칙연산과 괄호 맞추기다. 유명한 문제들이니만큼 풀이법도 세뇌수준으로 들어서 툭 건드리면 툭 나올만큼 외웠다. 왼쪽 괄호가 나오면 스택에 넣고(push) 오른쪽 괄호가 나오면 pop하는데 pop을 하려할 때 이미 스택이 비어있거나, 문자열의 끝까지 탐색을 완료했는데 스택이 비어있지 않으면 올바른 괄호 문자열이 아니다. 자세한 설명을 원한다면...나보다 훨씬 잘 설명한 블로그가 정말 많다. 그만큼 유명한 문제라는 것이다. 소스코드 #include #include #include using namespace std; void bracket(string input, int length) { stack s;..

문제 풀이 입력을 계속 스택에 push로 쌓다가 0을 만나면 pop해주면 되겠다. 입력이 끝나면 스택에 남아있는 모든 수를 더해주자. 소스코드 #include #include using namespace std; int main() { int K, input, sum = 0; stack s; cin >> K; for (int i = 0; i > input; if (input == 0) //0이면 가장 위에 있던 수 pop으로 뺌 s.pop(); else s.push(input); } while (!s.empty()) { //스택에 쌓인 모든 수 더해줌 sum += s.top(); s.pop(); } cout

문제 본문 과거 자료구조 수업시간에 C로 스택을 하나하나 정성스레 구현하던 때가 떠오른다. 그때 C++을 잘 모르던 때인데 다행이라고 생각한다. 만약 알고 있었다면 한줄로 해결할 수 있는걸 하나하나 작성하느라 홧병이 나서 죽었을 테니까... C++의 표준 템플릿 라이브러리(STL)중에는 스택이 있다. 그전에 스택이 뭔지 모를 수 있으니 간략히 설명하면 LIFO(Last In First Out) 형식의 자료구조이다. 이 문제는 스택의 기본 사용법을 배우는 그런 문제라고 볼 수 있겠다. www.cplusplus.com/reference/stack/stack/?kw=stack stack - C++ Reference container_typeThe second template parameter (Containe..

문제 풀이 myunji.tistory.com/231?category=1154147 [백준] 1676번 : 팩토리얼 0의 개수 문제 풀이 저 문제 기준으로 10은 1이다. 100은 2고, 1000은 3이다. 즉 해당 팩토리얼을 계산했을 때 10이 몇번이나 곱해졌는지 세어보면 답이 나올 것이다. 10=2x5다. 그니까 팩토리얼을 계산했을 때 myunji.tistory.com 이 문제의 풀이를 거의 그대로 사용할 것이다. nCm = n!/(m!(n-m)!)이다. 그니까 n!과 m!, 그리고 (n-m)!의 2와 5의 수를 각각 구한 뒤, 나눗셈 곱셈을 잘 고려해 계산하면 되겠다. 소스코드 #include #include using namespace std; pair binomial(long long n) { i..

문제 풀이 저 문제 기준으로 10은 1이다. 100은 2고, 1000은 3이다. 즉 해당 팩토리얼을 계산했을 때 10이 몇번이나 곱해졌는지 세어보면 답이 나올 것이다. 10=2x5다. 그니까 팩토리얼을 계산했을 때 곱해진 2의 수와 5의 수를 각각 구해 그 중 작은 것을 택하면 된다. 소스코드 #include #include using namespace std; int fact(int N) { int two_cnt = 0, five_cnt = 0; for (int i = 2; i N; cout