이건 강의는 따로 없고 그냥 참고해서 보고 문제를 푸는 느낌이당
- 후위표기법
중위 표기법은 일반적으로 수식을 표기할 때 사용하는 방식이다. 이는 연산자를 피연산자의 사이에 두는 방식이다.
ex) 1+2, 3*4, 5/6
반대로 후위 표기법은 연산자를 피연산자의 다음에 두는 방식이다.
ex) 1 2 +, 3 4 *, 2 1 -
전위 표기법은 연산자를 앞에 두는 방식이며, 폴란드 표기법이라고 한다. 반대로 후위 표기법은 역폴란드 표기법이라고도 한다.
중위 표기법은 사람이 보긴 편하지만, 컴퓨터가 처리하기엔 쉽지않다. 그래서 후위 표기법을 사용하면, 컴퓨터가 수식을 특별한 변환없이 처리할 수 있다.
후위 표기법으로 표현된 식을 계산하는 방법은 아래와 같다.
1. 피연산자는 스택에 넣는다.
2. 연산자를 만나면 피연산자를 2개를 스택에서 꺼내 계산하고, 계산된 결과를 다시 스택에 넣는다.
<1935번 / 후위 표기식2>
입력받은 숫자들을 배열에 저장해놓는다. 그리고 다른 숫자는 A, B, C, ... 순서대로 입력받기 때문에 저장한 배열에서 str[i]에서 대문자 알파벳 아스키코드를 뺀 값을 인덱스로 사용하여 배열에서 호출하면 된다. 전체적인 알고리즘은 스택을 이용하여 구현하면 된다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> #include <string> #include <stack> #include <iomanip> using namespace std; #define MAX 26 int arr[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; string str; cin >> str; for (int i = 0; i < n; i++) { cin >> arr[i]; } stack<double> s; for (int i = 0; i < str.length(); i++) { if (str[i] >= 'A'&&str[i] <= 'Z') { s.push(arr[str[i]-'A']); } else { double b = s.top(); s.pop(); double a = s.top(); s.pop(); switch (str[i]) { case '+': s.push(a + b); break; case '-': s.push(a - b); break; case '*': s.push(a * b); break; case '/': s.push(a / b); break; } } } cout << fixed; cout.precision(2); cout << s.top() << '\n'; return 0; } |
cs |
-차량기지 알고리즘
중위 표기법으로 표현된 식을 후위 표기법으로 바꾸는 알고리즘이다. 연산자를 저장하는 스택을 기반으로 이루어져 있다.
> 연산자의 우선순위가 스택의 가장 위에 있는 연산자의 우선순위보다 작거나 같은 동안 스택에 있는 연산자를 결과 추가한다.
> 모든 연산자/피연산자 처리가 끝나면, 연산자 스택에 있는 연산자를 하나씩 결과에 추가한다.
> 괄호가 있는 식의 경우에는 여는 괄호는 연산자 스택에 넣고 닫는 괄호가 나오면 여는 괄호가 나올 때까지 연산자 스택에서 계속해서 연산자를 꺼낸다.
<1918번 / 후위 표기식>
차량기지 알고리즘을 통해 구현한다. 알파벳이면 그냥 출력하고 연산자인 경우 우선순위에 따라 나누어서 출력한다. '('의 경우 연산자 스택에 넣는다. ')'인 경우에는 '('가 나올 때까지 연산자 스택에서 계속해서 연산자를 꺼낸다. '*' 또는 '/'인 경우 스택이 비어있지 않고 현재 스택의 top이 * 또는 / 인 경우 pop하여 출력한다. 그리고 이 과정이 끝나면 현재 연산자를 스택에 저장한다. '+'나 '-'인 경우 스택이 비어있지 않거나 top이 '('가 아닌 경우 스택의 top을 출력한다. 이 또한 위 과정을 마치면 연산자를 스택에 저장한다. 모든 과정이 끝나면 스택에 남아있는 연산자를 모두 출력하면 끝!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <iostream> #include <string> #include <stack> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str; cin >> str; stack<char> s; string result; for (int i = 0; i < str.length(); i++) { if (str[i] >= 'A'&&str[i] <= 'Z') { result += str[i]; } else { switch (str[i]) { case '(': s.push(str[i]); break; case '*': case '/': while (!s.empty() && (s.top() == '*' || s.top() == '/')) { result += s.top(); s.pop(); } s.push(str[i]); break; case '+': case '-': while (!s.empty() && s.top() != '(') { result += s.top(); s.pop(); } s.push(str[i]); break; case ')': while (!s.empty() && s.top() != '(') { result += s.top(); s.pop(); } s.pop(); break; } } } while (!s.empty()) { result += s.top(); s.pop(); } cout << result << '\n'; return 0; } |
cs
|
- 문자열
아스키코드는 문자 인코딩 방법으로, 대표적인 아스키 코드로는 '0' = 48, 'A' = 65, 'a' = 97, NULL = '0'을 나타낸다. 숫자가 저장되어 있는데, 출력만 글자로 해주는 것으로 이해하면 편하다고 한다 ><
<10808번 / 알파벳 개수>
26개 크기의 배열을 만들고 입력받은 문자에서 97을 빼서 아스키코드를 통해 index를 정해서 배열에 알파벳의 개수를 저장한다. 이는 소문자로만 이루어진 문자열을 입력받기 때문에 97을 빼서 계산하면 된다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <string> using namespace std; int arr[26]; int main() { string str; cin >> str; for (int i = 0; i < str.length(); i++) { arr[str[i] - 97]++; } for (int i = 0; i < 26; i++) { cout << arr[i] << " "; } cout << '\n'; return 0; } |
cs |
<10809번 / 알파벳 찾기>
위의 코드와 거의 같지만 배열에 인덱스를 저장한면 된다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <string> using namespace std; int arr[26]; int main() { string str; cin >> str; for (int i = 0; i < 26; i++) { arr[i] = -1; } for (int i = 0; i < str.length(); i++) { if (arr[str[i] - 97] == -1) { arr[str[i] - 97] = i; }
} for (int i = 0; i < 26; i++) { cout << arr[i] << " "; } cout << '\n'; return 0; } |
cs |
<10820번 / 문자열 분석>
4개의 함수를 만들어서 구현하였다. 여기서 종료조건이 명확히 드러나지 않아서 이를 안했더니 틀렸다. 그래서 입력받은 문자열의 길이가 0일때 종료하도록 설정하였다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <string> using namespace std; #define N 100 int upper(string str) { int n = 0; for (int i = 0; i < str.length(); i++) { if (str[i] >= 'A'&&str[i] <= 'Z') n++; } return n; } int lower(string str) { int n = 0; for (int i = 0; i < str.length(); i++) { if (str[i] >= 'a'&&str[i] <= 'z') n++; } return n; } int space(string str) { int n = 0; for (int i = 0; i < str.length(); i++) { if (str[i] == ' ') n++; } return n; } int number(string str) { int n = 0; for (int i = 0; i < str.length(); i++) { if (str[i] >= 48 && str[i] <= 57) n++; } return n; } int main() { for (int k = 0; k < 100; k++) { string str; getline(cin, str); if (str.length() == 0) break; cout << lower(str) << " " << upper(str) << " " << number(str) << " " << space(str) << '\n'; } return 0; } |
cs |
<2743번 / 단어 길이 재기>
이거 머 그냥 반복문 돌려서 문자열 개수 세면 됨. 좀 특이점은 for문 조건에 str[i] 부분? 이게 str[i]가 존재할 때까지 라는 의미인것같다. 이렇게 써도 되는지 처음 알아써... 신기하다ㅎㅎㅎ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str; cin >> str; int len = 0; for (int i = 0; str[i]; i++) { len++; } cout << len << '\n'; return 0; } |
cs |
자꾸 검색해서 찾아보기 귀찮아서 블로그에 박제 ^^*
<11655번 / ROT13>
이 문제는 원래 그냥 대소문자만 구분해서 처리하려고 했다. 근데 그러면 13을 더했을 때 알파벳의 범위를 벗어나게 된다. 이를 해결하기 위해 마지막 알파벳의 아스키코드값을 뺴고 그만큼을 첫번쨰 알파벳의 아스키코드에 더해서 해결하려고 했으나, u를 입력했을때 13을 더하자 -126으로 인식하였다. 그래서 고민하던 찰나에 알파벳은 26개이고 13씩 더해준다면 13을 기준으로 반씩 나눠서 0~12번째 index 알파벳은 13을 더하고, 그 뒤는 13을 빼주는 방식으로 구현하였다. (사실 구글링하다가 찾은거임..ㅋㅋ) 이게 더 효율적인것 같아서 이렇게 했다!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str; getline(cin, str); string res; for (int i = 0; i < str.length(); i++) { if (str[i] >= 'A'&&str[i] <= 'M') { res += str[i] + 13; } else if (str[i] >= 'N'&&str[i] <= 'Z') { res += str[i] - 13; } else if (str[i] >= 'a'&&str[i] <= 'm') { res += str[i] + 13; } else if (str[i] >= 'n'&&str[i] <= 'z') { res += str[i] - 13; } else res += str[i]; } cout << res << '\n'; return 0; } |
cs |
<10824번 / 네 수>
이씨 이것도 int / long long 시간 차이때매 런타임 에러 발생했다... stoi했을때 런타임초과나서 stoll했더니 해결됐다 - -
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int a, b, c, d; cin >> a >> b >> c >> d; string s1, s2; s1 = to_string(a) + to_string(b); s2 = to_string(c) + to_string(d); cout << stoll(s1) + stoll(s2) << '\n'; return 0; } |
cs |
<11656번 / 접미사 배열>
반복문에서 substr을 통해 문자열을 잘라서 string 배열에 저장한다. 그리고 alogoritm 헤더파일에 있는 함수인 sort함수를 통해 오름차순으로 정리한다. sort함수에는 시작 index부터 마지막 index를 입력하면 된다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str; cin >> str; string s[1000]; int len = str.length(); for (int i = 0; i < len; i++) { s[i] = str.substr(i, len); } sort(s, s + len); for (int i = 0; i < len; i++) { cout << s[i] << '\n'; } return 0; } |
cs |
아휴 겨우 다했넹
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 3강 수학 1 - 참고 (0) | 2020.08.20 |
|---|---|
| 3강 수학 1 - 연습 (0) | 2020.08.20 |
| 3강 수학 1 - 수학 1 (0) | 2020.08.19 |
| 2강 자료구조 1 - 연습 (0) | 2020.08.16 |
| 2강 자료구조 1 - 큐와 덱 (0) | 2020.08.10 |
댓글