본문 바로가기
✨ Club|Project/알튜비튜 e-class 튜터 | Algorithm

❇️ 알튜비튜 ❇️ - 7월 4주차 회의

by 정람지 2023. 7. 27.

🫒다음회의까지 해야할 일

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)

  1. 벡준 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..


더미파일이 뭐지?

아하! 더미인형처럼?