1. 스택 구현
https://www.acmicpc.net/problem/10828
구현
- 그냥 큰 배열 선언해두고, if문으로 명령어를 분류한다.
문제점
1. cout << stack[a--]; 이런 혼합식이 제대로 적용되지 않는다.(현재 VS에서 안된다)
따라서 a-1을 출력하고서, a--를 진행했다.
- OutOfBounds
명령어의 개수를 잘못 보았다.
1000개가 아니라 10000개라서, 배열의 크기를 1만개로 주어야했다.
2. 단어 뒤집기
getline
https://www.acmicpc.net/problem/9093
#include <iostream>
#include <stack>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
cin.ignore(); // 중요
//getline(cin, s);
string s;
stack<char> st;
while(T--)
{
getline(cin, s);
s+= " ";
for(int i=0; i<s.length();i++)
{
if(s[i] == ' ')
{
while(!st.empty())
{
cout << st.top();
st.pop();
}
cout << ' ';
}
else
{
st.push(s[i]);
}
}
cout << "\n";
}
return 0;
}구현
- 한 줄 입력을 받고, 그 한줄을 iterator하면서 stack에 넣는다.
- ' '를 발견하면, stack의 모든 글자를 그대로 출력한다.
(= 따라서 거꾸로 됨)
문제점
1. 1줄 입력
입력을 1줄씩 받아야 하는 경우, getline으로 받아야한다.
2. getline
getline으로 받는 경우, 이전에 cin이 있다면,
무조건 cin.ignore를 해주어야 한다.
cin을 하고 값을 받은 뒤, \n라는 값은 아직 받지 않은 상태가 되어서,
getline이 해당 값을 읽을 수 있다고 한다.
3. 괄호 파악
https://www.acmicpc.net/problem/9012
구현
- s[i]가 ( 인지 ) 인지에따라 push하고 pop한다.
- empty인데 pop을 해야한다면, stack에 아무거나 넣고 break한다.
- 최종적으로 stack이 비지 않았다면, NO 출력,
문제점
1. break가 아니라 for문 내에 return을 썼었다 = 오류
4. 스택 수열
https://www.acmicpc.net/problem/1874
우선 문제 자체가 설명이 제대로 되어있지 않다.
구현
- queue에 만들고자하는 수열을 저장한다.
- stack에서는 inp라는 값이 queue의 front보다 작다면,
front만큼 stack에 수를 쌓는다.- front와 stack의 top이 같다면, queue와 stack을 pop한다.
- 그 결과들은 ans라는 queue에 저장해둔다.
왜냐하면 중간에 수열을 만들 수 없어서 NO 가 발생하는 경우,
다른 결과들은 출력하지 않아야하므로.
문제점
1. ans를 구현하지 않았었다.
따라서 출력초과가 났었다.
5. 에디터 마우스 커서
https://www.acmicpc.net/problem/1406
구현
- 배열로 풀기에 상당히 힘든 문제
- 하지만 커서를 기준으로 left, right라는 2개의 스택을 두면 쉬워진다.
문제점
- stack을 2개 사용하는 생각을 했다면 상당히 쉽다.
6. 큐 구현
구현
- 구현문제는 역시 명령어 개수에 맞는 배열로 생성한다.
- front와 back의 idx를 두면 쉽게 풀림
문제점
- 함수로 구현하지 않아서 return을 썼다가 틀렸다.
while문 내이므로 continue 사용.
7. 요새푸스
https://www.acmicpc.net/problem/1158
구현
- 원형을 구현하기 위해, 큐의 앞을 큐의 뒤로 다시 push하는 행위를 한다.
- count하여 k값이 맞다면, result큐에 push하고 pop한다.
문제점
- 큐를 사용할 생각을 했다면, 일단 쉽다.
8. 덱 구현
https://www.acmicpc.net/problem/10866
구현
- 역시 배열을 둠. 하지만 다른점은, 크기를 3배 크게 둠.
그 이유는, 앞에서도 추가될 수 있기 때문.- 그리고 중간 인덱스 값을 front, back의 인덱스 초기값으로 둠
- 그러면 쉽게 풀림
문제점
- 없
9. 단어 뒤집기 < > 태그
https://www.acmicpc.net/problem/17413
구현
- < 괄호가 생기면 플래그를 참으로 하고 그대로 답에 넣는다.
- 플래그가 거짓이라면, stack에 넣고 단어를 반대로 돌려서 답에 넣는다.
문제점
1. 입력의 마지막에 " "를 추가할지, 아니면 i 자체가 length-1인 것으로 할지
고민을 했는데,
length-1이 더 깔끔하다고 생각한다. " " 까지 문자로 오인할 수 있어서
2. 반례들을 고민했어야 했다.
10. 오큰수
https://www.acmicpc.net/problem/17298
구현
- 입력배열1개, 정답배열1개, stack을 둔다.
- 역순으로 진행하며, 입력배열과 stack의 top을 비교한다.
- stack의 top은 항상 현재 입력배열의 원소보다 큰 수만 남도록 pop한다.
문제점
1. stack을 써야할 것 같다는 생각은 했는데, 어떻게 써야할지 생각이 나지 않았다.
2. 결국 풀이를 보았고, 이해했다.
#include <iostream>
#include <stack>
using namespace std;
int N;
stack<int> s;
int ans[1000001]; // 오큰수
int seq[1000001]; // 그냥 입력
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
// 입력
for (int i = 0; i < N; i++)
{
cin >> seq[i];
}
for (int i = N - 1; i >= 0; i--)
{
// 1 사전작업 (이게 가장 중요)
while (!s.empty() && s.top() <= seq[i])
{
s.pop(); // seq[i]보다 항상 큰 s.top이 남을 수 밖에 없다.
// 이게 자신의 가장 첫번째 오큰수가 될 수 있는 이유는, stack때문
}
// 2 s.top을 ans[i]로 둔다.
if (s.empty())
{
ans[i] = -1;
}
else
{
ans[i] = s.top();
}
// 3 현재 원소를 넣는다 (어짜피 1에서 걸러짐)
s.push(seq[i]);
}
// 정답 출력
for (int i = 0; i < N; i++)
cout << ans[i] << " ";
}11. 오등큰수
https://www.acmicpc.net/problem/17299
구현
- 위의 문제에서 count 배열을 하나 더 생성하면 끝.
문제점
1. 아래처럼 작성해야만 한다. < 라고 적었었다.while (!s.empty() && count[s.top()] <= count[seq[i]]) { s.pop(); }
- 이 문제를 어떻게 푸는지 하나의 카테고리로서
알아두는 것이 좋아보인다.
stack을 부수적으로 사용하면서도 핵심 알고리즘에 적절히 사용되어,
다른 곳에도 응용하기 좋은 문제로 보인다.
12. 후위 표기식
https://www.acmicpc.net/problem/1935
구현
- 후위표기식 자체가 stack과 매우 친숙하다.
- 기호가 나오면, 기호 앞 2개의 숫자를 연산만 하면 된다.
문제점
1. stack에서 숫자를 빼내올 때, 연산 순서에 주의.
2. 고정된 소수점을 cout에서 표현하는 것은 상당히 어렵다.
일단 시도는 해봤는데 그냥 ios::sync_with_stdio(0);를 지운다.
3. float는 왠만해서 쓰지 말자. double이 범위도 크고 더 정확하다.
float에서 double로 바꾸니 바로 해결되었다.
4. 그리고 getline을 사용해보았는데 무조건 cin.ignore이다.
cin.clear 절대 아니다
#include <iostream>
#include <stack>
#include <iomanip> // 이걸 추가해야만 소수점 지정 가능
using namespace std;
int value[26] = {
0,
};
int main()
{
ios::sync_with_stdio(0); // 이걸 지우면 printf scanf를 사용할 수 있다.
cin.tie(0);
int N;
cin >> N;
cin.ignore();
string s;
getline(cin, s);
for (int i = 0; i < N; i++)
{
cin >> value[i];
}
stack<double> st;
float ans;
for (int i = 0; i < s.length(); i++)
{
// alpha
if (65 <= s[i] - 0 && s[i] - 0 <= 92)
{
st.push(value[s[i] - 65]);
}
else
{
double b = st.top();
st.pop();
double a = st.top();
st.pop();
if (s[i] == '+')
{
//cout << "+ : "<< a+b << "\n";
st.push(a + b);
}
else if (s[i] == '-')
{
//cout << "- : "<< a-b << "\n";
st.push(a-b);
}
else if (s[i] == '*')
{
//cout << "* : "<< a << "*" << b <<" = "<< a*b << "\n";
st.push(a*b);
}
else if (s[i] == '/')
{
//cout << "/ : "<< a << "/" << b <<" = "<< "\n";
st.push(a/b);
}
}
}
// 문제의 그 부분
cout << fixed << setprecision(2) << st.top();
//cout << st.top() + 0.00f;
return 0;
}13. 중위 -> 후위표기식
https://www.acmicpc.net/problem/1918
구현
- +- / */ / ( ) 의 우선순위에 따라 출력 시점을 결정한다.
- 문자는 그냥 보이면 출력한다.
문제점
1. 다른 사람의 풀이를 그대로 보고 풀었다.
지금보니 이해가 되지 않는 부분은, +부분이다.
괄호 내에 +가 있으면 괄호전까지 모두 출려갛는데,
괄호 닫는 괄호가 괄호 전까지의 기호를 모두 출력한다.
이 둘이 겹치지는 않을지. 어떤 매커니즘인지 모르겠다.
2. 일단 적긴 했는데.. 넘어가자.
제대로 보면 시간을 많이 쏟아야 할 것 같다.
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
stack<char> op;
for (int i = 0; i < s.length(); i++)
{
if (s[i] >= 'A' && s[i] <= 'Z')
{
cout << s[i];
}
else
{
if (s[i] == '(')
{
op.push(s[i]);
}
else if (s[i] == '*' || s[i] == '/')
{
// stack에 * / 가 같은 레벨이므로 모두 출력
//
while (!op.empty() && (op.top() == '*' || op.top() == '/'))
{
cout << op.top();
op.pop();
}
op.push(s[i]);
}
else if (s[i] == '+' || s[i] == '-')
{
//덧셈은 최하위 우선순위기 때문에, 이전의 것들을 다 뽑아냄. 괄호제외.
while (!op.empty() && op.top() != '(')
{
cout << op.top();
op.pop();
}
op.push(s[i]);
}
else if (s[i] == ')')
{
// 괄호 사이 요소들 모두 출력 / 괄호 앞도 제거
// 무조건 출력, 괄호가 먼저다.
while (!op.empty() && op.top() != '(')
{
cout << op.top();
op.pop();
}
op.pop();
}
}
}
// 남아있는 것들 제거
while (!op.empty())
{
cout << op.top();
op.pop();
}
return 0;
}14. 알파벳 개수
https://www.acmicpc.net/problem/10808
구현
- 그냥 알파벳 배열에 추가하면 된다.
- 아래와 같은 식이 가능하다는 것을 알아두면 쉽다.
for(int i=0; i<s.length(); i++) { alpha[s[i]-'a'] ++; }
15. 알파벳 찾기
https://www.acmicpc.net/problem/10809
구현
- 아래의 식으로 모든 원소를 -1로 초기화하면 쉽다.
fill(alpha, alpha+26, -1);
16. 문자열 분석
https://www.acmicpc.net/problem/10820
구현
- 구현 자체는 쉽다.
문제점
1. 테스트 케이스가 다수 주어지는데,
테스트 케이스의 수를 주지 않는다.
따라서 while문을 돌릴 시, 무한으로 돌아가게 되는데..
풀이는 맞았다고 뜬다.for문으로 하면 아래와 같다.
최대 테스트케이스에 맞게 100 넣었다.
//while(true)
for (int i = 0; i < 100; i++)
{
string s;
getline(cin, s);
if (s.length() < 1)
{
break;
}17. 단어 길이
https://www.acmicpc.net/problem/2743
구현
- 그냥 cout << s.length() 하면 풀리는 기초문제...
18. 암호화 +13
https://www.acmicpc.net/problem/11655
구현
- 소문자, 대문자, 숫자에 맞게 구현하면 된다.
문제점
- +13시에, 초과하면 26을 빼야했는데,
a나 A값을 빼는 실수를 했다.
19. AB CD
https://www.acmicpc.net/problem/10824
구현
- 문자열을 서로 붙이고, 숫자로 바꾼다. 그리고 더한다.
문제점
- stoi를 사용하니 실패.
- 수로 주어지는 크기가 컸기 때문에, stoll을 사용하여 해결.
20. 모든 접미사
https://www.acmicpc.net/problem/11656
구현
- substr을 사용하는 것이 관건.
아래처럼 사용하면 된다.- 중복은 없을 테지만, set에 넣음으로써 자동정렬을 실행.
- 그대로 iterator로 출력.
#include <iostream>
#include <set>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
set<string> se;
for(int i=0;i<s.length();i++)
{
string tmp;
tmp = s.substr(i, s.length());
se.insert(tmp);
}
for(auto i:se)
{
cout << i << "\n";
}
return 0;
}문제점
- 없
21. 최대공약수 / 최소공배수
= GCD / LCM
https://www.acmicpc.net/problem/2609
참고한 사이트
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kmc7468&logNo=221017936040
구현
- 우선 알고리즘을 외우는게 편하다고 생각한다.
GCD알고리즘을 외울 수 있다면,
GCD를 통해서 LCM까지 구할 수 있다.
int gcd(int a, int b)
{
int c;
while(b!=0)
{
c = a%b;
a=b;
b=c;
}
return a;
}- c라는 변수를 만들고 나머지를 넣는다.
- a=b, b=c를 한다.
- b라는 값이 결국 나머지가 되는데, 해당 값이 0일때까지 while
- 최종적으로 a를 리턴
gcd는 위처럼 구하면 되고,
lcm은 a*b / gcd(a,b) 를 하면 끝이다.
22. 최소공배수 복습
https://www.acmicpc.net/problem/1934
구현
- 외우면 된다.
23. 소수 찾기
https://www.acmicpc.net/problem/1978
구현
- 우선 알고리즘을 외우는게 편하다고 생각한다.
- 엄청나게 효율적인 에라토스테네스의 체 알고리즘을 본다.
아래의 코드는 내가 이해하기 쉽게 수정한 코드이다.
(24번에서 long long을 사용하여 완벽하게 만든 코드가 있으니 참고)
vector<bool> che(int n)
{
// 1부터 n까지 사용할거라 n+1 크기의 true로 초기화 한 벡터
vector<bool> isPrime(n + 1, true);
// 0과 1은 일단 소수가 아니다.
isPrime[0] = isPrime[1] = false;
for (int p = 2; p * p <= n; p++)
{
if (isPrime[p])
{
for (int i = p * p; i <= n; i += p)
{
isPrime[i] = false;
}
}
}
return isPrime;
}- vector를 반환하는 함수이고, 매개변수로는 판별하고 싶은 범위를 받는다.
- 일단 모든 수를 소수로 보고 시작한다.
- 그리고 for문을 돌며, 현재 값이 소수라면,
본인의 배수인 제곱부터 p를 더해나가며 배수들을 false로 처리한다.
(왜 2의 배수가 아니라 제곱부터 하는지 이유를 모르겠음)
(그 이유는 2의 배수는 이미 이전에 2를 다룰 때 처리되었으니깐..)
(같은 이유로, 3,5,,,, p이전의 배수는 다 처리했기 때문) - 그러니까 그냥 2부터 n까지의 수를
본인의 제곱부터 n까지 배수만 싹 false시켜버리면 끝인
사실 알고보면 간단한 알고리즘 이었다. - 그래서 해당 벡터를 반환하고 인덱스로 false인지 아닌지 사용하면 끝.
24. 소수 찾기
https://www.acmicpc.net/problem/1929
구현
- 에라토스테네스의 체를 쓰면 됨.
문제점
1. 범위로 주어지는 M의 값이 1,000,000인데,
그로 인해서 에라토스테네스의 체에서 1,000,000x1,000,000
으로 integer범위를 넘어갔다.
- 따라서 제곱이 있는 부분만 long long을 해주었는데도
해결되지 않았다.- 바깥쪽 for문에도 long long을 해주어야만 했다. 왜?
i는 2부터 n까지만 저장하는 값인데..
흠... 일단 둘 다 long long을 default로 하는 것이 좋아보인다.
#include <iostream>
#include <vector>
using namespace std;
vector<bool> che(int n)
{
// 1 사전작업
vector<bool> isPrime(n+1, true);
isPrime[0] = isPrime[1] = false;
// 2 배수 삭제 - long long
for(long long i=2; i<=n; i++)
{
for(long long j = i*i; j<=n; j+=i)
{
isPrime[j] = false;
}
}
return isPrime;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<bool> result = che(M);
for(int i=N;i<=M;i++)
{
if(result[i])
{
cout << i << "\n";
}
}
return 0;
}25. 골드바흐
https://www.acmicpc.net/problem/6588
4 이상의 모든 짝수는 소수인 홀수 합으로 나타낼 수 있다.
(틀린말?)
구현
- 먼저 에라토스테네스의 체를 최대 범위로 돌린다.
그래야만 모든 테스트케이스에서 소수인 홀수인지 확인할 수 있다.- 이제 테스트케이스마다 해당 벡터를 사용하여 풀게 되는데,
입력으로 받은 짝수 값에서 빼야하는 값과, 뺀 값이 소수라면
출력을 정상적으로 한다.- 여기서 트릭이 들어갔는데, i를 3부터 하고, i를 n-3까지만 구한다.
그 이유는, 짝수인 소수는 2밖에 없고, 따라서 3부터
판별하면 무조건 홀수인 소수가 나올 것이고,
빼야하는 수인 i가 n-3보다 커진다면, 2나 1이 나머지가 될텐데
의미가 없을 것이므로 이렇게 정해봤다.
문제점
1.if(result[i] && result[n-i])이렇게 적어야했는데,
단순히if(result[n-i])이렇게 적었었다.
#include <iostream>
#include <vector>
using namespace std;
vector<bool> che(int n)
{
// 1 사전작업
vector<bool> isPrime(n+1, true);
isPrime[0] = isPrime[1] = false;
// 2 배수제거
for(long long i=2; i<=n;i++)
{
for(long long j=i*i; j<=n; j+=i)
{
isPrime[j] = false;
}
}
return isPrime;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
vector<bool> result = che(1000000);
while(true)
{
int n;
cin >> n;
if(n==0)
{
break;
}
//for(int i=3; i<=n;i++)
for(int i=3; i<=n-3;i++)
{
if(result[i] && result[n-i])
{
cout << n << " = " << i << " + " << n-i << "\n";
break;
}
if(i==n-3)
{
cout << "Goldbach's conjecture is wrong.\n";
}
}
}
return 0;
}복습필요
1. 13번문제 이해 안 됨.
2. 유클리드호제법 (gcd, lcm)
3. 에라토스테네스의 체 (소수)
