궤도

문제 풀이 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

문제 풀이 문제 자체는 아주 쉬운 경우의 수 문제다. X, Y 종류의 의상이 있다고 하자. 각 종류별 의상은 이러하다. X - a, b Y - c X 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, a, b}이고, Y 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, c}이다. 둘다 입지 않을 수는 없으니 3x2-1=5가 선택할 수 있는 총 경우의 수이다. 입력을 잘 처리해서 정리하는게 거의 다인 문제인거다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; struct outfit { //옷 정보 저장 string name; string kind; }; struct kindCnt { //종류별 옷의 개..

문제 풀이 myunji.tistory.com/228 [백준] 11050번 : 이항 계수 1 문제 본문 설마 이항 계수를 모르는 사람이 이 글을 보진 않겠지...고등학교 때 배우는 그거다. nCk를 구하면 되는건데 다들 알다시피 공식은 n!/(k!(n-k)!)이다. 이걸 그대로 코드로 작성하면 된다. myunji.tistory.com 이걸 동적 계획법으로 푸는 문제이다. 아마 학교에서 이항 계수에 대해 배웠을 때 파스칼의 삼각형도 들어봤을 것이다. nCk = n-1Ck-1 + n-1Ck 라는 공식을 기억하고 있다면 어렵지 않다. 소스코드 #include using namespace std; int dp[1001][1001] = { 0, }; int binomial(int N, int K) { if (N /..