우선 완전 탐색이라는 것은 대충 감이 왔을 것이다.

완전 탐색을 어떻게 구현할지가 문제이다.

• 법칙 1 : 완전 탐색은 항상 앞에서 뒤로간다. (인덱스 0에서부터 --> 방향으로만 진행한다는 의미)

• 법칙 2 : 인덱스 0에서부터 --> 방향으로만 진행하며, 각 인덱스에서 선택할 수 있는 경우의 수를 생각해보자

-> 이 문제의 경우 각 인덱스에서 선택할 수 있는 경우의 수는 오직 2개이다.

경우의 수가 2개니까 -> go() 재귀 호출을 2번 수행하도록 코드짜면 된다.

• 법칙 3 : 인덱스 idx를 활용해서 로직을 설계한다.

경우 1은 idx와 idx+1의 연산이고, 경우 2는 idx+1 과 idx+2의 연산 후에 idx와 연산을 수행한다.

또한 구간합의 개념이 들어가야한다. 기본은 앞에서부터 구간합이고, 괄호를 만난 경우만 뒤에꺼 연산하고 구간합과 연산한다고 생각하면된다.

2. 코드

#include <bits/stdc++.h>

using namespace std;



int ret = -987654321;
vector<int> num;
vector<char> operand;

int calc(int num1, char op, int num2) {
    switch(op) {
        case '+' : return num1+num2;
        case '*' : return num1*num2;
        default : return num1-num2;
    }
}

void go(int idx, int psum) {
    if(idx == num.size()-1) {
        ret = max(ret, psum);
        return;
    }
    go(idx+1, calc(psum, operand[idx], num[idx+1]));
    if(idx+2 <= num.size()-1 && idx+1 <= operand.size()-1) {
        int tmp = calc(num[idx+1], operand[idx+1], num[idx+2]);
        go(idx+2, calc(psum, operand[idx], tmp));
    }    
}



int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    for(int i=0;i<n;i++) {
        if(i%2==0) {
            num.push_back(s[i]-'0');
        } else operand.push_back(s[i]);
    }

    go(0,num[0]);
    cout << ret;

    return 0;
} 

3. 오답노트

(1) 완탐 재귀함수 go() 미숙 (중요)

완탐 재귀 함수 go() 구현이 미숙하다. 처음에 완탐을 해야함과 go() 재귀함수를 만들어야함은 캐치했다. 그러나 각 idx에서 어떤 경우의 수가 있는지, 어떻게 구현할지가 떠오르지 않았다.

재귀 구조를 잘 이해하고있어야겠다.

• 완탐은 항상 앞에서 뒤로간다

• 앞에서부터 시뮬레이션 돌리면서 각 idx에서 분기되는 경우의 수를 살펴보자
• idx를 활용해서 코드를짠다

위의 3가지를 잊지말자.

뮤탈이 SCV를 공격해서 전부 죽이는데 걸리는 최소 시간을 찾는 문제이다.

시도 1 - 반복문, 재귀 기반 완전 탐색

최악의 경우 몇 번의 공격이 필요할까?

재귀로 구현하는 경우 -> O(6^k) 의 시간 복잡도이다. k는 최악의 경우 21 정도로 예상된다. -> 무조건 시간 초과

시도 2 - 우선순위 큐

priority_queue 로 풀이해보려했는데 테케로 시뮬레이션 해보니 반례가 존재했다

정답 - BFS

결론적으로 위와같이 BFS로 최단 경로 찾기를 활용해서 가능한 모든 경우의 수를 탐색해야한다.

int visited[64][64][64]; // 3차원 배열의 인덱스를 SCV1,2,3의 체력으로 생각한다.

//9,3,1 을 CSV1,2,3의 체력에서 빼는 경우의 수 총 6개 <--BFS에서 dy, dx에 해당한다고 생각하면된다
int diff[6][3] = { 
    {9,3,1},
    {9,1,3},
    {3,9,1},
    {3,1,9},
    {1,3,9},
    {1,9,3}
}; 

struct A {
    int a,b,c;
}; //SCV의 체력을 저장할 구조체로, Queue에 이 구조체를 넣어줄 것이다.

queue<A> q; // bfs 사용할 Queue

int bfs(int a, int b, int c) {
    visited[a][b][c]=1;
    q.push({a,b,c});
    while(q.size()) {
        int a1 = q.front().a;
        int b1 = q.front().b;
        int c1 = q.front().c;
        q.pop();
        for(int i=0;i<6;i++) {
            int na = max(0, a1-diff[i][0]); //na,nb,nc는 인덱스로 사용되므로 0에서 클램핑 해준다
            int nb = max(0, b1-diff[i][1]);
            int nc = max(0, c1-diff[i][2]);
            if(visited[na][nb][nc]) continue; //이미 방문된 지점이면 queue에 들어가있고 6개의 경우의수에대해 자동으로 확인될테니 continue로 무시한다
            visited[na][nb][nc] = visited[a1][b1][c1] + 1; //비용업데이트 
            if(visited[0][0][0]) break; //만약 scv의 체력이 0,0,0 인 지점에 방문되었으면 bfs 종료!
            q.push({na,nb,nc});    
        }
    }
    return visited[0][0][0]-1;    //처음에 visited[a][b][c]를 1로 설정했으니 최종 return값에서는 1을 빼줘야함.
}

위의 방식으로 구현했을때 visited[][][] 로 인해 중복 방문이 제한되므로 시간복잡도는 O(64^3*6) 으로, 약 1570000 정도로 매우 안전하다.

2. 풀이

/*
bfs로 모든 경우의 수에 대해 탐색 수행하자.
그러다가, 0,0,0 도달하면 종료하고 비용 출력
*/

#include <bits/stdc++.h>

using namespace std;

int visited[64][64][64];

struct A {
    int a,b,c;
};

int diff[6][3] = {
    {9,3,1},
    {9,1,3},
    {3,9,1},
    {3,1,9},
    {1,3,9},
    {1,9,3}
};
queue<A> q;

int bfs(int a, int b, int c) {
    visited[a][b][c]=1;
    q.push({a,b,c});
    while(q.size()) {
        int a1 = q.front().a;
        int b1 = q.front().b;
        int c1 = q.front().c;
        q.pop();
        for(int i=0;i<6;i++) {
            int na = max(0, a1-diff[i][0]);
            int nb = max(0, b1-diff[i][1]);
            int nc = max(0, c1-diff[i][2]);
            if(visited[na][nb][nc]) continue;
            visited[na][nb][nc] = visited[a1][b1][c1] + 1;
            if(visited[0][0][0]) break;
            q.push({na,nb,nc});    
        }
    }
    return visited[0][0][0]-1;    
}


int main() {
    int n;
    cin >> n;
    int a[3] = {0,0,0};
    for(int i=0;i<n;i++) {
        cin >> a[i];
    } 
    cout << bfs(a[0],a[1],a[2]);
    return 0;
}

3. 오답 노트

(1) BFS로 완전탐색할 수 있구나..!

BFS로 완전탐색을 수행하는 문제를 처음 풀어봤다.

어렴풋이 완전탐색해야할 것 같긴했는데 BFS로 하는건 떠올리지 못했다.

BFS를 활용해서 완전 탐색이 가능하다

(2) BFS 기반 완전 탐색 -> 시간복잡도 감소

BFS기반으로 완전 탐색하면 반복, 재귀 기반 완전 탐색과 달리 visited 배열이 존재해서 중복 방문이 없다.

시간 복잡도가 그래프(맵)의 크기로 제한되는 효과가 있다. 완탐이 시간복잡도 빡세면 bfs기반 완탐으로 접근해보자.

(3) 최소 비용, 최단 거리, 최소 시간 ---> BFS 기반 최소 비용 찾기 알고리즘

이 문제도 결국은 최소 비용(시간)을 찾는 문제이다.

따라서 BFS로 접근하는 것을 떠올려야한다

문제 요약

불은 4방향 모두로 퍼지고, 지훈이는 4방향 중 하나로 움직인다.

지훈이가 불을 피해서 가장자리에 도달할 수 있으면 가장자리에 도달하는 최단 시간을 출력하고, 불을 피해서 가장자리에 도달할 수 없으면 IMPOSSIBLE을 출력한다.

그 과정에서 벽(#)은 사람도, 불도 통과할 수 없다.

알고리즘

• BFS는 4방향으로 퍼지는 불의 움직임과 동일하다. 불은 4방향으로 1칸씩 퍼진다. BFS도 이와 동일하다. BFS로 그래프를 4방향 탐색하는경우, 4방향으로 1칸씩 퍼지며 가중치를 업데이트한다. 따라서 불의 움직임도, 지훈이의 움직임도 전부 BFS로 표현 가능하다.

• 불을 피해서 도달가능한지 어떻게알까? 지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간 을 만족하면 된다.

• 가장자리임은 어떻게알까? y가 0 || y가 r-1 || x가 0 || x가 c-1 을 만족하면 가장자리인 것이다

• 반례

위의 경우 단순히 지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간 를 적용하면 어떻게될까?

우선 불의 BFS를 거치고나서 벽 안쪽(좌상단) 불에 의한 가중치는 전부 0이다. (벽에 막혀서 불이 방문을 못하니까)

이 상태에서 지훈이의 BFS에서 지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간를 적용하면 벽 안쪽(좌상단) 부분이 모두 continue 되버리는 문제가 발생한다.

따라서 Fire 의 visited[][]는 매우 큰 수로 초기화 해둬야한다. -> int INF = 987654321로 초기화하자.

• 풀이 흐름

불의 위치에서 BFS 수행 -> 지훈이가 BFS 수행 (각 방문에서 불보다 먼저 도달 가능한 위치이면 진행, 아니면 continue로 무시) -> 지훈이의 BFS 계속 반복하다가..가장자리 도달하면 비용 출력하고, 못하면 "impossible" 출력

2. 코드

/*

지훈이가 불 보다 가장자리에 빠르게 도착하면됨 ->  bfs각각 돌려서 지훈이의 비용이 더 작은 가장자리 영역 찾으면됨 

지훈이 bfs돌리기
불 bfs돌리기

순회하면서 지훈이쪽이 비용 더 작은거 벡터에 pushback
가장 작은 비용을 출력 

*/
#include <bits/stdc++.h>

using namespace std;


int INF=987654321;
queue<pair<int,int>> q;
int visited_j[1004][1004], visited_f[1004][1004], r, c;
char a[1004][1004];
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int ret;

//1:jihoon, 0: fire
void bfs_f() {
    while(q.size()) {
        int y,x;
        tie(y,x)=q.front(); q.pop();
        for(int i=0;i<4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= r || nx >= c || ny <0 || nx <0 || visited_f[ny][nx]!=INF || a[ny][nx]=='#') continue;
            visited_f[ny][nx]=visited_f[y][x] + 1;
            q.push({ny,nx});
        }    
    }    
}

void bfs_j(int y, int x) {
    visited_j[y][x]=1;
    q.push({y,x});
    while(q.size()) {
        int y,x;
        tie(y,x)=q.front(); q.pop();
        if(y == r-1 || x == c-1 || y == 0 || x == 0) {
            ret = visited_j[y][x];
            break;
        }
        for(int i=0;i<4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= r || nx >= c || ny <0 || nx <0 || visited_j[ny][nx] || a[ny][nx]=='#') continue;
            if(visited_j[y][x]+1 >= visited_f[ny][nx]) continue;
            visited_j[ny][nx]=visited_j[y][x] + 1;
            q.push({ny,nx});
        }    
    }    
}

int main() {
    pair<int,int> jihoon;
    fill(&visited_f[0][0], &visited_f[0][0]+1004*1004, INF);
    cin >> r >> c;
    for(int i=0;i<r;i++) {
        for(int j=0;j<c;j++) {
            cin >> a[i][j];
            if(a[i][j]=='J') jihoon = {i,j};
            else if(a[i][j]=='F') {
                q.push({i,j});
                visited_f[i][j]=1;
            }
        }

    }
    bfs_f();
    bfs_j(jihoon.first, jihoon.second);
    ret == 0 ? cout << "IMPOSSIBLE" : cout << ret;
    return 0;
}

3. 오답 노트

불의 움직임과 BFS

불의 움직임이 BFS의 동작과 동일함을 생각하지 못했다.

BFS는 4방향으로 퍼지며 비용을 업데이트하낟.

반례 생각

처음에 FIRE의 visited[][]를 0으로 초기화했다가 틀렸다.

위의 경우를 생각하지못했다.

로직이 맞는것같은데도 틀리면 이처럼 반례를 떠올려보자

지훈이도, 불도 움직이는데 불을 피해서 도달 가능한지 어떻게확인할까?

핵심은 지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간 이면 결국 불을 피할수있다는 뜻이다.

이를 확인하기위해서 우선 불에 대해서 bfs돌리고 -> 이후 지훈이에 대해서 bfs돌리며 각 방문마다 위의 조건을 체크해준다.

문제에 주관을 넣지말자.

문제에 불이 하나라는 말이 없다. 불이 하나였으면 좋겠다는 것은 어디까지나 나의 바램이다. 나의 주관을 문제에 넣지말자. 실제로 이 문제도 불이 여러개인 경우가 입력으로 들어오는 문제였다.

방법 1 - 카운팅 배열 활용

어쨋든 동시에 이용시간이 겹치는 횟수 = 필요한 방의 개수 이다. 따라서 이용 시간에 해당되는 경우마다 카운팅배열에 ++ 해주면, 배열의 최댓값이 결국 필요한 방의 개수이다.

코드가 날라갔다..ㅠ

시간복잡도는 O(n) 이다.

방법 2 - 우선순위 큐 활용

사람의 사고 과정을 생각해보자.

우린 가장 일찍 대실이 시작되는 방 부터, 방을 배정해주고 이후에 그 다음 방, 그 다음 방을 배정해준다. 그리고 배정하기전에 항상 대실이 끝난 방이 있는지 확인해준다.

이런 사람의 사고 과정을 그대로 구현하면된다.

• 우린 가장 일찍 대실이 시작되는 방 부터 -> sort로 book_time을 정렬
  • 2차원 벡터도 알아서 오름차순으로 정렬됨
• 방을 배정해주고 -> 우선순위 큐에 해당 방의 대실 마감시간을 넣어줌
• 그리고 배정하기전에 항상 대실이 끝난 방이 있는지 확인 -> 우선순위 큐의 top과 이번에 받을 예약의 시작 시간을 비교해서, top이 시작 시간보다 작으면 이미 대실 마감이니 pop()해줌

이때, 청소 시간이 항상 10분 있으므로 대실 마감시간은 원래 마감시간 + 10 으로 생각해야함.

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;



int get_min(const string & input, string delimiter) {
    auto start=0;
    auto end = input.find(delimiter);
    vector<int> result;
    while(end != string::npos) {
        result.push_back(atoi((input.substr(start, end-start)).c_str()));
        start = end + delimiter.size();
        end = input.find(delimiter, start);
    }
    result.push_back(atoi((input.substr(start)).c_str())); 
    return result[0]*60+result[1];  
}

priority_queue<int, vector<int>, greater<int>> q;
int ret = -1;
int solution(vector<vector<string>> book_time) {
    int answer = 0;

    sort(book_time.begin(), book_time.end());
    for(auto it : book_time) {
        int start = get_min(it[0],":");
        int end = get_min(it[1],":") + 10;
        while(q.size() && q.top() <= start) {
            q.pop();
        }          
        q.push(end);
        ret = max(ret, (int)q.size());
    }

    return ret;
}

시간복잡도는 O(nlogn) 이다.

2. 오답노트

(1) 우선순위 큐 개념과 연결 실패

매번 작은걸 확인해야함은 감 잡았지만..작은 걸 확인한다 -> 우선순위 큐 사용 으로 개념을 연결짓지 못했고, 결국 우선순위 큐를 사용하지 못했다.

다음부터 작은걸 확인해야하는 경우에는 우선순위 큐를 활용해서 풀 수 있을지 꼭 확인해봐야겠다.

(2) 이차원 벡터 sort

처음에 "sort() 해볼까?" 싶었는데 sort로 이차원 벡터도 정렬이 된다는 것을 몰랐다.

vector<vector<int>> 정렬

vector<vector<int>> v = {
    {2, 3},
    {1, 5},
    {1, 2}
};
sort(v.begin(), v.end());

{1, 2}
{1, 5}
{2, 3}

vector<vector<string>> 정렬

vector<vector<string>> v = {
    {"15:00", "17:00"},
    {"09:10", "10:10"},
    {"10:20", "12:20"}
};

sort(v.begin(), v.end());
{"09:10", "10:10"}
{"10:20", "12:20"}
{"15:00", "17:00"}

• 문제: https://school.programmers.co.kr/learn/courses/30/lessons/68645
• 유형 : 구현

이 문제를 처음보고 풀면 진짜 대단한 사람인것같다. (그냥 내가 바보인건가)

크게 두 가지 단계로 풀이하면된다.

1. 2차원 배열에 저 모양 넣기
2. 2차원 배열을 순회하며 return하는 벡터에 push_back 해주기

(1) 2차원 배열에 저 모양 넣기

(1) 우리가 쓰는 2차원 배열은 저런 피라미드 구조를 표현할 수 없다. -> 직각 삼각형으로 표현하자

-> 한쪽 끝을 배열의 0열에 붙여버린다. -> 결과적으로 피라미드 형태가 아니라 위의 사진 처럼 직각 삼각형 형태로 배열에 넣어준다.

(2) 삼각 달팽이 이동 유형은 3가지이다.

아래로 끝까지, 우로 끝까지, 좌상단 대각선으로 끝까지.

중요한 것은 항상 어느 방향이든 채워지지 않은 끝 까지 이동한다는 것이다.

그럼 어디 까지 이동하는지를 알아야한다.

끝을 알려 주기위해 4개의 변수

top : 채워져있지 않은 가장 윗 행 bottom : 채워져있지 않은 가장 아래 행 left : 채워져있지 않은 가장 왼쪽 열 right : 채워지지 않은 가장 오른쪽 열 (왼쪽 변을 벽에 붙인 직각삼각형 형태로 생각했을때)

를 두고, 각 이동에서 이 4개의 변수를 활용해, 행과 열의 범위를 지정해준다.

각 이동의 행, 열 범위를 파악 및 각 이동이 끝나고 top,bottom,left,right를 업데이트 해주면된다.

(3) 언제까지 이동?

삼각달팽이의 움직임을 관찰해보면, n=4인 경우 총 움직임이 4+3+2+1 번 발생한다. -

-> (n(n+1)) / 2 번.

(2) 2차원 배열을 순회하며 return하는 벡터에 push_back 해주기

0이 아닌 값들만 벡터에 넣어준다.

시간 복잡도는 O(n^2) 으로 매우 매우 널널하다.

2. 코드

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define top t
#define bottom b
#define left l
#define right r
#define end e



int top,bottom,left,right,end,num,state;
int arr[1004][1004];
vector<int> solution(int n) { //O(n^2)
    vector<int> answer;
    end = (n*(n+1))/2; top = 0; bottom = n-1; left = 0; right = n-1; num = 1; state = 0;  
    while(num <= end) {
        switch(state) {
            case 0 : for(int i=top; i<=bottom; i++) arr[i][left] = num++;
                left++; top++; state = 1; //left = 1, top = 1;
                break; 
            case 1 : for(int i = left ; i<=right; i++) arr[bottom][i] = num++;
                bottom--; right--; state = 2; // bottom = 4 , right = 4 
                break;
            case 2 : for(int i = 0; i <= bottom-top; i++) arr[bottom-i][right-i] = num++;
                top++; right--; state = 0; //top = 2, right = 3
                break;
        }
    }
    for(int i=0;i<1004;i++) {
        for(int j=0;j<1004;j++) {
            if(arr[i][j]) answer.push_back(arr[i][j]);
        }
    }
    return answer;
}

3. 오답노트

(1) 시뮬레이션 문제 처음 접함

구현 유형중의 대표문제인 시뮬레이션 이다.

시뮬레이션 문제는 이처럼 문제에서 주어진대로 이동 시킨다. 이러한 시뮬레이션 문제를 처음 풀어봐서 어떤 유형인지 감도 못잡았다.

다음에 비슷한 유형있으면 이 문제처럼 top,bottom,left,right 두고 풀이하는거 적용해봐야겠다.

(2) 노력 부족 ?

구현 문제일수도 있겠다는 생각은 들었지만, 규칙이 너무 복잡해보여서 구현으로 풀이하는 시도를 안해봤다.....생각을 더욱 하는 습관을 들여야겠다.

시도 1 - 완전탐색

완전 탐색시 시간복잡도가 O(eCk)인데, 이러면 최악의 경우 1000000C500000 이라 절대 불가..)

시도 2 - 큰 순서로 k개 찾고 -> 무적권 적용

정렬해서 가장 큰거 3개 찾고, 앞에서부터 벡터 순회하면서 무적권 적용 ?

• n=2, k=2 , enemy = [1,1,1,3,4] 이면 3,4 에 무적권 적용인데, 그전에 3라운드에서 죽어버림 -> 잘못된 가설임

옳은 풀이

이후에 어떤 방법 시도해볼지 못 떠올렸다. 답을 보고 풀었다.

우선순위 큐에 enemy의 수를 매 라운드 집어넣는다. 만약 우선순위 큐의 크기가 k보다 크면 -> 그때부턴 무적권으로 처리가 안되고, 내 병사 써서 막아야하므로 -> 우선순위 큐의 요소중 가장 작은 애를 누적한다. (사용한 병사를 누적하는 것임) -> 그 과정에서 만약 누적 사용 병사의 수가 내가 가진 병사의 수 보다 커지면 반복 횟수를 반환한다.

사고 과정은..음...

문제 1. 나는 미래의 값과 비교해서 더 적군 적을때 내 병사로 상대하고, 적군 많을때 무적권 쓰고싶다. 그러나 앞에서부터 순회하면 미래의 값을 모른다. 어떻게할까?

-> 앞에서 부터 순회하며 일단 어떤 자료구조(무적권으로 커버할 적군의 수가 저장된다) 에든 넣어준다. 일단 무적권을 다 쓰는게 무조건 이득이니 자료구조의 크기 > 무적권 갯수가 되면 그 중 최소값을 찾아서 내 병사 쓰자. -> 이렇게하면 가장 작은 적군 오는 라운드에서만 내 병사 쓸 수 있게된다.

문제 2. 최솟값을 어떻게 찾을까? 순회하면서 최솟값 찾으면 전체 시간복잡도는 O(e*k) 이고, 최악의 경우 연산량은 500000000000 = 5천억 이 되버린다. 어떡하지?

-> 우선순위 큐를 사용해서 최솟값 접근에 O(1)이 걸리도록 한다.

2. 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int n, int k, vector<int> enemy)
{
    int sum = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < enemy.size(); i++) //O(N)
    {
        pq.push(enemy[i]); //O(logQ)
        if (pq.size() > k) //O(logk)
        {
            sum += pq.top();
            pq.pop(); //O(logk)
        }
        if (sum > n) return i;
    }
    return enemy.size();
}

시간복잡도는 어떻게 될까?

최악의 경우 for문 내부 코드가 모두 실행되므로, for 문 내부 시간복잡도는 O(logk)이고, 전체를 고려했을때 시간 enemy의 크기를 e라 두면, 시간 복잡도는 O(elogk)이다.

e가 최대 1000000, k가 최대 500000이므로, 최악의 경우 연산량은 1000000log500000 으로 안전하다.

3. 오답 노트

(1) 우선순위 큐 처음 사용해봄

우선순위 큐를 잘 몰랐어서, 우선순위 큐를 사용하면 된다는 것을 몰랐다

(2) 태도 : 가설 시도와 우디르급 태세 전환

여러 가설을 세우고 도전해보며 안되면 우디르급 태세 전환 했어야했는데 그러지 못했다. 어제 너무 바빴었다..ㅠ

(1) next_permuatation(arr+0,arr+베열 크기)

오름차순 순열로 원본을 조작

do {
    ...
    ...
} while (next_permutation(arr+0, arr+배열 크기))

모든 순열을 탐색하니, 시간복잡도는 내부로직 고려 x시 O(n!) 이다.

2. 조합

(1) combi() <--- 4개 이상 뽑는 경우

사용자가 직접 정의해서 구현한다

void combi(int start, vector<int> b) {
    if (b.size() == n) {
        ...
        return;
    }
    for (int i = start + 1; i<n;i++) { //참고로 b의 내용물은 인덱스이다.
        b.push_back(i);
        combi(i, b);
        b.pop_back();

    }
}

대부분의 연산이 if (b.size() == n) {...} 에서 발생한다. 해당 부분이 메인 로직이고, 시간복잡도는 내부로직 고려 x시 O(nCr) 이다.

(2) 반복문 <--- 3개 이하로 뽑는 경우

반복문으로 구현되면, 반복문을 사용하는 것이 좋다

int n = 5;
int k = 3;
int a[5] = {1,2,3,4,5};
int main() {
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            for(int k=j+1;k<n;k++) {
                ...                //로직 (i,j,k는 인덱스임)
                ...                //로직
            }
}

시간복잡도는 내부 로직 고려 X시 O(nCr) 이다.

3. split()

내가 원하는 구분자(delimiter)로 파싱하는 함수

vector<string> split(string const &input, string delimiter) {
    auto start = 0;
    auto end = input.find(delimiter);
    vector<string> result;
    while(end != string::npos) {
        result.push_back(input.substr(start, end-start));
        start = end + delimiter.size();
        end = input.find(delimiter, start);
    }
    result.push_back(input.substr(start));
    return result;
}

4. 중복 요소 제거

sort() 후에 unique()를 사용한다.

vector<int> s = {4,3,3,5,1,2,3};
sort(s.begin(), s.end());
s.erase(unique(s2.begin(), s2.end()), s2.end());

unique()로 원본을 오름차순 정렬 후 중복 보장 x인 첫번째 이터레이터 반환한다. 이후, 해당 이터레이터를 이용해 중복 보장 x인 부분을 erase를 통해 지워버린다.

5. 구간합

psum[] 로 구현한다

(1) psum[]

int a [100004], psum[100004], n, m;
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        psum[i] = psum[i-1] + a[i];
    }
}

이렇게하면 psum[i] 에는 a[1]+a[2]+...+a[i] 가 저장된다. (누적합이 저장된다는 뜻)

완전탐색으로(프루닝 없이도 시간 통과 가능) 최소 치킨 거리를 찾는 문제이다.

도시에 있는 치킨집 중에서 최대 M개 고르라는데, 당연히 M-1개보다는 M개를 골랐을때 치킨 거리가 더 적은 경우의수가 존재한다. *따라서 치킨집은 M개를 골라야한다. *

모든 문제는 처음에 완탐으로 접근하는게 정석이다.

완탐을 하는 경우 연산량은 어떻게될까?

치킨집 M개 뽑는 조합에 대해 전부 확인해줘야하고(13 C m), 각 조합에대해 집 갯수 만큼 확인해줘야하고(2n), 각 집에 대해 치킨집 갯수만큼(m) 조사해줘야한다.

13 C M * 2N * M 이고, 이는 최대 13C6 x 100 x 13 = 2,230,800

으로 매우 널널하다. (조합은 nCr에서 r이 중간값에 가까워질수록 커진다)

(일일이 계산 전부 안해봐서 m의 값에따라 저게 최댓값이 아닐수도 있긴한데 그래봐야 저 정도 숫자 언저리여서 신경안써도됨)

따라서 완탐으로 풀이가 가능하다.

집과 치킨집은 입력받을때 벡터에 따로 저장해둔다. (이렇게 안하면 이차원 배열에 전부 저장해두고 순회하면서 일일이 다 찾아야하는데 그러면 시간 복잡도 측면에서 코스트가 매우 커진다)

이후 combi() 돌려서 m개뽑는 조합 완성되면 그때그때 치킨거리의 최소 합 구하는 함수 돌려서 ret을 업데이트한다.

combi()다 돌리고 마지막에 ret() 출력해준다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> c_list;
vector<pair<int,int>> h_list;
int a[54][54];
int n,m;
int ret = 10000

int get_chicken_dist(vector<int> v) {
     int sum = 0;
     for(pair<int,int> p : h_list) {
         int cnt = 200;
         for(int idx : v) {
             cnt = min(cnt, abs(p.first-c_list[idx].first)+abs(p.second-c_list[idx].second));
         }
         sum+=cnt;
     }
     return sum;
 }     

void combi(int start, vector<int>& v) {
     if(v.size()==m) {
         ret = min(ret, get_chicken_dist(v));
         return;
     }

     for(int i = start+1; i<c_list.size() ; i++ ) {
         v.push_back(i);
         combi(i,v);
         v.pop_back();
     }
 }     

int main() {
    int tmp;
    vector<int> v1={};
    cin >> n >> m;
    for (int i=0;i<n;i++) {
       for (int j=0;j<n;j++) {
           cin >> tmp;
           if(tmp == 1) h_list.push_back({i,j});
           else if(tmp == 2) c_list.push_back({i,j});
       }
    }
    combi(-1,v1);
    cout << ret;
    return 0;
}     

최소값 잡는게 살짝 애매해서 그냥 안전하게 잡았다.

맵의 최대 크기가 50*50 이고, 따라서 집과 치킨집 사이의 최대 거리는 100 이다. 집은 최대 100개이므로 최솟값의 초기값을 10000 보다 크게 설정하면된다.

2. 오답노트

1. 조합 재귀 구현 코드 외우기

void combi(int start, vector<int>& v) {
     if(v.size()==m) {
         ret = min(ret, get_chicken_dist(v));
         return;
     }

     for(int i = start+1; i<c_list.size() ; i++ ) {
         v.push_back(i);
         combi(i,v);
         v.pop_back();
     }
 }  

이상하게 조합의 재귀 구현 코드는 항상 까먹는다. 잘 외워두자

2. 맵에 들어가는게 1,2,3 이렇게 종류가 다양한 경우 -> 벡터에 꼭 넣어주자

이 문제처럼 맵에 들어가는 요소의 종류가 1,2,3 이렇게 다른 경우 벡터에 넣어줘야한다.

뒤에 항상 쟤네들에 대해 별도로 연산이 수행되어야하는 경우가 많기에 벡터에 넣어두면 시간복잡도 측면에서 매우 save가 가능하다. (이렇게 벡터에 안넣어주면 나중에 쟤네 필요할때 이차원 배열을 순회하며 찾아야해서 시간복잡도 측면에서 코스트가 매우 매우 매우 크다)

3. 시간 복잡도 계산 미스

vector에 1,2,3 이런 애들 넣어줘야하는거 까먹고 "아..완탐에 순회에 이러면 연산량 1억넘기는데.." 하며 완탐을 포기했다.

벡터에 넣어주는 테크닉을 잊어서 시간 복잡도 계산도 미스가났고, 완탐 풀이가 안된다고 생각했다.

1,2,3 같은 애들 벡터에 꼭! 꼭! 넣어주자.

모든 경우의 수를 탐색하는 알고리즘으로, (순열 OR 조합) + 로직 으로 구현한다

(1) 사용하는 경우

전체 경우의 수를 다 검사해봐도 연산량 고려했을때 시간 제한을 통과하는 경우

(2) 구현 방법

✍ 반복문

for문 또는 반복문을 이용해 주어진 범위를 모두 검사하는 방법

• 반복문으로 완전 탐색 구현이 가능하면, 재귀말고 반복문을 쓰는것이 좋다 (반복문으로 구현하는 방식의 코스트가 더 적다)

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;

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

✍ 재귀함수

재귀함수를 이용해 주어진 범위를 모두 검사히는 방법

• 반복문보다 코스트가 크다 (시간이 오래 걸린다)
• 재귀로 구현하는 경우
  • 반복문으로 구현하기 힘든 경우
  • 매개변수가 수정되며 반복되는 경우
  • nC1, nC2, nC3 .. 등 이런 경우의 수를 다 생각해야 하는 경우

✍ 재귀함수 구현 - 조합 누적

vector<int> v={1,2,3,54,8,34,54,70,46};
int sum=0;

int go(int idx, int sum) {
    if(idx==n) {
        //검사하거나 등등해서 조건에 부합하면 return 1하고 아니면 return0 하는식으로 누적(카운트)
    }
    return go(idx+1, sum + v[idx]) + go(idx+1, sum); //sum에 고른 수들을 누적
}

• v: 입력받은 숫자들이 저장되어있는 벡터
• idx: 포함 or 불포함 여부를 결정할 인덱스
• idx가 n이되면 조합 1개가 완성된것이므로 적절한 로직을 수행한 후 결과에따라 return한다.

✍ 재귀함수 구현 - 조합 검사

vector<int> v;
int sum=0;

int go(int idx, int sum) {
    if(idx==n) {
          //값 비교해서 최댓값 갱신하거나...등등의 로직
      }
    go(idx+1, sum + v[idx]);
    go(idx+1, sum);
}

완전탐색 - 그래프 완전탐색 (원상복구 기능)

그래프를 완전탐색하는 경우에는 원상복구 기능이 들어가야한다. 이전 탐색이 다음 탐색에 영향을 주면 안되기때문이다.

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[10];   // 인접 리스트
int visited[10];
vector<int> path;

void go(int here) {
    // 현재 경로 출력
    if(path.size() == n) {
        for (int x : path) cout << x << " ";
        cout << "\n";
        return;
    }   

    for (int there : adj[here]) {
        if (visited[there]) continue;

        visited[there] = 1;
        path.push_back(there);

        go(there);

        visited[there] = 0;      // 🔥 백트래킹
        path.pop_back();         // 🔥 백트래킹
    }
}

int main() {
    // 간단한 그래프
    adj[1] = {2, 3};
    adj[2] = {4};
    adj[3] = {4};
    adj[4] = {};

    // 시작 노드 1
    visited[1] = 1;
    path.push_back(1);

    go(1);
}

위의 코드를 보자.

노드에 방문할때마다 visited[]에 방문 표시 및 path 벡터에 원소로 노드를 추가해준다. 이후 go()를 통해 한번 더 재귀를 수행해서 위의 과정을 반복하다가,,

return이 되면 가장 최근에 방문한 노드를 visited[]에 미방문 처리하고, path 벡터에서도 삭제해줌으로써 다음 탐색에 주는 영향을 제거하고, 독립적으로 다음 경로를 탐색할 수 있게된다.

void go(int here) {
    // 현재 경로 출력
    if(path.size() == n) {
        for (int x : path) cout << x << " ";
        cout << "\n";
        return;
    }   

    for (int there : adj[here]) {
        if (visited[there]) continue;

        visited[there] = 1;
        path.push_back(there);

        go(there);

        visited[there] = 0;      // 🔥 백트래킹
        path.pop_back();         // 🔥 백트래킹
    }
}

이 go()의 코드 블럭을 외워두면 편할 것 같다.

백트래킹

완전탐색 + 가지치기(프루닝)

가지치기 (Pruning)

현재 탐색하는 경로가 조건에 부합할 가능성이 없으면 더이상 탐색하지 않고 되돌아가는(Back-Tracking) 방식

기존 완전탐색은 불필요한 부분까지 전부 탐색해버리지만, 가지치기(Pruning)을 적용하면 알고리즘의 효율성이크게 향상된다.

완전 탐색과 백트래킹의 비교

✍ 완전탐색

#include <bits/stdc++.h>
using namespace std;

int n = 4, target = 10;
int arr[4] = {2, 4, 6, 8};
int cnt = 0;

void dfs(int idx, int sum) {
    if (idx == n) {
        if (sum == target) cnt++;
        return;
    }

    // 선택 / 미선택 (모든 경우 탐색)
    dfs(idx + 1, sum + arr[idx]);
    dfs(idx + 1, sum);
}

int main() {
    dfs(0, 0);
    cout << "경우의 수: " << cnt << endl;
}

✍ 백트래킹

#include <bits/stdc++.h>
using namespace std;

int n = 4, target = 10;
int arr[4] = {2, 4, 6, 8};
int cnt = 0;

void dfs(int idx, int sum) {

    // 🔥 Pruning: 이미 target 넘으면 더 볼 필요 없음
    if (sum > target) return;

    if (idx == n) {
        if (sum == target) cnt++;
        return;
    }

    dfs(idx + 1, sum + arr[idx]);
    dfs(idx + 1, sum);
}

int main() {
    dfs(0, 0);
    cout << "경우의 수: " << cnt << endl;
}

백트래킹의 경우 위와 같이 if (sum > target) return;을 통해서 이미 합이 target을 넘으면 더이상 해당 경로의 탐색을 진행하지않고 return해버린다.

오른쪽에 위치한 수 중 처음으로 만나는 큰 수를 출력해야한다. 각 수마다 대응되는 오큰수를 찾는 문제, 즉 짝 짓기를 하는 유형이다.

사실 시간복잡도 조건만 없으면 이중 for문 O(N^2)돌리면 바로 풀리는 문제이다. 그러나 N<=100만이라 O(N^2)알고리즘은 시간 제한을 통과할 수 없다.

짝짓기 유형은 stack으로 푼다. 입력받은 수들을 stack에 push해뒀다가, 대응되는 오큰수를 찾으면 결과 배열 ret에 오큰수를 저장 및 stack에서 pop해준다.

이렇게하면 함수의 수행을 생각해봤을때 O(N)의 시간복잡도가 나온다. (stack에 n번 push 및 stack이 비지 않았을때만 pop하니까)

정답률이 되게 낮은데, 짝짓기는 stack으로 풀이한다는 거이 잘 떠오르지 않아서 그런 것 같다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int n, a[1000004], ret[1000004];
stack<int> s;
int main()
{
    cin >> n;
    fill(&ret[0], &ret[0]+1000004, -1); //O(1)
    for(int i=0;i<n;i++) {//O(N)
        cin >> a[i];
        while(s.size() && a[i] > a[s.top()]) {
            ret[s.top()] = a[i]; //N번 실행*O(1) = O(N)
            s.pop(); //N번 실행 *O(1) = O(N)
        }
        s.push(i);// N번 실행 *O(1) = O(N)

    }
    for(int i=0;i<n;i++) cout << ret[i] << " ";
    return 0;
}

2. 오답노트

(1) 오큰수 찾기 = 짝짓기 유형임을 인지하지 못했다

오큰수 찾기를 짝짓기 유형으로 인지하지 못했다. 문제를보고, 이게 어떤 유형인지 매핑해보는 능력이 많이 부족한 것 같다.

*문제에 직접적으로 짝짓기라는 언급이 없더라도, "어?이거 짝짓기 유형인가?" 하며 내가 알고있는 유형에 매핑해보는 것이 좋을 것 같다. *

(2) 짝짓기는 stack으로 푼다.

짝짓기 문제는 stack으로 풀어야한다는 것을 잊어버렸다..잘 기억해둬야겠다.

(3) 시간복잡도 구하기

for(int i=0;i<n;i++) {//O(N)
        cin >> a[i];
        while(s.size() && a[i] > a[s.top()]) {
            ret[s.top()] = a[i]; //N번 실행*O(1) = O(N)
            s.pop(); //N번 실행 *O(1) = O(N)
        }
        s.push(i);// N번 실행 *O(1) = O(N)

    }

위 코드의 시간 복잡도가 O(N)인지 O(N^2)인지 헷갈렸다.

어찌됐건 시간 복잡도는 수행 횟수로 구한다. s.push(i)는 총 n번 수행된다. s.pop() 은 s.size() 때문에 최대 n번 수행된다.

따라서 (반복문 고려해서) 빅 오 표기법으로 나타내면 둘다 O(n) 이므로, 위의 코드의 시간 복잡도는 O(n) 이다.

이때까지 시간복잡도는 거의 공식처럼 구했는데, dfs도 그렇고 이렇게 코드의 의미, 흐름을 읽어서 시간 복잡도를 구해야할때도 있다. 시간복잡도가 애매할때는 이렇게 코드의 의미, 흐름을 읽어서 시간복잡도를 구해보자.

Tree에서 특정 노드를 삭제했을때 리프 노드의 개수를 구하는 문제이다.

DFS를 통해 트리 순회가 가능하므로, 루트 노드에서부터 시작해서 트리를 순회한며, 삭제하는 노드를 만나면 인접 리스트 순회 과정에서 continue로 무시해주면 된다.

이게 기본적인 컨셉이고,,구현 과정에 몇 가지 주의점이 존재한다.

(1) 삭제된 노드로 인해서 새롭게 리프노드가 되는 노드들이 존재한다 -> child 변수를 통해 continue처리되는 애들을 제외한 각 노드의 자식 노드 갯수를 카운트한다. 만약 인접리스트 순회가 끝나고도 child가 0이면 리프노드이므로 1을 return해준다.

(2) 루트 노드가 항상 0번 노드인것은 아니다.

문제 어디에도 루트 노드가 항상 0번 노드라는 말은 존재하지 않는다. 따라서 문제에 나와있는대로 -1을 입력받은 경우, 해당 번호를 루트노드로 인식하는 것이 적절하다.

(3) 카운트를 누적해야한다. 이런류의 그래프 탐색을 통해 카운트하는 문제는 int형 dfs를 설계하여 지역 변수 cnt를 두고 cnt+=dfs(here)로 매번 재귀호출을 수행하면 편리하게 카운트할 수 있다.

(4) 트리 순회에는 visited[] 배열이 필요없다. root부터 tree 순회를 시작하면 아래로 점점 내려가므로 같은 노드를 절대로 반복할 수 없다. 그래서 visited[]배열이 따로 필요없다.

(5) 시간복잡도는 트리 순회이므로 평균 O(n)이다.

1. 풀이 (1)

#include <bits/stdc++.h>

using namespace std;
vector<int> a[51];
int del;
int dfs(int from) {
    int cnt=0;
    int child = 0;
    for(int here: a[from]) {
        if(here == del) continue;
        child++;
        cnt+=dfs(here);
    }
    if(child==0) return 1;
    return cnt;
}
int main() {
    int n,in,root;
    cin >> n; //5
    for(int i=0;i<n;i++) {
        cin >> in; //5
        if (in == -1) { root = i; continue; } 
        a[in].push_back(i);
    }
    cin >> del;
    if(del==root) {
        cout << 0; return 0;
    }
    cout << dfs(root);
    return 0;
}

2. 오답 노트

(1) 반례를 충분히 생각해보지 못했다.

삭제된 노드로 인해서 새롭게 리프노드가 되는 노드가 존재한다. 그러나 이번에도 공개된 테케만 해보고, 히든 테케에 대해서 생각해보지 못했다. 히든 테케를 꼭꼭꼭꼭 생각해보자.....

(2) 루트 노드가 항상 0번 노드인것은 아니다.

공개 테케만보고 루트 노드가 항상 0이라 생각했다. 문제에서도 -1이 루트노드라 했으므로, 문제에 입각해서 문제를 해석할때 내 주관을 담지않도록 노력해야겠다.

(3) 트리 순회에는 visited[] 배열이 필요없다.

트리를 dfs로 순회하면 항상 아래 방햐응로 내려가므로 절대 같은 노드를 재반복할 일이 없다. 따라서 노드 방문 정보를 저장하기위한 visited[] 배열이 필요없다.

DFS를 이용해 테두리를 제거하는 문제이다.

(1) 가장 바깥쪽은 전부 치즈가 존재할 수 없는 영역이라는 조건은 왜 주어졌을까 ?

이 문제에서 특이한점은 가장 바깥쪽은 전부 치즈가 존재할 수 없는 영역이라는 것이다. 왜 이런 조건을 주었을까? 이 조건 덕분에 우리는 어디서 DFS를 시작해야할지 찾지 않아도된다. 이조건 덕분에 가장 가쪽 영역 어디에서나 DFS를 호출하면 자동으로 연결된 컴포넌트를 순회하기때문이다.

-> (0,0)에서 시작하여 DFS를 수행하면 치즈 바깥쪽을 순회할 수 있다.

(2) DFS의 본질은 연결된 컴포넌트의 순회이다.

DFS는 재귀적으로 연결된 컴포넌트를 순회하는 로직이다. 우리는 DFS를 통해 치즈 바깥쪽 부분을 순회할 수 있다. 이때 4방향 탐색을 할텐데, 필연적으로 치즈의 테두리(치즈가 공기와 접하는 부분)를 방문하게된다. 그렇다면 테두리의 좌표만 따로 뽑아낼수 있지 않을까? -> 각 방문마다 방문 처리후에 a[][]가 1이라면 치즈의 테두리이므로 vector에 넣어주자

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int n,m,ret,cnt;
int a[104][104];
int visited[104][104];
vector<pair<int,int>> v;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};

void dfs(int y, int x) {
    visited[y][x]=1;
    if(a[y][x]) {
        v.push_back({y,x});
        return;
    }
    for(int i=0;i<4;i++) {
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx]) continue;
        dfs(ny,nx); 
    }    
}

bool is_1_exist() {
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(a[i][j]==1) return true;
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> a[i][j];
        }
    }
    while(is_1_exist()) {
        fill(&visited[0][0],&visited[0][0]+104*104, 0);
        dfs(0,0);
        for(pair<int,int> p: v) {
            a[p.first][p.second] = 0;
        }
        cnt = v.size();
        ret++;
        v.clear();
    }
    cout << ret << '\n' << cnt;
    return 0;
}

2. 오답노트

(1) DFS의 본질은 그래프의 순회이다

DFS는 연결된 컴포넌트를 순회한다. 이를 잘 생각해보면, 당연히 그 과정에서 치즈이 바깥 테두리를 방문하므로, 치즈 바깥 테두리의 좌표를 알아낼 수 있다.

이렇듯 DFS문제인데 단순 DFS로 안풀리는 문제는 꼭 DFS과정을 시뮬레이션해보며, 그 DFS 과정에서 내가 찾고자하는 노드가 방문이 되는지를 생각해보는 것이 중요하다.

만약 DFS과정에서 방문이 이뤄진다면, DFS함수를 조금만 수정하면 문제를 풀 수 있다.

이 문제는 3가지 단계로 풀면된다

(1) 벽을 3개 세우기 (2) DFS 나 BFS로 바이러스 퍼뜨리기 (3) 안전영역 카운트하기

N,M이 모두 최대 8이다. 그렇기때문에 최악의 경우, 공간은 최대 64개이다.

64C3으로 조합을 통해 벽을 세우면 -> 21504번 반복 (이때 중요한 점은, 벽은 바이러스와 벽이 없는 곳에만 세울 수 있다. 즉, 현재 맵 사응로 0인 부분에만 벽을 세울 수 있다)

각 반복마다 DFS나 BFS로 바이러스 퍼뜨리면 -> 64번 반복 안전 영역 카운트하면 -> 64번 반복

총 반복 횟수는 21504*(64+64) = 2,752,512 로 연산량은 충분하다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int a[8][8];
int visited[8][8];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int n,m;
vector<pair<int,int>> virus_list;
vector<pair<int,int>> wall_list;

void dfs(int y, int x) {
    visited[y][x]=1;
    for(int i=0;i<4;i++) {
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if(visited[ny][nx]) continue;
        if(a[ny][nx]==0) dfs(ny,nx);
    }
    return;
}

int main() {
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> a[i][j]; //연구소 초기 모습을 2차원 배열에 저장
            if(a[i][j]==2) virus_list.push_back({i,j});
            else if(a[i][j]==0) wall_list.push_back({i,j});
        }
    }
    int ret=-1; //MAX찾기위해 결과값의 초기값을 -1로 설정
    for(int i=0;i<wall_list.size();i++) {//O(64C3*(4*64))
        for(int j=i+1;j<wall_list.size();j++) {
            for(int k=j+1;k<wall_list.size();k++) {
                int cnt=0;  //안전 영역을 카운트할 카운트 변수
                fill(&visited[0][0], &visited[0][0]+64, 0); //visited를 초기화
                a[wall_list[i].first][wall_list[i].second]=1;
                a[wall_list[j].first][wall_list[j].second]=1;
                a[wall_list[k].first][wall_list[k].second]=1;//a에 벽 3개 세우기
                for(int p=0;p<n;p++) {
                    for(int q=0;q<m;q++) {
                        if(!visited[p][q] && a[p][q]==2) dfs(p,q);
                    }
                }//전염병 다 퍼뜨려서 2로 채움
                for(int p=0;p<n;p++) {
                    for(int q=0;q<m;q++) {
                        if(a[p][q]==0 && !visited[p][q]) cnt++; //0인애들 카운트
                    }
                }
                ret = max (ret, cnt);
                a[wall_list[i].first][wall_list[i].second]=0;
                a[wall_list[j].first][wall_list[j].second]=0;
                a[wall_list[k].first][wall_list[k].second]=0;
            }
        }
    }  
    cout << ret;
    return 0;
}

a[][]를 입력 받을때 바이러스가 존재하는 곳과 벽을 세울 수 있는(값이 0인) 지점들을 vector에 넣어서 따로 관리한다.

벽을 세울 수 있는 지점들이 저장된 wall_list 이름의 vector에서 3중 for문으로 3개를 뽑는 조합을 만든다.

각 조합에 대해서 DFS로 a[][]가 0인 노드들을 순회하며 바이러스가 퍼뜨려진 곳은 visited[][]에 1로 표시한다.(=바이러스를 퍼뜨리는 행위)

이후, 이중 for문으로 그래프를 순회하며 a[][]가 0이고, visited[][]가 0인 지점들을 찾고나서 이전에 세웠던 벽 3개를 원상 복귀 시킨다.

2. 오답 노트

(1) 거의 다 맞았는데..벽세우기 실수

기존 벽이 존재하는 지점에는 벽을 세우지 못한다는 것을 인지했는데 바이러스가 존재하는 지점에 벽을 세울 수 없다는 것을 깜빡하고 실수해서 틀렸다.

(2) 기존 코드의 비효율적 부분들

1. 기존 코드에는 그래프 원본을 저장하는 2차원 배열 1개, 각 반복마다 사용하는 오염될 2차원 배열 1개를 만들어서 매 반복마다 원본 2차원 배열을 deep copy해서 사용해서 비효율적이었다. 개선된 코드에서는 배열을 1개만 사용하고 매번 원상복구 해주는 식이라서 효율적이다

2. 기존 코드에서는 전염병의 방문을 a[][]를 2로 만듦으로써 표시했다. 그러나 잘 생각해보면 어차피 visited[][]로 전염병이 퍼진 곳은 확인이되기에 굳이 a[][]를 2로 만들어줄 필요가 없었다. 개선된 코드에서는 vistied[][]로 전염병이 퍼진 곳을 식별하고 a[][]는 따로 건들이지 않으므로 효율적이다.

(3) 벽 3개 세우기. 조합 어떻게 구현?

3중 for문으로 조합을 구현하는 것 까지는 떠올렸고, 기능 자체는 동작했지만 매우매우 비효율적이었다.

개선된 코드에서는 vector에 벽을 세울 수 있는 후보지들을 pair<int,int> 형태로 저장해두고 vector의 size로 index 범위를 구하여, 이를 기반으로 3중 for문을 돌려서 조합을 구현한다. 이 방식이 훨씬 더 직관적이고 코드 가독성도 좋다.

다음부터 이런식으로 2차원 여러개중에 3개를 골라야하는 경우 vector<pair<int,int>>에 좌표들을 저장해두고 vector의 index 중 3개를 뽑는 방식을 활용해야겠다.

괄호 검사 문제인데 종류가 2개이다.

괄호가 아니라면 무시하고, 괄호인 경우에 대해서만 처리해주면된다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    while(1) {
        stack<int> st;
        getline(cin,s);
        bool stop = 0;
        if(s==".") break;
        for(char c:s) {
            if(c=='(' || c=='[') st.push(c);
            if(c==')') {
                if(!st.empty() && st.top()=='(') st.pop();
                else {
                    stop = 1; break;
                }
            } else if(c == ']') {
                if(!st.empty() && st.top()=='[') st.pop();
                else {
                    stop = 1; break;
                }
            }

        }
        (st.empty() && !stop) ? cout << "yes\n" : cout << "no\n"; 
    }
    return 0;
}

2. 오답 노트

(1) 조건문에 구멍이 생겼다

조건문을 치밀하게 설계하지않아서 빈틈이 생겼고, 거기서 오류가 발생했다.

그냥 단순하게

            if(c=='(' || c=='[') st.push(c);
            if(c==')') {
                if(!st.empty() && st.top()=='(') st.pop();
                else {
                    stop = 1; break;
                }
            } else if(c == ']') {
                if(!st.empty() && st.top()=='[') st.pop();
                else {
                    stop = 1; break;
                }
            }

위와 같이 모든 경우의 수에 대해 (마치 switch문 처럼) 조건문을 작성하는 방식이 실수할 확률을 감소시킬 수 있다.

괄호 검사는 대표적인 stack을 활용해서 풀이하는 문제이다.

(는 stack에 저장해두고 )를 만나면 stack이 비어있지 않은 경우(=stack에 (가 존재하는 경우) pop() 해주면된다.

그렇게해서 최종 stack이 비어있으면 올바른 괄호이고, stack이 비어있지 않으면 올바르지 않은 괄호이다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    int T;
    cin >> T;
    while(T--) {
        stack<char> st;
        cin >> s;
        for(char c:s) {
            if(c=='(') st.push(c);
            else if(!st.empty()) st.pop();
            else {
                st.push(c); break;
            }
        }
        if(st.size()) cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}

2. 오답노트

(1) stack 관련 함수 까먹지말자

stack<int> st; //stack 선언 -> 비어있는 stack이 생성됨
st.pop();//stack의 top에 위차한 요소 삭제
st.push(); //stack 요소 삽입(top에 위치하게됨)
st.empty(); //stack이 비어있으면 1을 반환
st.size(); //stack의 size 반환

stack은 지역 변수와 다르게 함수내에서 선언해도 비어있는 상태로 초기화된다.

(2) 로직

처음에는 )를 만나면 stack의 top이 (인지를 확인하고 st.pop()을 수행했다.

그러나 stack에는 항상 (만 넣으므로 top이 (인지 확인할 필요 없이 stack이 empty가 아닌지만 확인해주면된다.

만약 stack이 empty인데 )를 만나면 올바르지 않은 괄호이므로 stack에 push후 바로 break 한다.

이 문제는 666이 들어가는 수 중에서 n 번째로 작은 수를 찾는 문제이다.

처음에 조합,순열 이런 느낌으로도 풀어보려했으나, 잘 떠오르지 않았다.

이 문제를 잘보면 N<=10000 이다. 따라서 내가 찾는 수는 아무리 커도 6660000 안에서 전부 해결된다.

이정도 수면 1부터 6660000까지 모든 수를 순회하며 666을 포함하는지 확인해봐도 시간복잡도 측면에서 문제가 없을듯보인다.

이런 문제는 무식하게 풀어야한다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    int cnt;
    cin >> cnt;
    int i;
    for(i=0;i<6660000; i++) { //O(6660000*3*S)
        if(to_string(i).find("666") != string::npos) cnt--;
        if(cnt==0) break;
    }
    cout << i;


    return 0;
}

시간복잡도는 최악의 경우 O(666000003S)인데 S(to_string()으로 문자열로 바꾼 숫자의 길이)는 매 반복마다 변한다.

그러나 S=7로 둬도 1.2억이므로,,실제 연산량은 1억 이하일 것으로 보인다. (만약 시간초과 뜨면 다른 방법으로 풀이하면된다. 연산량이 1억 이하일 것으로 보이거나, 간당간당해보이는 경우라면 충분히 시도할만한 가치가있다)

아마 제출하면 시간 초과가 뜨지않을 것이다.

2. 오답 노트

(1) 범위는 파악했지만 전부 순회할 생각을 못했다

문제를 보고 내가 찾는 수는 아무리 커도 6660000 안에서 전부 해결됨은 파악했지만, 얘를 전부 순회할 생각을 하지못했다.

최대가6660000 정도의 수라면 모든 수를 순회하는것이 충분히 가능하다. 다음 부터는 모든 수를 순회하며 찾는것이 가능한지를 가장 먼저 떠올려야겠다.

무식한 풀이가 최고로좋다. 다른 고차원적인 풀이를 찾기전에 무식하게 가능한 범위를 전부 순회하면서 찾는 풀이를 가장 먼저 떠올려야한다.

사고 순서 : 가능한 범위 전부 순회하면서 찾기 -> 안되면, 다른 풀이 생각해보기

1팀 VS 2팀 경기의 득점 정보를 입력받고, 이를 기반으로 각 팀이 몇분, 몇초 동안 승리를 유지하고 있었는지를 출력하는 문제이다.

이 문제의 포인트는 3가지이다.

(1) scnaf()로 시간, 분 나누어 입력받기 (2) 분:초 형식의 시간 계산시 분*60+초 로 가장 작은 단위로 통일하여 계산하기 (3) %02d 형식지정자를 활용해서 2자리 분:2자리 초 형식으로 출력하기

위의 포인트를 잘 알고있으면 문제를 쉽게 풀 수 있다.

1. 풀이

 #include <bits/stdc++.h>

using namespace std;
int cnt_1; // 1
int cnt_2; // 2
int time_1;
int time_2;

int main() {
    int n,t, m, s; 
    scanf("%d", &n); //3
    int prev_time = -1 ;
    while(n--) {

        scanf("%d %d:%d", &t, &m, &s);
        int curr_time = 60*m+s;
        if(prev_time != -1 && cnt_1 != cnt_2) {
           int diff_time = curr_time-prev_time;
           if(cnt_1 > cnt_2) time_1+=diff_time;
            else time_2+=diff_time;
        }
        if(t==1) cnt_1++; 
        else cnt_2++;
        prev_time = curr_time; // 31:30
    }
    if(cnt_1!=cnt_2) (cnt_1 > cnt_2) ? time_1+=48*60-prev_time : time_2+=48*60-prev_time;
    //cout << get_time_out(time_1) << '\n' << get_time_out(time_2);
    printf("%02d:%02d\n%02d:%02d", time_1/60, time_1%60, time_2/60, time_2%60);

    return 0;
}

2. 오답 노트

(1) scanf() 사용할 생각을 못했다.

문제와 같이 입력,출력 조건이 까다롭고, string으로 받아서 parsing하기 번거로운 경우에는 scanf()를 적절한 형식 지정자와 함께 사용하는것이 훨씬 편하다.

(2) 시간이 2가지 단위의 혼합(분:초)으로 주어질 경우 가장 작은, 초 단위로 통일하자

이 문제에서는 시간이분:초(2가지 단위의 혼합)로 주어진다. 이런 경우 계산의 편리성을 위하여 초로 시간의 단위를 통일하고 전부 계산한 다음에 나머지 연산, 모듈러 연산을 통해 값을 출력하는 것이 효율적이다.

팩토리얼 문제는 수가 기하급수적으로 커지기때문에 항상 자료형, 입력 범위를 잘 봐줘야한다.

이 문제는 팩토리얼 문제인데, 심지어 입력도 <= 10억 조건이 걸려있다.

O(logN)의 알고리즘만 사용이 가능하다.

N!이 약수로 10을 몇개 가지는지 찾으면 N!뒤에 0이 몇개 있는지 찾을 수 있다. 10=2*5 이므로 N!이 약수로 2와 5를 각각 몇개 가지는지 찾아야한다.

10!은 1 2 3 4 5 6 7 8 9 10 으로 이루어져있고, 2를 8개 약수로 가진다.

잘 생각해보면 이는 10/2 + 10/2*2 + 10/2*2*2 이다.

마찬가지로 약수로 5를 몇개 가지는지 찾아주면되고,

둘 중 최솟값을 출력해주면된다

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t,n;
    cin >> t;
    while(t--) {
        cin >> n;
        int cnt_2=0;
        int cnt_5=0;
        for(int i=2;n>=i;i*=2) {
            cnt_2+=n/i;
        }
        for(int i=5;n>=i;i*=5) {
            cnt_5+=n/i;
        }        
        cout << min(cnt_2, cnt_5) << '\n';
    }


    return 0;
}

2. 느낀 점

(1) 아이디어 떠올리기

이 문제의 아이디어는 사실 시간복잡도를 기반으로 떠올리는 방법 밖에 없을 것 같다. 사용 가능한 알고리즘의 시간복잡도가 O(logN)이다.

O(logN)이면 어떤 수가 계속 곱해지며, 그 값이 N보다 작은 동안 반복을 수행하는 것이다.

예를들어 아래와 같다.

for(int i=2;n>=i;i*=2) {
            cnt_2+=n/i;
        }

시간복잡도를 기반으로 알고리즘을 떠올리는 것도 생각해보자.

n!이 k를 몇개 약수로 가지는지 확인하는 방법을 가능하면 외워두는 것도 좋을 것 같다.

구현 문제이다. n줄에 걸쳐 소문자+숫자를 입력받고 그중에 숫자만 추출(앞에 붙은 0은 생략)해서 비내림차순으로 출력하는 문제이다.

처음에 그냥 "걍 대충 아스키코드 비교로 숫자 추출하고 순회하면서 0제거 해서 벡터에 넣어서 sort()조지면 돼지않을까?" 하고 접근했는데 주어진 테케는 다 통과했음에도 자꾸 오답이 나왔다.

이 문제의 핵심은 히든테케이다.

1. 입력은 1줄에 최대 100글자이다. 각 줄은 최대 100글자이다 -> int는 10자리 숫자를, long long은 19자리 숫자를 표현할 수 있다. -> 100글자는 정수 자료형으로 절대 표현불가 -> string으로 숫자를 저장해야한다. -> vector<int>가 아니라 vector<string>을 써야하고, sort() 사용시 기본 정렬또한 아스키코드 기준으로 수행해줘야한다.

2. sort() 사용자 정의 비교함수 cmp 앞에서 설명했듯이 아스키코드 기준으로 비교해야하는데, 반례가 존재한다. "1111111" 과 "92" 를 아스키코드 기준으로 비교(sort()의 기본 오름차순 정렬 방식)하면 앞에서부터 아스키코드 비교하니까 "92"가 "1111111"보다 뒤에 배치된다. 이는 문제에서 주어진 출력 규칙에 어긋나므로 사용자 정의 cmp를 통해 string의 size가 동일한 경우는 그대로 오름차순으로, size가 다른 경우는 size더 큰 애를 뒤에오도록 해야한다.

3. 효율적인 0 제거 방식

while(s.size() && s[0]=='0') {
        s.erase(0,1);
    }

를 통해서 쉽게 숫자 앞의 0을 제거해줄 수 있다. (인덱스에 접근하기전에 항상 해당 인덱스가 존재하는지 size()로 가장 앞에서 확인해줘야함을 잊지말자)

연산량 대충 따져봤을때 1줄당 50000~100000 언저리로 보인다

1. 풀이

#include <bits/stdc++.h>

using namespace std;

string input, tmp;

vector<string> ret; //43,

bool cmp(string s1, string s2) {
    if(s1.size()==s2.size()) {
        return s1 < s2;
    } else {
        return s1.size() < s2.size();
    }


}
string erase_zero (string s) {
    while(s.size() && s[0]=='0') {
        s.erase(0,1);
    }
    tmp="";
    if(!s.size()) return "0";
    return s;
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        cin >> input;
        for(char c:input) {
            if(c >= '0' && c <='9') {
                tmp+=c;
            } else if(tmp.size()) ret.push_back(erase_zero(tmp));
        }
        if(tmp.size()) {
            ret.push_back(erase_zero(tmp));
         }
    }
    sort(ret.begin(), ret.end(), cmp);
    for(string s:ret) {
        cout << s << '\n';
    }
    return 0;
}

2. 오답 노트

(1) 문자열 대소 비교

문자열 대소 비교 -> 앞에서부터 아스키코드가 누가 더 큰지 비교한다.

(2) 사용자 정의 비교함수 cmp. 앞에꺼, 뒤에꺼 순서

bool cmp(string s1, string s2) {
    if(s1.size()==s2.size()) {
        return s1 < s2;
    } else {
        return s1.size() < s2.size();
    }   
}

return문에서 왼쪽에 있는 애가 정렬 결과 앞에 있을 애를 의미하고, 오른쪽에 있는 애가 정렬 결과 뒤에 있을 애를 의미한다.

(3) 히든 테케를 또 생각안해보고 방심하고 넘어갔다.

히든테케를 떠올릴때 그냥 문제에서 주어진 입력의 최소,최대 or 있거나 없거나를 떠올려보면된다.

한 줄에 최대 100글자이고, 전부 숫자인 경우를 떠올려봤으면 정수 자료형으로는 절대 안되고 무조건 string 써야한다는 것을 떠올렸어야하는데, 방심하고 넘어가서 떠올리지 못했다.

입력의 범위와, 범위의 최소, 최대인 경우의 경우의 수를 꼭 생각해보기

CubeMX의 MAX_PRIORITEIS 설정을 통해 사용할 Task 우선순위의 범위를 설정할 수 있다.

2. Task 생성

BaseType_t xTaskCreate( TaskFunction_t pvTaskCode,
 const char * const pcName,
 unsigned short usStackDepth,
 void *pvParameters,
 UBaseType_t uxPriority,
 TaskHandle_t *pxCreatedTask );

• pvTaskCode : Task 함수
• pcName : Task 함수의 이름
• usStackDepth : Stack에 넣을 수 있는 word(4Byte) 단위 데이터 개수
• pvParameters : Task에 전달할 파라미터
• uxPriority : Task 우선순위
• pxCreatedTask : Task 핸들 (Task 식별, 접근할때 사용)

3. Task 삭제

#include “FreeRTOS.h”
#include “task.h”
void vTaskDelete( TaskHandle_t pxTask );

• pxTask : 삭제할 태스크 핸들
  • 인자로 NULL을 전달하면 자기 자신을 삭제할 수 있다.

4. Task 우선 순위 변경

#include “FreeRTOS.h”
#include “task.h”
void vTaskPrioritySet( TaskHandle_t pxTask, UBaseType_t uxNewPriority );

• pxTask : 변경하고자하는 Task의 Handle
  • NULL을 전달하면 자기 자신의 우선 순위 변경 가능
• uxNewPriority : 새로운 우선 순위
• 주의
  • IDLE 태스크의 우선 순위 변경은 불가능하다

5. Task 일시 중단(Suspend)

#include “FreeRTOS.h”
#include “task.h”
void vTaskSuspend( TaskHandle_t pxTaskToSuspend );

• xTaskToSuspend : Suspend 상태로 보낼 Task의 Handle
• Task를 다시 동작시키려면 vTaskResume()을 이용해야함

6. Task 의 실행 재개(Resume)

#include “FreeRTOS.h”
#include “task.h”
void vTaskResume( TaskHandle_t pxTaskToResume );

• pxTaskToResume : Ready 상태로 보낼 Task의 Handle

7. Task를 일정 시간 Block 상태로 보내기

#include “FreeRTOS.h”
#include “task.h”
void vTaskDelay( TickType_t xTicksToDelay );

• xTicksToDelay : Block 상태로 보낼 Tick 단위 시간
  • 내가 Tick Interrupt를 얼마 주기로 설정했냐에 따라 같은 값을 전달해도 동작이 달라진다.
  • 1 Tick의 주기는 FreeRTOSConfig_base.h의 configTICK_RATE_HZ 로 설정한다.
• vTaskDelay( pdMS_TO_TICKS(100) )
  • pdMS_TO_TICKS() 매크로를 활용하면 현재 Tick Interrupt 주기가 얼마이든 인자로 전달한 ms단위 시간만큼을 Tick 단위로 반환한다 <---권장되는 방법
• Running 상태이던 Task를 Block 상태로 보내므로 필연적으로 Context Switch가 발생한다.

8. Task를 내가 원하는 주기마다 Ready로 보내기 (실행 빈도 일정하게 유지)

#include “FreeRTOS.h”
#include “task.h”
void vTaskDelayUntil( TickType_t *pxPreviousWakeTime, TickType_t xTimeIncrement );

• pxPreviousWakeTime :
• xTimeIncrement :

9. 상호 배제

임계 영역 보호를 위한 상호 배제 구현 방법

(1) 공유 변수 사용 X (2) 세마포어 or 뮤텍스 사용 <---------- 가장 추천되고, 안전한 방식. 그러나 남발하면 코드가 늘어나니, 성능 저하 유발

(3) 임계영역에서 인터럽트 일시 중지 -> Tick Interrupt 발생 x -> 스케줄링(Preemptino) 발생 x (4) 공유 변수 사용 O 더라도, Task 1개가 특정 변수 or I/O 장치를 독점적으로 사용하게한다.

(1) 임계영역에서 인터럽트 일시 중지

//임계영역 시작
taskENTER_CRITICAL();
//...임계영역
taskEXIT_CRITICAL();
//임계영역 끝

taskENTER_CRITICAL() 와 taskEXIT_CRITICAL() 사이에서 인터럽트가 일시 중지됨

• 주의
  • 인터럽트 금지 구간에서는 FreeRTOS API 사용하면 안된다.
    • 인터럽트 금지 구간에서 vTaskDelay() 같은 FREERTOS API 사용시 시스템이 멈춰버릴 수도 있다
  • 인터럽트 금지 구간이 길어질수록 -> 스케줄링 동작 X인 시간 증가 -> 시스템의 실시간성이 떨어진다.

10. 문맥 전환 - vPortYieldProcessor()

기존에 실행되던 Task의 레지스터 값을 모두 Stack에 저장 -> 새로운 Task의 Stack에 저장된 레지스터 값을 CPU로 로드 -> 새로운 Task가 실행됨