면빈면빈면빈면빈

[적용한 알고리즘]

유니온 파인드

[아이디어]

유니온 파인드에서 parent를 먹여주는 방식은 상관없었는데, 

일정한 규칙을 부여해줘서 parent가 될 조건을 정해주면 

항상 root 노드에는 친구비들 중 최소값이 저장되어 있을 것이다.

(우선선위 큐 같은 느낌인가?)

[생각의 흐름 / 절차] 

아이디어를 제외하면 유니온 파인드이다.

마지막 : 전부 친구가 될 수 없는 조건은 돈이 초과되는 상황밖에 없으니 조건문으로 분기 나눠주면 됨.

[교훈]

유니온 파인드에서 트리를 만들어가는데

parent를 정해주는데 규칙을 적용하면 (집합) + (또 다른 규칙)을 포함한 트리를 

나타내준다고 생각할 수도 있겠다. 

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

int parent[10001];
int a[10001];

int find(int x){
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y){
    x = find(x);
    y = find(y);

    if (x == y) return;
    //친구비가 더 작은 애가 parent가 될 수 있도록 한다.
    if (a[x] < a[y]) parent[y] = x;
    else parent[x] = y;
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    fill(parent, parent + n + 1, -1);

    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }

    while (m--){
        int x, y;
        scanf("%d %d", &x, &y);
        merge(x, y);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++){
        if (parent[i] == -1){
            ans += a[i];
        }
    }

    if (k < ans) printf("Oh no\n");
    else printf("%d\n", ans);

    return 0;
}

[적용한 알고리즘]

Disjoint-set, 유니온 파인드 (뭐가 맞는 표현인지 잘모름)

[아이디어]

유니온 파인드 문항의 기본 예제

[생각의 흐름 / 절차] 

[교훈]

나중에 크루스칼 알고리즘이나 이런 곳에 많이 쓰이니 잘 익혀두자.

find 함수에서 메모이제이션 같은 느낌이 들어가는 곳이 시간 단축에 큰 도움이 된단다.

<코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1000001
using namespace std;

int p[MAX];
int find(int n){
    if (n == p[n]) return n;
    return p[n] = find(p[n]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);

    if (a == b) return;
    p[a] = b;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i <= n; i++) p[i] = i;

    for (int i = 0; i < m; i++){
        int oper, a, b;
        scanf("%d %d %d", &oper, &a, &b);

        if (oper == 1){
            if (find(a) == find(b)) printf("YES\n");
            else printf("NO\n");
        }
        else merge(a, b);
    }

    return 0;
}

[적용한 알고리즘]

BFS

[아이디어]

아주아주 기본적인 BFS 문제가 3차원으로 확장된거 정도?

[생각의 흐름 / 절차] 

갈 수 있는지 검사해주고 queue에 추가해주면 됨.

[교훈]

3차원이라 pair을 두번 쓸까 아님 구조체를 쓸까

고민했는데 앞으로 좌표 관련된건 구조체로 해주는게 좋을 듯 하다.

<코드>

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef struct {
    int z;
    int x;
    int y;
} cord;

int dirx[] = {1, -1, 0, 0, 0, 0};
int diry[] = {0, 0, 1, -1, 0, 0};
int dirz[] = {0, 0, 0, 0, 1, -1};
int l, r, c;
char building[31][31][31];
bool visited[31][31][31];
int dist[31][31][31];
queue<cord> q;

void bfs(){
    while (!q.empty()){
        int curz = q.front().z;
        int curx = q.front().x;
        int cury = q.front().y;
        q.pop();

        for (int k = 0; k < 6; k++){
            int nx = curx + dirx[k];
            int ny = cury + diry[k];
            int nz = curz + dirz[k];

            if (0 <= nx && nx < r && 0 <= ny && ny < c && 0 <= nz && nz < l){
                if (!visited[nz][nx][ny] && building[nz][nx][ny] != '#'){
                    visited[nz][nx][ny] = true;
                    dist[nz][nx][ny] = dist[curz][curx][cury] + 1;
                    q.push({nz, nx, ny});
                }
            }
        }
    }
}

int main(){
    while (true){
        memset(building, 0, sizeof(building));
        memset(dist, 0, sizeof(dist));
        memset(visited, false, sizeof(visited));

        scanf("%d %d %d", &l, &r, &c);
        if (l == 0 && r == 0 && c == 0) break;

        int x, y, z; //z층 x행 y열
        int ex, ey, ez;

        for (int k = 0; k < l; k++){
            for (int i = 0; i < r; i++){
                scanf("%s", building[k][i]);
                for (int j = 0; j < c; j++){
                    if (building[k][i][j] == 'S'){
                        x = i;
                        y = j;
                        z = k;
                    }
                    if (building[k][i][j] == 'E'){
                        ex = i;
                        ey = j;
                        ez = k;
                    }
                }
            }
        }

        visited[z][x][y] = true;
        q.push({z, x, y});
        bfs();

        if (!visited[ez][ex][ey]){
            printf("Trapped!\n");
        }
        else {
            printf("Escaped in %d minute(s).\n", dist[ez][ex][ey]);
        }
    }

    return 0;
}

[적용한 알고리즘]

BFS

[아이디어]

숨바꼭질이랑 냄새가 비슷하다.

그냥 전형적인 BFS로 보인다. 

[생각의 흐름 / 절차] 

가능한 경우를 큐에 넣어주고, BFS를 실시한다. 

[교훈]

앞서서 4번 정도 틀렸는데, 

dist[goal] = 0 이거나 dist[goal] > t 이면 ANG을 출력하도록 했는데, 

이게 계속 50% 쯤에서 틀렸다고 나오길래 끝내 이유는 찾지 못했다. 

누군가가 알려줬으면 좋겠다.

그래서 bfs를 다 돌리고 정답을 리턴하게끔, 안되면 -1을 리턴하게끔 코드를 수정해줬더니

귀신같이 맞았습니다가 나왔다. 코드의 논리가 맞아도 디테일함이 중요해보인다.

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX 200000
using namespace std;

queue<int> q;
bool visited[MAX];
int dist[MAX];
int n, goal, t;

int getDigit(int n){
    int digit = 1;
    while (n){
        n /= 10;
        digit *= 10;
    }
    return digit / 10;
}

int bfs(){
    while (!q.empty()){
        int cur = q.front();
        q.pop();

        if (dist[cur] > t) return -1;

        if (cur == goal) return dist[cur];

        int nxt_A = cur + 1;

        if (!visited[nxt_A] && nxt_A <= 99999){
            visited[nxt_A] = true;
            q.push(nxt_A);
            dist[nxt_A] = dist[cur] + 1;
        }

        int temp = cur * 2;
        if (temp > 99999) continue;

        int nxt_B = temp;
        nxt_B -= getDigit(temp);

        if (!visited[nxt_B] && cur * 2 <= 99999){
            visited[nxt_B] = true;
            q.push(nxt_B);
            dist[nxt_B] = dist[cur] + 1;
        }
    }
    return -1;
}

int main(){
    scanf("%d %d %d", &n, &t, &goal);
    q.push(n);
    visited[n] = true;
    int result = bfs();

    if (result == -1){
        printf("ANG\n");
        return 0;
    }
    printf("%d\n", result);

    return 0;
}

[적용한 알고리즘]

백트래킹, 재귀, DFS

[아이디어]

바로 전에 풀었던 문제랑 거의 흡사하다.

[생각의 흐름 / 절차] 

전 문제와 거의 동일

[교훈]

지금까지 나왔는 지 안나왔는지에 대한 중복 검사를 어떻게 할까 고민을 좀 했는데

그냥 간단하게 bool을 알파벳 길이만큼 해서 검사해주면 끝이다.

재밌다 재밌어

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int r, c;
int ans = -1;
char map[21][21];
bool visited[21][21];
bool overlap[26];
int dirx[] = {1, -1, 0, 0};
int diry[] = {0, 0, -1, 1};

void dfs(int x, int y, int cnt){
    if (ans < cnt){
        ans = cnt;
    }

    visited[x][y] = true;
    overlap[map[x][y] - 'A'] = true;

    for (int k = 0; k < 4; k++){
        int nx = x + dirx[k];
        int ny = y + diry[k];

        if (0 <= nx && nx < r && 0 <= ny && ny < c){
            if (!visited[nx][ny] && !overlap[map[nx][ny] - 'A']){
                dfs(nx, ny, cnt + 1);
            }
        }
    }

    visited[x][y] = false;
    overlap[map[x][y] - 'A'] = false;
}

int main(){
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++){
        scanf("%s", map[i]);
    }

    dfs(0, 0, 1);
    printf("%d\n", ans);


    return 0;
}

[적용한 알고리즘]

백트래킹, 재귀

[아이디어]

포함이 되는가 안되는가를 이용해서 재귀함수를 짜주면 될 것 같았다.

경우의 수도 2^15 개라 32768 충분하다.

모음 1개 이상 자음 2개 이상도 체크해줘야 하므로,

인덱스가 배열의 끝을 가르키고 있을 때 원하는 결과에 맞는다면 출력해주게끔 하면 될 것이다.

[생각의 흐름 / 절차] 

1. len, n 을 입력 받고 입력 받은 알파벳들을 사전 순으로 정렬을 해준다.

2. 재귀함수에 넘겨줄 인자들은 현재 배열의 인덱스 값, 모음의 개수, 자음의 개수다. 

3. 탈출 조건을 설계 해야한다.

만약 인덱스가 배열의 끝이라면 모음 + 자음이 암호의 길이와 일치하는지 검사, 

그리고 모음과 자음의 개수가 문제의 조건에 맞는지를 살핀다. 

맞으면 걔네들 출력 후 리턴

4. 먼저 선택하는 경우를 고려해준다.

ans에 넣어주려는 애가 자음인지 모음인지 알아야함.

그래서 검사해주고, 상황에 맞게 재귀 호출을 해주면 됨.

5. 넣어주는 경우의 재귀가 끝나면 넣어줬던 문자를 다시 pop 해줘야 다음 암호로 넘어간다.

6. 선택 안하는 경우를 고려해준다. 인덱스+1 만 넘겨주는 거.

[교훈]

넣는 경우에서 넣었다가 빼주는 게 정확히 와닿지는 않았는데, 그림 그려보니 너무 당연했음.

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int len, n;
char arr[16];
char m[] = {'a', 'e', 'i', 'o', 'u'};
vector<char> ans;

void go(int idx, int mo, int ja){
    if (idx == n){
        if (mo + ja == len && mo >= 1 && ja >= 2){
            for (int i = 0; i < len; i++){
                printf("%c", ans[i]);
            }
            printf("\n");
        }
        return;
    }

    //선택하는 경우
    ans.push_back(arr[idx]);
    bool isMo = false;
    for (int i = 0; i < 5; i++){
        if (arr[idx] == m[i]){
            go(idx + 1, mo + 1, ja);
            isMo = true;
            break;
        }
    }
    if (!isMo){
        go(idx + 1, mo, ja + 1);
    }
    ans.pop_back();

    //선택안하는 경우
    go(idx + 1, mo, ja);
}

int main(){
    scanf("%d %d", &len, &n);
    for (int i = 0; i < n; i++){
        scanf(" %c", &arr[i]);
    }

    sort(arr, arr + n);

    go(0, 0, 0);
    return 0;
}

[적용한 알고리즘]

브루트포스, 재귀

[아이디어]

경우의 수가 4^10개니까 다 해봐도 상관없겠다.

[생각의 흐름 / 절차] 

1. 각 동전의 좌표를 알아낸다.

2. 검사해야할 것들을 살펴본다. (탈출 조건)

1) 혹시 옮긴 횟수가 10번을 넘어가지는 않는가?

2) 지금 좌표에서 1개만 떨어지는 상황인가?

2-1) 1개만 떨어지는 상황이면 지금까지 반복했던 횟수를 리턴한다.

2-2) 둘다 떨어진다면 -1을 리턴한다.

3) 가려고 하는 방향에 벽이 있다면? 

4) ans에는 항상 최소가 들어가도록 한다. 

[교훈]

재귀함수는 여전히 나한테 어렵다. 머리가 안좋은건가?

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

char map[21][21];
int n, m;
int x[2], y[2];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, 1, -1};

int go(int x1, int y1, int x2, int y2, int cnt){
    bool out1 = false;
    bool out2 = false;

    if (cnt > 10) return -1;

    if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) out1 = true;
    if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) out2 = true;
    if (out1 && out2) return -1;
    if (out1 || out2) return cnt;

    int ans = -1;

    for (int k = 0; k < 4; k++){
        int nx1 = x1 + dirx[k];
        int ny1 = y1 + diry[k];
        int nx2 = x2 + dirx[k];
        int ny2 = y2 + diry[k];

        if (0 <= nx1 && nx1 < n && 0 <= ny1 && ny1 < m && map[nx1][ny1] == '#') {
            nx1 = x1;
            ny1 = y1;
        }
        if (0 <= nx2 && nx2 < n && 0 <= ny2 && ny2 < m && map[nx2][ny2] == '#') {
            nx2 = x2;
            ny2 = y2;
        }

        int nxt = go(nx1, ny1, nx2, ny2, cnt + 1);
        if (nxt == -1) continue;
        if (ans == -1 || ans > nxt){
            ans = nxt;
        }
    }
    return ans;
}

int main(){
    scanf("%d %d", &n, &m);

    int pos = 0;
    for (int i = 0; i < n; i++){
        scanf("%s", map[i]);
        for (int j = 0; j < m; j++){
            if (map[i][j] == 'o'){
                x[pos] = i;
                y[pos] = j;
                pos++;
            }
        }
    }
    printf("%d", go(x[0], y[0], x[1], y[1], 0));

    return 0;
}

[적용한 알고리즘]

브루트 포스, 재귀

[아이디어]

1. 한칸만 정하고 인접한 3칸만 이동하면 1가지 경우를 제외하고 전부 나타낼 수 있다.

2. 예외 케이스는 따로 처리해준다

[생각의 흐름 / 절차] 

1. 모양을 다해봐야하나? 너무 노가다여서 하기가 싫었다. 모양 간의 공통점을 찾고싶었다.

(ㅗ) 모양을 제외하면 나머지는 인접하게 붙은 4칸의 모양이었다. 

2. 경우의 수를 다 해봐야겠다. 한칸만 정하면 대부분의 경우의 수 표현가능,

나머지 한가지 (ㅗ,ㅜ,ㅓ,ㅏ) 모양은 따로 예외케이스 처리해서 빼줘야겠다.

3. 다음 칸으로 이동할때 dfs와는 동일하게 check 배열에 체크를 해주고,

재귀를 돌고 나올 때 check를 해제해줘야겠다.

-> 그래야 다른 점에서 시작하는 경우를 계산할 수 있으니까.

중복은 생기겠지만, 고려하지 않아도 된다. 어차피 최댓값만 구하면 되니까.

4. 모든 칸마다 반복문을 돌면서 실행해서 최댓값을 정해야겠다.

[교훈]

열심히 예외 케이스 처리하자. 이런 식으로 최대한 같은 걸로 묶고 예외로 빼줘야할 수도 있다. 

<코드>

#include <cstdio>
#include <algorithm>
#define SIZE 501
using namespace std;

int map[SIZE][SIZE];
bool check[SIZE][SIZE];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
int n, m;
int ans = 0;

void tetrimino(int cnt, int curx, int cury, int sum){
    if (cnt == 4){
        ans = max(ans, sum);
        return;
    }

    if (check[curx][cury]) return;

    check[curx][cury] = true;

    for (int k = 0; k < 4; k++){
        int nx = curx + dirx[k];
        int ny = cury + diry[k];

        if (0 <= nx && nx < n && 0 <= ny && ny < m){
            tetrimino(cnt + 1, nx, ny, sum + map[curx][cury]);
        }
    }

    check[curx][cury] = false;
}

int tetrimino2(int curx, int cury){
    int ret = -1;
    int tempSum = 0;
    //세로 방향
    if (curx + 2 < n){
        tempSum = map[curx][cury] + map[curx + 1][cury] + map[curx + 2][cury];
        if (cury + 1 < m){
            int temp = tempSum + map[curx + 1][cury + 1];
            ret = max(ret, temp);
        }
        if (cury - 1 >= 0){
            int temp = tempSum + map[curx + 1][cury - 1];
            ret = max(ret, temp);
        }
    }

    //가로 방향
    if (cury + 2 < m){
        tempSum = map[curx][cury] + map[curx][cury + 1] + map[curx][cury + 2];
        if (curx + 1 < n){
            int temp = tempSum + map[curx + 1][cury + 1];
            ret = max(ret, temp);
        }
        if (curx - 1 >= 0){
            int temp = tempSum + map[curx - 1][cury + 1];
            ret = max(ret, temp);
        }
    }

    return ret;
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            tetrimino(0, i, j, 0);
            ans = max(ans, tetrimino2(i, j));
        }
    }

    printf("%d\n", ans);
    return 0;
}

[적용한 알고리즘]

연산자 끼워넣기와 똑같다. 꽁문제 개이득ㅋ

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

내용

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
vector<int> res;

void go(vector<int> &arr, int idx, int cur, int pl, int mi, int mul, int div){
    if (idx == n){
        res.push_back(cur);
        return;
    }

    if (pl > 0) go(arr, idx + 1, cur + arr[idx], pl - 1, mi, mul, div);
    if (mi > 0) go(arr, idx + 1, cur - arr[idx], pl, mi - 1, mul, div);
    if (mul > 0) go(arr, idx + 1, cur * arr[idx], pl, mi, mul - 1, div);
    if (div > 0) go(arr, idx + 1, cur / arr[idx], pl, mi, mul, div - 1);
}

int main(){
    scanf("%d", &n);
    vector<int> arr(n);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    int oper[4];
    for (int i = 0; i < 4; i++){
        scanf("%d", &oper[i]);
    }

    go(arr, 1, arr[0], oper[0], oper[1], oper[2], oper[3]);

    int ans_min = 1000000005;
    int ans_max = -1000000005;
    for (int x : res){
        ans_min = min(ans_min, x);
        ans_max = max(ans_max, x);
    }

    printf("%d\n%d", ans_max, ans_min);
    return 0;
}

[적용한 알고리즘]

재귀, 브루트포스

[아이디어]

경우의 수를 세보니 다 해볼만 하더라.

[생각의 흐름 / 절차] 

다 해볼만 함 

필요한 인수 정리

제한 조건 써주기

[교훈]

재귀를 더 조져보자.

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
vector<int> res;

void go(vector<int> &arr, int idx, int cur, int pl, int mi, int mul, int div){
    if (idx == n){
        res.push_back(cur);
        return;
    }

    if (pl > 0) go(arr, idx + 1, cur + arr[idx], pl - 1, mi, mul, div);
    if (mi > 0) go(arr, idx + 1, cur - arr[idx], pl, mi - 1, mul, div);
    if (mul > 0) go(arr, idx + 1, cur * arr[idx], pl, mi, mul - 1, div);
    if (div > 0) go(arr, idx + 1, cur / arr[idx], pl, mi, mul, div - 1);
}

int main(){
    scanf("%d", &n);
    vector<int> arr(n);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    int oper[4];
    for (int i = 0; i < 4; i++){
        scanf("%d", &oper[i]);
    }

    go(arr, 1, arr[0], oper[0], oper[1], oper[2], oper[3]);

    int ans_min = 1000000005;
    int ans_max = -1000000005;
    for (int x : res){
        ans_min = min(ans_min, x);
        ans_max = max(ans_max, x);
    }

    printf("%d\n%d", ans_max, ans_min);
    return 0;
}