△9023▲

https://programmers.co.kr/learn/courses/30/lessons/12973

- Stack사용/ 예시문자열 "baabaa"

1) 문장의 첫 문자(s[0]) push

2) 두번째 문자(s[1])부터 s.size만큼 반복하며 stack의 top과 비교

3) top과 비교문자가 같으면 pop

4) top과 비교문자가 다르면 push

5) 반복문 종료전 stack이 empty인 경우 비교하지 않고, push만 실행

6) 반복문 종료후 stack이 empty인지 확인

PASS) stack 사용하여 top과 다음 비교문자가 같으면 pop/ 다르면 push, 정확성: 60.2/ 효율성: 39.8

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = -1;

    bool flag = 0;

    stack<char> st;
    st.push(s[0]);
    for (int i = 1; i < s.size(); i++) {
        if (st.empty()) {
            st.push(s[i]);
            continue;
        }

        char ch = st.top();
        if (ch == s[i]) 
            st.pop();
        else
            st.push(s[i]);
    }

    if (st.empty())
        answer = 1;
    else
        answer = 0;

    return answer;
}

FAIL) substr로 2글자씩 split하여 비교, 정확성: 60.2 /효율성: 0.0

#include <iostream>
#include<string>
using namespace std;

int solution(string s)
{
    int answer = -1;

    bool flag = 0;
    for (int i = 0; i < s.size() - 1; i++) {
        if (s.empty()) {
            flag = 1;
            break;
        }
        
        string tmp = s.substr(i, 2);

        if (tmp[0] == tmp[1]) {
            s.erase(i, 2);
            i = -1;
        }
    }
    
    if (flag==1)
        answer = 1;
    else 
        answer = 0;

    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/42628

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;

    priority_queue<int, vector<int>> max_pq;
    priority_queue<int, vector<int>, greater<int>> min_pq;

    int cnt = 0;
    for (int i = 0; i < operations.size(); i++) {

        //pq가 empty일때 max_pq, min_pq 모두 초기화 해야됨
        if (cnt == 0) {
            while (!min_pq.empty()) min_pq.pop();
            while (!max_pq.empty()) max_pq.pop();
        }


        if (operations[i][0] == 'I') {
            string tmp = operations[i].substr(2, operations[i].size() - 2);
            int num = stoi(tmp);
            max_pq.push(num);
            min_pq.push(num);
            cnt++;
        }
        else {
            if (cnt == 0) continue;
            if (operations[i] == "D 1") {
                max_pq.pop();
                cnt--;
            }
            else {
                min_pq.pop();
                cnt--;
            }
        }
    }

    if (cnt != 0) {
        answer.push_back(max_pq.top());
        answer.push_back(min_pq.top());
    }

    else {
        answer.push_back(0);
        answer.push_back(0);
    }

    return answer;
}

int main() {

    //vector<int> answer = solution({ "I 16", "D 1" }); // 0, 0
    //vector<int> answer = solution({ "I 7","I 5","I -5","D -1" }); //7, 5
    vector<int> answer = solution({ "I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333" }); //333, -45

    cout << answer[0] << answer[1];

    return 0;
}

https://www.youtube.com/playlist?list=PLRx0vPvlEmdDgOIBt9MKQl-uMVrxtac4n 

1강 이산수학 개요

- 불연속적인 숫자를 다루는 수학

- 컴퓨터를 위한 수학, 참과 거짓으로 살펴보는 컴퓨터 수학, 전산, 정보 수학, 1학년이나 처음 컴퓨터를 배우는 입장에서 배우게됨, 자료구조 또는 알고리즘의 베이스, 논리적 사고, 컴퓨팅 사고력 향상

2강 명제와 연산자
- 명제 : 참/ 거짓으로 구분할 수 있는 문장

ex) "저 안경쓴 사람은 남자이다" -> 참이라는 진리값을 가지는 명제

 -> 여러 개의 명제를 조합할 수 있다.

- 명제 예시

1) 원빈은 잘생겼다 -> 개인의 주관이 개입가능, 명제X

2) 컴퓨터는 재미 없다 -> 개인의 주관이 개입가능, 명제X 

3) 11은 소수이다 -> 명제(참)

4) 모기는 동물이다. -> 명제(참)

- 연산자로 명제 다루기

 -> 연산자 : 명제를 연산하기 위한 도구

 : 여러 개의 명제를 합치면 합성명제/ 원인 -> 결과가 되는 명제는 조건명제

3강 역, 이, 대우(주로 조건명제에서 사용)

- 진리표 : 각 명제 사이의 관계식의 진리값을 보여주는 표, 아무리 복잡한 합성 명제라도 진리표로 해결할 수 있다.

 Q. 명제 "30이 10보다 크다면 30은 50보다 작다."에 대한 진리값과 역, 이, 대우 각각의 진리값 구하기

 : 본명제와 대우값은 반드시 같은 진리값을 반환한다.

4강 동치 관계

- 동치 : '논리적으로 일치한다'는 의미

 -> 같은 의미를 가진 더 쉬운 명제를 발견하는데 사용

 -> 동치법칙에는 다양한 종류가 있다.

- 동치법칙을 이용한 증명

 : 복잡한 합성명제도 간단한 명제로 바꿀 수 있다.

 -> 중요 : 드모르간의 법칙/ 흡수법칙/ 부정법칙/ 함축법칙

예시 문제) 동치법칙을 잘 알고있다면 진리표를 작성하지 않고 빠르게 간소화가 가능하다

https://leetcode.com/problems/second-highest-salary/

- group by 사용해서 중복 제외

SELECT IFNULL((
    SELECT Salary AS SecondHighestSalary
    FROM Employee
    /* group by 미사용시 중복제거 안됨 */
    GROUP BY salary
    ORDER BY Salary DESC
    /* offset을 limit보다 먼저하면 에러 */
    LIMIT 1
    OFFSET 1),NULL)
AS SecondHighestSalary

- max 제외하고 distinct

select ifnull(
    (select distinct salary 
    from Employee
    where salary < (select max(salary) from Employee)
    order by salary desc
    limit 1), null)
as SecondHighestSalary;

https://programmers.co.kr/learn/courses/30/lessons/42626

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;

    priority_queue<int, vector<int>,greater<int>> pq;

    for (int i = 0; i < scoville.size(); i++) {
        pq.push(scoville[i]);
    }

    int cnt = 0;
    while (1) {
        if (pq.size() == 1 && pq.top() < K)
            return -1;

        if (pq.top() > K)
            break;

        int pq1 = pq.top();
        pq.pop();
        int pq2 = pq.top();
        pq.pop();

        int tmp = pq1 + (pq2 * 2);

        pq.push(tmp);
        cnt++;
    }

    answer = cnt;
    return answer;
}

int main() {

    cout << solution({ 1, 2, 3, 9, 10, 12 }, 7);//	2

    return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/60057

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string s) {
    int answer = 0;

    int MIN = 21e8;

    if (s.size() == 1)
        MIN = 1;

    for (int i = 1; i <= s.size()/2; i++) {
        string result;
        int st=0;
        int cnt = 1;
        while (1) {
            string st1 = s.substr(st, i);
            if (st + i > s.size()) {
                result += st1;
                break;
            }
            string st2 = s.substr(st + i, i);
            if (st1 == st2)
                cnt++;
            else {
                if (cnt != 1)
                    result += to_string(cnt);
                result += st1;
                cnt = 1;
            }
            st += i;
            if (st >= s.size())
                break;
        }

        if (result.size() < MIN)
            MIN = result.size();
    }

    answer = MIN;
    return answer;
}

int main() {

    //TC5번
    cout << solution("a") << endl;//	1
    cout << solution("aaaaaaaaaaaaaaabbbbbbbbbbc") << endl;//	7
    cout << solution("aabbaccc") << endl;//	7
    cout << solution("ababcdcdababcdcd") << endl;//	9
    cout << solution("abcabcdede") << endl;//	8
    cout << solution("abcabcabcabcdededededede") << endl;//	14
    cout << solution("xababcdcdababcdcd") << endl;//	17
    cout << solution("acdhdh") << endl;//	5
    cout << solution("xztjabcdabcd") << endl;//	9

    return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/1835

#include <string>
#include <vector>
#include <iostream>

using namespace std;

char Friend[8];
bool used[8];

int cnt;
void dfs(int le, char path[], vector<string>check) {
    if (le==8) {
        for(int x=0; x<check.size(); x++){
            int a, b;
            for (int y = 0; y < 8; y++) {
                if (path[y] == check[x][0])
                    a = y;
                else if (path[y] == check[x][2])
                    b = y;
            }
            int checkNum = check[x][4] - '0';
            if (check[x][3] == '=') {
                if (abs(a - b) -1 != checkNum)
                    return;
            }
            else if (check[x][3] == '>') {
                if (abs(a - b) - 1 <= checkNum)
                    return;
            }
            else if(check[x][3] == '<') {
                if (abs(a - b) - 1 >= checkNum)
                    return;
            }
        }

        cnt++;
        return;
    }

    for (int i = 0; i < 8; i++) {
        if (used[i] == 1) continue;
        path[le] = Friend[i];
        used[i] = true;
        dfs(le + 1, path, check);
        used[i] = false;
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;

    Friend[0] = 'A';
    Friend[1] = 'C';
    Friend[2] = 'F';
    Friend[3] = 'J';
    Friend[4] = 'M';
    Friend[5] = 'N';
    Friend[6] = 'R';
    Friend[7] = 'T';

    cnt = 0;
    char path[8] = { NULL, };

    dfs(0, path, data);

    answer = cnt;
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/12981

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;

    vector<vector<string>> vec(10);

    int a = 0;
    int charSize = words[a].size();
    char last_ch = words[a][charSize - 1];

    int round = 1;
    while (1) {

        for (int i = 0; i < n; i++) {

            if (a == 0) {
                vec[i].push_back(words[a]);
                a++;
                continue;
            }

            //주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.
            if (a == words.size()) {
                answer.push_back(0);
                answer.push_back(0);
                return answer;
            }

            //이미 나왔던 단어면 탈락
            for (int x = 0; x < a; x++) {
                if (words[a] == words[x]) {
                    answer.push_back(i+1);
                    answer.push_back(round);
                    return answer;
                }
            }

            if (last_ch == words[a][0]) {
                vec[i].push_back(words[a]);
                charSize = words[a].size();
                last_ch = words[a][charSize - 1];
            }

            //끝말잇기 실패 탈락자 발생
            else {
                answer.push_back(i+1);
                answer.push_back(round);
                return answer;
            }

            a++;
        }
        round++;
    }

}