△9023▲

- Test1. 답은 맞으나 시간초과

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n,x;
int arr[100000];
int path[2];
int cnt = 0;

void run(int le, int st) {

    if (le == 2) {
        if (path[0] + path[1] == x)  cnt++;
        return;
    }

    for (int i = st; i < n; i++) {
        path[le] = arr[i];
        run(le + 1, i + 1);
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cin >> x;
    
    run(0,0);

    cout << cnt;
    return 0;
}

- Test2. 정렬후 처음과 끝의 합이 찾는값보다 크거나 작으면 s++, e--

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n,x;
int arr[100000];
int cnt = 0;

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cin >> x;
    
    sort(arr, arr + n);
    
    int start = 0, end = n - 1;
    int sum;
    while(start<end) {
        sum = arr[start] + arr[end];
        if (sum == x) {
            cnt++;
            start++;
            end--;
        }
        else if (sum > x) end--;
        else if (sum < x) start++;
    }

    cout << cnt;
    return 0;
}

- insert sort 삽입정렬

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int arr[6] = { 4,9,11,8,6,2 };

    int result[6];

    for (int y = 0; y < 6; y++) {
        result[y] = arr[y];

        for (int x = y; x > 0; x--) {
            if (result[x - 1] < result[x])
                swap(result[x - 1], result[x]);
            else break;
        }
    }

    for (int x = 0; x < 6; x++)
        cout << result[x] << " ";

    return 0;
}

- 삽입정렬 구조체, compare함수 사용

#include<iostream>
#include<vector>

using namespace std;

struct node {
    int a;
    char b;
};

bool compare(node front, node back) {
    if (front.a < back.a) return true; //앞의 숫자가 더 작아야 한다 true
    if (front.a > back.a) return false; // 뒤에 숫자가 더 작으면 false
    return front.b > back.b;        // 숫자가 같을경우 문자비교
}

int main() {
    node arr[5] = {
        {1,'A'},{3,'A'},{2,'C'},{1,'B'},{3,'B'}
    };

    node result[5];

    for (int i = 0; i < 5; i++) {
        result[i] = arr[i];

        for (int j = i; j > 0; j--) {
            node front = result[j - 1];
            node back = result[j];
            if (!compare(front, back)) { //우선순위조건에 반하지 않을때 자리바꿈
                swap(result[j - 1], result[j]);
            }
            else break;
        }
    }

    for (int i = 0; i < 5; i++) 
        cout << result[i].a <<" " << result[i].b << endl;

    return 0;
}

- sort STL 사용하기

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {

    int arr[6] = { 3,6,2,1,5,8 };

    sort(arr, arr + 6); // 오름차순 (, less<int>()) default
    sort(arr, arr + 6, greater<int>()); //내림차순

    string str = "kevinchoi";
    sort(str.begin(), str.end());
    sort(str.begin(), str.end(), greater<char>());

    string brr[4] = { "kevin","bob","jane","kate" };
    sort(brr, brr + 4);
    sort(brr, brr + 4, greater<string>());

    vector<int>vect = { 6,3,4,6,5,2,1,9 };
    sort(vect.begin(), vect.end());
    sort(vect.begin(), vect.end(),greater<int>());

    vector<vector<int>>t = { {3,2},{1,3}, {6,2} };
    sort(t.begin(), t.end());
    sort(t.begin(), t.end(), greater<vector<int>>());

    pair<int, int> p;
    vector<pair<int, int>>pp = { {8,2},{3,3},{5,2} };
    sort(pp.begin(), pp.end(), greater<pair<int, int>>());

    return 0;
}

- 짝수우선 내림차순 (STL사용)

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

//짝수우선 내림차순
bool compare(int front, int back) {
    if (front % 2 == 0 && back % 2 == 1) return true;
    if (front % 2 == 1 && back % 2 == 0) return false;
    return front > back;
}

int main() {
    int arr[7] = { 2,6,41,3,7,4,8 };

    
    sort(arr, arr + 7, compare);

    return 0;
}

- 구조체배열 sort (숫자내림, 문자오름)

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct abc {
    char ch;
    int num;
};

bool compare(abc front, abc back) {
    if (front.num > back.num) return true;
    if (front.num < back.num) return false;
    return front.ch < back.ch;
}

int main() {
    
    abc arr[4] = {
        {'A',1}, {'B',2},{'B',1},{'A',9}
    };
    
    sort(arr, arr + 4, compare);

    return 0;
}

- Counting sort

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
    int arr[7] = { 3,9,1,2,1,3,4 };
    int dat[11] = { 0 };
    int result[11];

    for (int i = 0; i < 7; i++) {
        dat[arr[i]]++;
    }

    for (int i = 1; i < 11; i++) {
        dat[i] += dat[i - 1];
    }

    for (int i = 0; i < 7; i++) {
        int t = arr[i];
        result[dat[t]--] = t;
    }

    return 0;
}

- union-find 독립된 data를 그룹화시켜서 관리

#include <iostream>

using namespace std;

int arr[200];

char findboss(char member) {
    if (arr[member] == 0) return member;
    char boss = findboss(arr[member]);
    return boss;
}

void setunion(char a, char b) {
    char aboss = findboss(a);
    char bboss = findboss(b);
    if (aboss == bboss) return;
    arr[bboss] = aboss;
}

int main() {

    setunion('A', 'B');
    setunion('E', 'F');
    setunion('B', 'F');
    setunion('F', 'A');
    setunion('C', 'D');
    
    char input1, input2;

    cin >> input1 >> input2;

    if (findboss(input1) == findboss(input2))
    {
        cout << "같은그룹";
    }

    else cout << "다른그룹";

    return 0;
}

- union-find 그룹은 몇개?

#include <iostream>
#include <vector>

using namespace std;

int arr[200];

char findboss(char member) {
    if (arr[member] == 0) return member;
    char boss = findboss(arr[member]);
    arr[member] = boss; //효율성
    return boss;
}

void setunion(char a, char b) {
    char aboss = findboss(a);
    char bboss = findboss(b);
    arr[bboss] = aboss; //bboss가 aboss 밑으로 들어감(같은그룹)
}

int main() {
    vector<string>vect = {
        "AE",
        "BD",
        "FE",
        "CE",
        "DB",
        "CA",
    };

    int len = vect.size();
    int cnt = len;
    for (int x = 0; x < len; x++) {
        if (findboss(vect[x][0]) != findboss(vect[x][1])) {
            setunion(vect[x][0], vect[x][1]);
            cnt--;
        }
    }

    cout << cnt;

    return 0;
}

- union-find를 사용하여 n개의 간선 연결시 cycle 존재여부 확인

#include <iostream>
#include <vector>

using namespace std;

int arr[200];

char findboss(char member) {
    if (arr[member] == 0) return member;
    char boss = findboss(arr[member]);
    arr[member] = boss;
    return boss;
}

void setunion(char a, char b) {
    char aboss = findboss(a);
    char bboss = findboss(b);
    arr[bboss] = aboss;
}

int main() {
    int n;
    cin >> n;

    for (int x = 0; x > n; x++) {
        int a, b;
        cin >> a >> b;
        if (findboss(a) == findboss(b)) { //보스가 같으면 싸이클존재
            cout << "cyle 존재";
            return 0;
        }
        setunion(a, b);
    }

    cout << "cycle 없음";

    return 0;
}

- 최소신장트리 (크루스칼알고리즘)

 1. 비용기준 sort

 2. 그룹화 union-find - 싸이클방지

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node {
    char a;
    char b;
    int cost;
};

vector<node>arr = {
    {'A','B',5},
    {'A','C',3},
    {'A','D',2},
    {'A','E',6},
    {'B','C',7},
    {'B','E',8},
    {'C','D',4},
    {'C','E',2},
};

char brr[200];

bool compare(node front, node back) {
    return front.cost < back.cost;
}

//char findboss(char member) {
//    if (arr[member] == 0) return member;
//    char boss = findboss(arr[member]);
//    arr[member] = boss;
//    return boss;
//}
//
//void setunion(char a, char b) {
//    char aboss = findboss(a);
//    char bboss = findboss(b);
//    arr[bboss] = aboss;
//}

int main() {
    int n = arr.size();

    sort(arr.begin(), arr.end(), compare);

    int sum = 0;
    int cnt = 0;

    for (int x = 0; x < n; x++) {
        if (findboss(arr[x].a) != findboss(arr[x].b)) {
            setunion(arr[x].a, arr[x].b);
            sum += arr[x].cost;
            cnt++;
            if (cnt == 4) break; //정점의 갯수 -1 최소경로
        }
    }
    
    cout << sum;

    return 0;
}

- 테두리 칠하고 시작하기

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

using namespace std;

int cnt;
int n, m;
int map[20][20];
vector<int>word;

void check(int y, int x) {
    
    for (int i = 0; i < m+2; i++) {
        if (x + i >= n + 2 || word[i] != map[y][x + i])break;
        if (i == m + 1)
            cnt++;
    }

    for (int i = 0; i < m + 2; i++) {
        if (y + i >= n + 2 || word[i] != map[y + i][x])break;
        if (i == m + 1) 
            cnt++;
    }
}

int sun = 0;
void run() {
    sun++;
    cnt = 0;
    word.clear();

    cin >> n >> m;

    word.push_back(0);
    for (int i = 0; i < m; i++) {
        word.push_back(1);
    }
    word.push_back(0);


    for (int i = 0; i < n+2; i++) {
        for (int j = 0; j < n+2; j++) {
            if (i == 0 || i == n + 1 || j == 0 || j == n + 1)
                map[i][j] = 0;
            else cin >> map[i][j];
        }
    }

    /*for (int i = 0; i < n + 2; i++) {
        for (int j = 0; j < n + 2; j++) {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }*/

    for (int i = 0; i <= n + 2; i++) {
        for (int j = 0; j <= n+2; j++) {
            check(i, j);
        }
    }



    cout << "#" << sun << " " << cnt<< endl;

}

int main() {
    int t;

    cin >> t;

    for (int i = 0; i < t; i++)
        run();

    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int sun = 0;
void run(string bit){
    sun++;
    int cnt = 0;
    int size = bit.size();

    bool now = 1;

    for (int i = 0; i < size; i++) {
        int num = stoi(bit.substr(i,1));
        if (num == now) {
            cnt++;
            now = !now;
        }
    }

    cout << "#" << sun << " " << cnt << endl;
    
}

int main() {
    int t;
    cin >> t;
    string bit;

    for (int i = 0; i < t; i++) {
        cin >> bit;
        run(bit);
    }
    

    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
int sun = 0;
void run(string st) {
    int bu = st.size() / 3;
 
    sun++;
 
    int s[14] = { 0 }, d[14] = { 0 }, h[14] = { 0 }, c[14] = { 0 };
 
    int ss = 13, dd = 13, hh = 13, cc = 13;
 
    char ch;
    int num;
    for (int i = 0; i < bu; i++) {
        ch = st[i * 3];
        string tmp = st.substr(i * 3 + 1, 2);
        num = stoi(tmp);
        if (ch == 'S')
            s[num]++;
        else if (ch == 'D')
            d[num]++;
        else if (ch == 'H')
            h[num]++;
        else if (ch == 'C')
            c[num]++;
    }
 
    for (int i = 1; i <= 13; i++) {
        if (s[i] >1  || d[i] >1 || h[i] >1 || c[i] >1) {
            cout << "#" << sun << " " "ERROR" << endl;
            return;
        }
        if (s[i] == 1) ss--;
        if (d[i] == 1) dd--;
        if (h[i] == 1) hh--;
        if (c[i] == 1) cc--;
    }
 
    cout << "#" << sun << " " << ss << " " << dd << " " << hh << " " << cc << endl;
 
}
 
int main() {
    int t;
    string st;
 
    cin >> t;
 
    for (int i = 0; i < t; i++) {
        cin >> st;
        run(st);
    }
 
    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
int t, sun;
 
void run(int le) {
 
    int dat[101] = { 0 };
    cin >> sun;
    int num;
    for(int i=0; i<1000; i++){
        cin >> num;
        dat[num]++;
    }
 
    int max = -1;
    int index;
    for (int i = 0; i < 100; i++) {
        if (max <= dat[i]) {
            max = dat[i];
            index = i;
        }
    }
 
    cout << "#" << sun << " " << index << endl;
 
}
 
int main() {
    cin >> t;
 
    for (int i = 0; i < t; i++) {
        run(i);
    }
 
    return 0;
}

https://pro.mincoding.co.kr/problem/G4LV26_Three

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

using namespace std;

vector<int> arr;

int main() {
    int n;
    string order;
    int num;

    cin >> n;

    cin.ignore();
    for (int i = 0; i < n; i++) {
        getline(cin, order);

        int a = order.find(" ", 0);

        if (order.substr(0, 4) == "push") {
            num = stoi(order.substr(a + 1));
            arr.push_back(num);
        }

        else if (order == "printLast") {
            int s = arr.size();
            cout << arr[s-1] <<endl;
        }

        else if(order=="pop")
            arr.pop_back();
    }

    return 0;
}

- tree DFS

#include<iostream> // tree dfs
using namespace std;

char name[6] = "KFCMC";
int map[5][5] = {
//  0 1 2 3 4
    0,1,1,0,0,
    0,0,0,1,1,
    0,0,0,0,0,
    0,0,0,0,0,
    0,0,0,0,0,
};

void dfs(int now)
{
    cout << name[now]; // 탐색 순서대로 출력

for (int x = 0; x < 5; x++)
{
    if (map[now][x] == 1)
    {
        dfs(x);
    }
}
}
int main()
{

dfs(0); // 탐색 시작하는 인덱스


return 0;
}

- 그래프 (1번씩 탐색) _ used 사용 !! 1로만 켜주기

#include<iostream> 
using namespace std;

char name[5] = "ABCD";
int map[4][4] = {
    0,1,1,0,
    1,0,1,1,
    0,1,0,1,
    0,0,0,0,
};
int used[4];
void dfs(int now)
{
    cout << name[now]<<" ";
    for (int x = 0; x < 4; x++)
    {
        if (map[now][x] == 1&&used[x]==0)
        {
            used[x] = 1;
            dfs(x);
        }
    }
}
int main()
{
    used[1] = 1;
    dfs(1);  // 시작인덱스
}

- dfs 경로탐색 (출발지 도착지 입력)

#include<iostream> 
using namespace std;

char name[5] = "ABCD";
int map[4][4] = {
    0,1,1,0,
    0,0,1,1,
    0,1,0,1,
    0,0,0,0,
};
int used[4];
char start, dochak;
int startindex, endsindex;
int cnt = 0;
void dfs(int now)
{

// if(now==endsindex)
if (name[now] == dochak)
{
    cnt++;
}
for (int x = 0; x < 4; x++)
{
    if (map[now][x] == 1 && used[x] == 0)
    {
        used[x] = 1;
        dfs(x);
        used[x] = 0;
    }
}
}
int main()
{

    cin >> start >> dochak; // 시작점 도착점
    for (int x = 0; x < 4; x++)
    {
        if (name[x] == start)
        {
            startindex = x;
        }
        if (name[x] == dochak)
        {
            endsindex = x;
        }
    }

used[startindex] = 1;
dfs(startindex);
cout << cnt;
}

- tree bfs

#include<iostream> // tree bfs
using namespace std;

char name[6] = "KFMCC";
int map[5][5] = {
    0,1,0,0,1,
    0,0,1,1,0,
    0,0,0,0,0,
    0,0,0,0,0,
    0,0,0,0,0,
};
struct node {
    int index;
    int level;
};
node queue[10] = { 0,0 };
int head = 0;
int tail = 1;
int main()
{
    while (head != tail)
    {
        node now = queue[head++];  // queue[0].index=0  //  queue[0].level =0;

    cout<<name[now.index];

    for (int x = 0; x < 5; x++)
    {
        if (map[now.index][x] == 1)
        {
            queue[tail++] = { x,now.level + 1 };
        }
    }
    //head++;
}
}

- bfs 그래프 탐색

#include<iostream>  // bfs 그래프 탐색 
using namespace std;
char name[6] = "KMSTY";
int map[5][5] = {
    0,1,1,1,0,
    0,0,1,0,0,
    1,0,0,1,1,
    0,0,0,0,1,
    0,0,0,0,0,
};
struct node {
    int index;
    int level;
};
node queue[100];
int used[5];
int head = 0, tail = 1;
int main()
{
    queue[0] = {1,0}; // 1번 인덱스 부터 bfs 탐색
    used[1] = 1;

while(head != tail)
{
    node now = queue[head++];

    cout << name[now.index] << " ";

    for (int x = 0; x < 5; x++)
    {
        if (map[now.index][x] == 1 && used[x] == 0)
        {
            used[x] = 1;
            queue[tail++] = { x,now.level + 1 };
        }
    }
}

return 0;
}

- 슬라이딩윈도우 (민코딩) https://pro.mincoding.co.kr/problem/SDS_%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9%EC%9C%88%EB%8F%84%EC%9A%B0

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

using namespace std;

int n, w;
vector<int> img;

int sum, mmax, maxin;

void run() {
    img.clear();
    
    sum = 0;
    mmax = -21e8;
    maxin = 0;

    cin >> n >> w;

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

        img.push_back(num);
        if(i<w)
            sum += img[i];
    }

    for (int i = 0; i <= n-w; i++) { //i<n-w시 마지막자리 max 비교를 못함
        if (mmax < sum) {
            mmax = sum;
            maxin = i;
        }
        
        if (i == n - w) break; //마지막자리까지 비교후 sum실행시 오류로 break

        sum += img[i + w];
        sum -= img[i];
    }

}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        run();
        cout << "#" << i + 1 << " "
            << maxin << " " << maxin + (w-1)
            << " " << mmax;
        cout << endl;
    }

    return 0;
}

- 슬라이딩윈도우 (민코딩 예식장서빙)

https://pro.mincoding.co.kr/problem/SDS_%EC%98%88%EC%8B%9D%EC%9E%A5%EC%84%9C%EB%B9%99

-> 원형을 1차원배열로 복사하기

//교수님 코드
#include<iostream>
using namespace std;
int main()
{
    int n = 8;//음식 개수
    int r = 2;//범위 거리
    int arr_temp[] = { 65, 65, 81, 66, 65, 65, 69, 69 };
    int arr[16] = { 0 }; // 0~7 인덱스 원본 8~15 인덱스 까지 복사본

for (int x = 0; x < 8; x++)
{
    arr[x] = arr_temp[x];
    arr[x + n] = arr[x];
}

// 로테이션 준비
// 원하는것 은 : 각 음식이 몇개씩 있는가??  3개 이상이면 땡

int dat[201] = { 0 };
int check = 0;

// 슬라이딩 윈도 해주는데 확인할 구간은
// 2*r +1개 를 확인

for (int x = 0; x < 2 * r; x++)
{
    //2*r개에 대한 처리
    dat[arr[x]]++;
    if (dat[arr[x]] >= 3)
    {
        check = 1;
    }
}

for (int x = 0; x < n; x++)
{
    //2*r 개-> 2*r+1개를 확인

    dat[arr[x + 2 * r]]++;
    // 2*r+1개의  음식에 대한 처리

    if (dat[arr[x + 2 * r]] >= 3) {
        check = 1;
    }
    // 다음 구간에 겹치는 음식만 남기기 위해서

    // 현재 구간의 맨앞 data를 삭제

    dat[arr[x]]--;
}


if (check == 1)cout << "노";
else cout << "예스";

return 0;
}

- TC 부분 실패

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

using namespace std;

int n, r;
vector<int> menu;
int sum, mmax, maxin;

bool run() {
    menu.clear();

    sum = 0;
    mmax = -21e8;
    maxin = 0;


    int dat[200] = { 0 };

    cin >> n >> r;

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        menu.push_back(num);
    }

    for (int i = 0; i <= 2 * r; i++) {
        dat[menu[i]]++;
        if (dat[menu[i]] > 2) return false;
    }

    int s = 2 * r + 1;
    for (int i = 0; i < r; i++) {
        dat[menu[s+i]]++;
        dat[menu[i]]--;
        if (dat[menu[s + i]]>2) return false;

    }

    return true;
}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        if (run())
            cout << "#" << i + 1 << " " << "YES" << endl;
        else
            cout << "#" << i + 1 << " " << "NO" << endl;
    }

    return 0;
}