🫒다음회의까지 해야할 일
1. 자신이 담당인 주제 2개 중 1개에 대해 라이브코딩 + 필수 + 도전문제 샘플코드 작성하여 PR
2. 자신이 보조자인 주제 2개중 1개에 대해 구현문제 샘플코드 작성하여 PR
3. 이퍼 담당 문제 샘플코드 작성하여 이퍼 노션 페이지에 업로드
* 4기 문제 재활용하셨으면 4기 샘플코드와 강의자료 모두 재활용하셔도 됩니다.
Organization에서 4기 레포지토리 들어가면 확인 가능합니다!
(혹시 새로 뽑은 문제가 너무 많아서 준비할 샘플코드 양이 부담되시면 4기 문제를 재활용하셔도 좋아요:)
🫒 담당 주차 1개 - 필수문제,도전문제 PR
4기 코드 참고! 선배님들 감사합니다
라이브 코딩
백준 10828: 스택 (실버4/스택)
#include <iostream>
#include <stack> //스택 라이브러리
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, x;
stack<int> s; //스택 s 선언
string cmd;
cin >> n;
while(n--) {
cin >> cmd;
if(cmd == "push") {
cin >> x;
s.push(x); //스택에 값 push
}
else if(cmd == "pop") {
if(s.empty()) { //스택이 비어 있을 시 1 리턴
cout << -1 << '\n';
}
else {
cout << s.top() << '\n'; // 스택 top 값 삭제 없이 리턴
s.pop(); // 스택 top 값 삭제(리턴값 없음)
}
}
else if(cmd == "size") {
cout << s.size() << '\n'; //스택 크기 리턴
}
else if(cmd == "empty") {
cout << s.empty() << '\n';
}
else if(cmd == "top") {
if(s.empty()) {
cout << -1 << '\n';
}
else {
cout << s.top() << '\n';
}
}
}
return 0;
}
백준 10845: 큐 (실버4/큐)
#include <iostream>
#include <queue> // 큐 라이브러리
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, x;
string cmd;
queue<int> q;
cin >> n;
while(n--) {
cin >> cmd;
if(cmd == "push") {
cin >> x;
q.push(x); //큐에 값 넣기
}
else if(cmd == "pop") {
if(q.empty()) { //큐가 비어 있을 시 1 리턴
cout << -1 << '\n';
}
else {
cout << q.front() << '\n'; //큐의 front 값 삭제 없이 리턴
q.pop(); // 큐의 front 삭제
}
}
else if(cmd == "size") {
cout << q.size() << '\n'; //큐의 사이즈 리턴(구성요수수)
}
else if(cmd == "empty") {
cout << q.empty() << '\n';
}
else if(cmd == "front") {
if(q.empty()) {
cout << -1 << '\n';
}
else {
cout << q.front() << '\n';
}
}
else if(cmd == "back") {
if(q.empty()) {
cout << -1 << '\n';
}
else {
cout << q.back() << '\n';
}
}
}
return 0;
}
백준 10866: 덱 (실버4/덱)
#include <iostream>
#include <deque> //덱 라이브러리
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, x;
string cmd;
deque<int> dq; //덱 dp 선언
cin >> n;
while(n--) {
cin >> cmd;
if(cmd == "push_front") {
cin >> x;
dq.push_front(x); //덱의 앞의 원소 front를 삭제한다
}
else if(cmd == "push_back") {
cin >> x;
dq.push_back(x);//덱의 뒤의 원소 back을 삭제한다
}
else if(cmd == "pop_front") {
if(dq.empty()) {
cout << -1 << '\n';
}
else {
cout << dq.front() << '\n';
dq.pop_front();
}
}
else if(cmd == "pop_back") {
if(dq.empty()) { // 덱이 비어 있을 시 1 리턴
cout << -1 << '\n';
}
else {
cout << dq.back() << '\n';
dq.pop_back();
}
}
else if(cmd == "size") {
cout << dq.size() << '\n'; //덱의 크기(구성요소수) 리턴
}
else if(cmd == "empty") {
cout << dq.empty() << '\n';
}
else if(cmd == "front") {
if(dq.empty()) {
cout << -1 << '\n';
}
else {
cout << dq.front() << '\n';
}
}
else if(cmd == "back") {
if(dq.empty()) {
cout << -1 << '\n';
}
else {
cout << dq.back() << '\n'; //덱의 백 요소 리턴 (삭제 없음)
}
}
}
return 0;
}
필수(3)
백준 1158번 : 요세푸스 문제 (실버 4 / 큐)
#include <iostream>
#include <queue>
using namespace std;
vector<int> josephus(int n, int k) { // 요세푸스 순열 반환
vector<int> result; // 요세푸스 순열
queue<int> q; // 원
for(int i = 1; i <= n; i++) { // 원 초기화
q.push(i);
}
while(!q.empty()) {
for(int i = 0; i < k-1; i++) { // k-1번 pop & push
q.push(q.front());
q.pop();
}
// k번째 사람 pop 후 순열에 추가
result.push_back(q.front());
q.pop();
}
return result;
}
/*
* 원을 따라 k번째 사람을 제거한다.
* 1. k번째 사람이 아닌 사람은 원의 맨 뒤로 보낸다.
* 2. k번째 사람은 원에서 제거한다.
*/
int main() {
int n, k;
queue<int> q;
// 입력
cin >> n >> k;
// 연산
vector<int> result = josephus(n, k);
// 출력
cout << "<" << result[0];
for(int i = 1; i < n; i++) {
cout << ", " << result[i];
}
cout << ">";
return 0;
}
백준 4949번 : 균형잡힌 세상 (실버 4 / 스택)
#include <iostream>
#include <stack>
using namespace std;
bool isBalanced(string input) { // 괄호가 균형을 이루었는지 여부 반환
stack<char> s; // 괄호 저장하는 스택
for(int i = 0; i < input.length(); i++) {
char ch = input[i];
switch(ch) {
case '(': case '[': // 여는 괄호는 무조건 push
s.push(ch);
break;
case ')': // 닫는 소괄호
if(s.empty() || s.top() != '(') {
return false;
}
s.pop();
break;
case ']': // 닫는 대괄호
if(s.empty() || s.top() != '[') {
return false;
}
s.pop();
break;
}
}
return s.empty();
}
/*
* [괄호 균형 확인하기]
* 1. 여는 괄호는 바로 스택에 넣는다.
* 2. 닫는 괄호가 나오면 가장 최근에 넣었던 여는 괄호와 비교한다.
* 2-1. 닫는 괄호와 여는 괄호의 종류가 같다면 해당 닫는 괄호가 균형을 이룬다.
* 2-2. 직전에 나온 여는 괄호가 없거나 그 종류가 다르다면 해당 닫는 괄호가 균형을 이루지 못한다.
* 3. 모든 닫는 괄호가 여는 괄호와 짝을 이루었더라도 스택에 여는 괄호가 남아있다면 균형을 이루지 못한다.
*/
int main() {
string input;
while(true) {
// 입력
getline(cin, input);
if(input == ".") {
break;
}
// 연산 & 출력
if(isBalanced(input)) {
cout << "yes\n";
}
else {
cout << "no\n";
}
}
return 0;
}
도전(2)
- 벡준 17298 : 오큰수 (골드 4 / 스택)
#include<iostream>
#include<algorithm>
#include<stack> //스택 사용
using namespace std;
int N;
stack<int> myStack;
int answer[1000001];
int Nlist[1000001];
int main()
{
cin >> N;
// 입력받기
for (int i = 0; i < N; i++)
cin >> Nlist[i];
// 스택이 비었을 때 예외 처리 / 새로 들어오는 값(오른쪽에 있는값)이 해당 값보다 크면 해당값의 오큰수가 될 수 있음.
for (int i = 0; i < N; i++){
while (!myStack.empty() && Nlist[myStack.top()] < Nlist[i]){
answer[myStack.top()] = Nlist[i];
myStack.pop();
}
myStack.push(i);
}
// 스택에 남아있던 애는 오큰수가 될 수 있는 수가 없었던 것이므로 -1 저장
while(!myStack.empty()) {
answer[myStack.top()] = -1;
myStack.pop();
}
// 결과
for (int i = 0; i < N; i++)
cout << answer[i] << " ";
}
백준 1918 : 후위 표기식 (골드2/ 스택)
#include <iostream>
#include <stack>
using namespace std;
int priority(char ch) { // 연산자 우선순위 반환
switch(ch) {
case '(': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2; // 연산자 순위 가장 높음 (먼저 계산되어야 함)
}
}
string postfix(string input) { // 중위 표기식 -> 후위 표기식
string result = ""; // 후위 표기식
stack<char> op; // 연산자 저장하는 스택
for(int i = 0; i < input.size(); i++) {
char ch = input[i];
switch(ch) {
// 여는 괄호는 무조건 push
case '(':
op.push(ch);
break;
// 닫는 괄호는 여는 괄호를 만날 때까지 pop
case ')':
while(!op.empty() && op.top() != '(') {
result += op.top();
op.pop();
}
op.pop(); // 여는 괄호 제거
break;
// 연산자의 경우, 스택에 들어있는 연산자와 우선순위 비교
case '+': case '-': case '*': case '/':
// 스택에 현재 연산자보다 우선순위가 높은 (=먼저 계산되어야 하는) 연산자가 있는 경우 pop
while(!op.empty() && priority(op.top()) >= priority(ch)) {
result += op.top();
op.pop();
}
op.push(ch); // 현재 연산자 push
break;
// 피연산자는 바로 결과에 추가
default:
result += ch;
}
}
// 스택에 남아있는 연산자 결과에 추가
while(!op.empty()) {
result += op.top();
op.pop();
}
return result;
}
/*
* [중위 표기식 -> 후위 표기식]
* 1. 피연산자는 순서가 변하지 않으므로 바로 결과에 추가한다.
* 2. 연산자는 우선순위에 따라 순서가 변하므로 스택에 잠시 저장한다.
* 3. 스택의 top에 있는 연산자는 우선순위가 제일 높아야 한다.
* 4. 스택의 top에 있는 연산자가 현재 연산자보다 우선순위가 같거나 높으면 스택에서 값을 꺼내야 한다.
* 5. 여는 괄호는 무조건 스택에 넣는다.
* 6. 닫는 괄호가 들어오면 여는 괄호가 나올 때까지 스택에 있는 연산자를 결과에 추가한다.
*/
int main() {
string input; // 입력값 (중위 표기식)
// 입력
cin >> input;
// 연산 & 출력
cout << postfix(input);
return 0;
}
🫒 보조 주차 구현 문제 1개 - 샘플코드 작성 & PR
- 4주차 브루트포스
- 구현(1) : 백준 1063: 킹 (실버4/구현, 시뮬레이션)
C++
#include<iostream>
#include<string>
#include<vector> //pair
using namespace std;
typedef pair<char, char> cc; //pair<char, char> -> cc
cc move(string input, char x, char y) {//이동 함수 x : 열, y : 행
for (char how : input) {
if (how == 'R') {
x++;
}
else if (how == 'L') {
x--;
}
else if (how == 'B') {
y--;
}
else {//T
y++;
}
}
return { x, y };
}
bool checkRange(cc position) { //범위 체크 하는 함수
if (position.first < 'A' || position.first > 'H' || position.second < '1' || position.second > '8') {
return false;
}
return true;
}
bool isSame(cc k, cc s) {
return (k.first == s.first && k.second == s.second);
}
/*
* HINT : 문자형 변수의 연산은 비교적 자유로워요! 또 킹과 돌의 움직임이 모두 판 안에서 이뤄질 때만 다음으로 움직일 수 있는 점을 신경써주세요!
* 1. king 이동 (move)
* 2. king과 stone의 위치 동일 -> stone 이동 (move)
* 3. king과 stone의 위치 점검 (checkRange
*/
int main() {
cc k, s; //king, stone
int n;
string input;
//입력
cin >> k.first >> k.second >> s.first >> s.second >> n;
//연산
while (n--) {
cin >> input;
cc next_k, next_s;//이동 후 위치 저장할 변수
//king 이동
next_k = move(input, k.first, k.second);
//stone 이동
if (isSame(next_k,s)) {//돌 위치와 겹치면
next_s = move(input, s.first, s.second);
}
else {
next_s = s;
}
//범위 체크
if (checkRange(next_k) && checkRange(next_s)){//이동한 king과 stone가 유효 범위면 최종적으로 이동
k = next_k;
s = next_s;
}
}
//출력
cout << k.first << k.second <<'\n'<< s.first << s.second ;
return 0;
}
4기 활용
🫒 이퍼 담당 샘플 코드
으..c..
더미파일이 뭐지?
'✨ Club|Project > 알튜비튜 e-class 튜터 | Algorithm' 카테고리의 다른 글
❇️ 알튜비튜 ❇️ - 8월 2주차 회의 (0) | 2023.08.12 |
---|---|
❇️ 알튜비튜 ❇️ - 8월 1주차 회의 (0) | 2023.08.08 |
❇️ 알튜비튜 ❇️ - 7월 5주차 회의 (0) | 2023.07.31 |
❇️알튜비튜❇️ - 7월 3주차 회의 (0) | 2023.07.16 |
❇️알튜비튜 5기❇️ / 알고리즘 튜터👩🏻🏫 (1) | 2023.05.31 |