greentea31's Note

https://www.acmicpc.net/problem/1926

풀이 과정

배열에서 연결 요소의 개수와 연결 요소의 가장 큰 크기를 구하는 문제이다.

연결 요소의 개수와 크기를 구하려면 DFS 혹은 BFS로 모든 배열을 탐색하면 된다.

소스 코드

C++

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

bool vis[501][501];
bool board[501][501];

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int cou = 0;
int n, m;

int bfs(int y, int x) {
    if (vis[y][x] || board[y][x] == 0) {
        return 0;
    }
    cou++;
    int width = 1;

    vis[y][x] = true;
    queue<pair<int, int>> Q;
    Q.push(make_pair(y, x));


    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();

        for (int i = 0 ; i < 4; i++) {
            int nx = cur.second + dx[i];
            int ny = cur.first + dy[i];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (vis[ny][nx] || board[ny][nx] != 1) continue;
            vis[ny][nx] = true;
            width++;
            Q.push(make_pair(ny, nx));
        }
    }

    return width;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> answer_list;
    int board_number;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board_number;
            board[i][j] = board_number;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            answer_list.push_back(bfs(i, j));
        }
    }

    cout << cou << '\n';

    cout << *max_element(answer_list.begin(), answer_list.end());

    return 0;
}

파이썬

import collections
import sys

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
gaesu = 0


def bfs(start_y, start_x, board):
    if vis[start_y][start_x] or not board[start_y][start_x]:
        return 0
    global gaesu
    gaesu += 1
    width = 1
    vis[start_y][start_x] = 1
    queue = collections.deque()
    queue.append([start_y, start_x])

    while queue:
        y, x = queue.popleft()
        for cur in range(4):
            nx = x + dx[cur]
            ny = y + dy[cur]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if not board[ny][nx] or vis[ny][nx]:
                continue
            vis[ny][nx] = 1
            width += 1
            queue.append([ny, nx])

    return width


n, m = map(int, sys.stdin.readline().split())
vis = [[0 for _ in range(m)] for _ in range(n)]
board = []
answer = []
for i in range(n):
    board.append(list(map(int, sys.stdin.readline().split())))

for i in range(n):
    for j in range(m):
        answer.append(bfs(i, j, board))

print(gaesu)
print(max(answer))

https://www.acmicpc.net/problem/1103

풀이 과정

보드에서 해당 칸에 적혀있는 숫자만큼 상하좌우로 이동이 가능할 때, 최대 몇 번 이동이 가능한지 구하는 문제이다.

(A, B)라는 칸에서 상하좌우로 이동해봤더니 4번 이동이 가능했다고 하자. 그러면 (C, D)라는 칸에서 (A, B)라는 칸으로 이동했을 때, 다시 상하좌우로 이동해보면서 몇 번 이동이 가능한지 다시 구할 필요 없이, 예전 방문 때 4번 이동이 가능했다고 저장한 걸 꺼내서 쓰면 1 + 4로 (C, D) 기준 5번 이동할 수 있음을 알 수 있다.

DFS로 특정 칸수에서 몇 번 이동이 가능한지 구하고, 추후 이 점을 다시 방문했을때 다시 DFS로 계산할 필요 없이 이동 횟수를 꺼내서 기억할 수 있도록 해당 칸의 배열에 최대 이동 가능 횟수를 적어서 효율적으로 문제를 해결할 수 있다.

소스 코드

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

bool visit[50][50];
int dp[50][50];
int board[50][50];
int N, M;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int DFS(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= M || board[x][y] <= 0) return 0;
    if (visit[x][y]) {
        cout << -1 << '\n';
        exit(0); // 사이클 탐지하면 출력하고 프로그램 종료
    }
    if (dp[x][y] != -1) return dp[x][y];

    visit[x][y] = true;
    dp[x][y] = 0;

    for (int i = 0; i < 4; i++) {
        int nx = x + (board[x][y] * dx[i]);
        int ny = y + (board[x][y] * dy[i]);
        dp[x][y] = max(dp[x][y], DFS(nx, ny) + 1);
    }

    visit[x][y] = false;
    return dp[x][y];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string S; cin >> S;
        for (int j = 0; j < S.length(); j++) {
            if (S[j] == 'H') board[i][j] = -1;
            else board[i][j] = S[j] - '0';
        }

        for (int j = 0; j < M; j++) {
            dp[i][j] = -1;
        }
    }
    int answer = DFS(0, 0);
    cout << answer;

    return 0;
}

https://www.acmicpc.net/problem/3425

풀이 과정

스택을 조금 변형한 고스택을 구현하는 문제이다.

문제에서 주어진 대로 구현하면 되나, 프로그램 에러의 3가지 경우를 구현하는데 신경을 써야 한다.

소스 코드

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#define max_value 1000000000
#define min_value -1000000000
using namespace std;

stack<long long> st;

void num(int x) {
    st.push(x);
}

int pop() {
    if (st.empty()) {
        return -1;
    } else {
        st.pop();
        return 1;
    }
}

int inv() {
    if (st.empty()) {
        return -1;
    } else {
        long long temp = st.top() * -1;
        st.pop();
        st.push(temp);
        return 1;
    }
}

int dup() {
    if (st.empty()) {
        return -1;
    } else {
        st.push(st.top());
        return 1;
    }
}

int swp() {
    if (st.size() < 2) {
        return -1;
    } else {
        long long first = st.top();
        st.pop();
        long long second = st.top();
        st.pop();
        st.push(first);
        st.push(second);
        return 1;
    }
}

int add() {
    if (st.size() < 2) {
        return -1;
    } else {
        long long first = st.top();
        st.pop();
        long long second = st.top();
        st.pop();
        long long temp = first + second;
        if (temp < min_value ||temp > max_value) {
            return -1;
        }
        st.push(temp);
        return 1;
    }
}

int sub() {
    if (st.size() < 2) {
        return -1;
    } else {
        long long first = st.top();
        st.pop();
        long long second = st.top();
        st.pop();
        long long temp = second - first;
        if (temp < min_value || temp > max_value) {
            return -1;
        }
        st.push(temp);
        return 1;
    }
}

int mul() {
    if (st.size() < 2) {
        return -1;
    } else {
        long long first = st.top();
        st.pop();
        long long second = st.top();
        st.pop();
        long long temp = first * second;
        if (temp < min_value ||temp > max_value) {
            return -1;
        }
        st.push(temp);
        return 1;
    }
}

int div() {
    if (st.size() < 2) {
        return -1;
    } else {
        long long first = st.top();
        st.pop();
        long long second = st.top();
        st.pop();
        if (first == 0) {
            return -1;
        }
        long long temp = second / first;
        if (temp < min_value ||temp > max_value) {
            return -1;
        }
        st.push(temp);
        return 1;
    }
}

int mod() {
    if (st.size() < 2) {
        return -1;
    } else {
        long long first = st.top();
        st.pop();
        long long second = st.top();
        st.pop();
        if (first == 0) {
            return -1;
        }
        long long temp = second % first;
        if (temp < min_value ||temp > max_value) {
            return -1;
        }
        st.push(temp);
        return 1;
    }
}

int main() {
    while (true) {
        vector<string> vec;
        string str;

        while (true) {
            cin >> str;
            if (str == "END") {
                break;
            } else if (str == "QUIT") {
                return 0;
            }
            vec.push_back(str);
        }
        int N;
        cin >> N;
        while(N--) {
            long long initial;
            cin >> initial;
            int errFlag = 0;
            st.push(initial);
            for (int i = 0; i < vec.size(); i++) {
                if (vec[i] == "NUM") {\
                num(stoi(vec[i+1]));
                    i += 1;
                } else if (vec[i] == "POP") {
                    errFlag = pop();
                } else if (vec[i] == "INV") {
                    errFlag = inv();
                } else if (vec[i] == "DUP") {
                    errFlag = dup();
                } else if (vec[i] == "SWP") {
                    errFlag = swp();
                } else if (vec[i] == "ADD") {
                    errFlag = add();
                } else if (vec[i] == "SUB") {
                    errFlag = sub();
                } else if (vec[i] == "MUL") {
                    errFlag = mul();
                } else if (vec[i] == "DIV") {
                    errFlag = div();
                } else if (vec[i] == "MOD") {
                    errFlag = mod();
                }

                if (errFlag == -1) {
                    cout << "ERROR" << '\n';
                    while (!st.empty()) {
                        st.pop();
                    }
                    break;
                }
            }

            if (errFlag == -1) {
                continue;
            }

            if (st.size() != 1) {
                cout << "ERROR" << '\n';
                while (!st.empty()) {
                    st.pop();
                }
            } else {
                cout << st.top() << '\n';
                st.pop();
            }

        }
        cout << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/1927

풀이 과정

최소 힙을 이용하여 문제에서 주어진 연산을 지원하는 프로그램을 작성하면 된다.

힙은 이진트리의 일종이므로 일차원 배열로 직접 구현이 가능하나, 라이브러리에 구현되어 있는 힙을 사용하였다.

C++의 경우에는 기본이 최대 힙이고, 파이썬은 기본이 최소 힙이다.

priority_queue<int> max_heap; // 최대 힙
priority_queue<int, vector<int>, greater<int>> min_heap; // 최소 힙

import heapq

heap = []
heapq.heappush(3)
heapq.heappush(5) # 기본은 최소힙

max_heap = []
heapq.heappush((-3, 3))
heapq.heappush((-5, 5)) # 이런 테크닉을 이용하여 최소힙을 최대힙처럼 사용해야 한다

소스 코드

c++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    priority_queue<int, vector<int>, greater<int>> pq;
    int N, num;
    cin >> N;
    while (N--) {
        cin >> num;
        if (num == 0) {
            if (pq.empty()) {
                cout << 0 << '\n';
            } else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        } else {
            pq.push(num);
        }
    }

    return 0;
}

Python

import heapq
import sys

heap = []
N = int(sys.stdin.readline())

for i in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
        continue
    heapq.heappush(heap, x)

https://www.acmicpc.net/problem/2748

풀이 과정

n번째 피보나치 수를 출력하는 문제이다.

피보나치 수를 재귀로 구하면 너무 시간이 오래 걸린다.

fi[n] = fi[n-1] + fi[n-2]

다음과 같은 점화식을 사용해 동적 계획법으로 문제를 해결하였다.

소스 코드

#include <iostream>
using namespace std;
long long d[91] = {0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    d[0] = 0; d[1] = 1; d[2] = 1;

    for (int i = 3; i < 91; i++) {
        d[i] = d[i-1] + d[i-2];
    }

    cout << d[n];
    return 0;
}

https://www.acmicpc.net/problem/2805

풀이 과정

절단기 높이 H보다 높은 나무의 길이를 길이 - H 만큼 잘라서 길이 M만큼 챙겨야 할 때, 가능한 최소 절단기의 높이를 구하는 문제이다.

나무 최대 길이 = 절단기 높이를 초기값으로 잡고, 길이 M만큼 챙길 수 있을 때 까지 절단기 높이 H를 1씩 낮추는 방법이 먼저 떠오르지만, 나무 길이가 10억까지 들어오므로 100% TLE가 날 것이다. 따라서 이분 탐색을 활용하여 문제를 해결하였다.

소스 코드

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

bool cut(long long mid, vector<long long>& vec, int N, int M) {
    long long sum = 0;

    for (int i = 0; i < N; i++) {
        if (vec[i] > mid) {
            sum += vec[i] - mid;
        }

        if (sum >= M) {
            return true;
        }
    }

    return false;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<long long> tree(N);

    for (int i = 0; i < tree.size(); i++) {
        cin >> tree[i];
    }

    long long left = 0;
    long long right = *max_element(tree.begin(), tree.end());
    long long mid;
    long long answer;

    while (left <= right) {
        mid = (left + right) / 2;
        if (cut(mid, tree, N, M)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << answer;

    return 0;
}

https://www.acmicpc.net/problem/2003

풀이 과정

i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하면 된다.

for문 중첩시키고 모든 연속구간을 만들어 보는 방법으로는 시간제한 내로 문제를 해결할 수 없다. 간단하게만 생각해봐도 N이 만까지 들어오는데 O(N^2) 알고리즘만 되도 TLE가 날 가능성이 있다. 투 포인터 알고리즘을 사용하면 O(N)으로 해결할 수 있다.

l, h 두 개의 포인터를 조절해가며 문제를 해결하였다.

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, sum, number, answer, l, h;
    sum = 0; l = 0; h = 0; answer = 0;
    vector<int> vec(N);
    cin >> N >> M;

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

    while(true) {
        if (sum >= M) {
            sum -= vec[l++];
        } else if (h == N) {
            break;
        } else {
            sum += vec[h++];
        }

        if (sum == M) {
            answer++;
        }
    }
    cout << answer;
    return 0;
}

https://www.acmicpc.net/problem/1260

풀이 과정

정점 수, 간선 수, 시작 점을 입력 받고 DFS, BFS를 사용했을 때의 순회 순서를 반환해주면 된다.

그래프의 간선을 파이썬의 딕셔너리를 활용하여 인접 리스트로 표현하고, DFS와 BFS를 통해 순회하였다. 방문할 수 있는 정점이 여러가지 인 경우 정점 번호가 작은 것을 먼저 방문하게 하려면 입력받은 인접 리스트를 정렬해주어야 한다.

소스 코드

from collections import deque
import sys

N, M, V = map(int, sys.stdin.readline().split())
g = {}
for i in range(N+1):
    g[i] = []
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    g[a].append(b)
    g[b].append(a)

for i in g.keys():
    g[i].sort()
    

def b_dfs(x, discovered=[]):
    discovered.append(x)
    for vertex in g[x]:
        if vertex not in discovered:
            discovered = b_dfs(vertex, discovered)
    return discovered


def b_bfs(start_x):
    discovered = [start_x]
    queue = deque([start_x])
    while queue:
        vertex = queue.popleft()
        for w in g[vertex]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered


a = b_dfs(V)
b = b_bfs(V)

for i in range(len(a)):
    if i == len(a) - 1:
        print(a[i])
        break
    print(f'{a[i]}', end=' ')
for i in range(len(b)):
    if i == len(b) - 1:
        print(b[i])
        break
    print(f'{b[i]}', end=' ')

https://www.acmicpc.net/problem/2309

풀이 과정

9명중에 진짜 난쟁이를 7명 찾아야 하고 7명의 키의 합이 100이라 한다.

-> 모든 난쟁이의 키의 합을 구하고 9명중에 2명의 난쟁이의 키의 합을 뺐을 때 100이 나오면 그 2명은 진짜 난쟁이가 아니다

루프 2번 돌면서 9명중에 2명의 난쟁이를 고르는 수인 36번 돌다 보면 가짜 난쟁이 2명이 걸러진다 브루트 포스 방법으로 2명 뺐을 때 키의 합이 100이 나올때까지 다 찾아보면 된다.

키의 합을 구하는 연산 O(N), 가짜 난쟁이 2명을 찾는 연산 O(N^2)으로 총 O(N^3)의 시간복잡도를 갖고, N이 9이므로 그냥 다 해봐도 시간제한 내로 문제를 해결하는데 문제가 없다.

소스 코드

import sys
height = []

for i in range(9):
    height.append(int(sys.stdin.readline()))

height.sort()

sumHeight = sum(height)

fake1 = 0
fake2 = 0

for i in range(8):
    for j in range(i+1, 9):
        if sumHeight - height[i] - height[j] == 100:
            fake1 = i
            fake2 = j

for i in range(9):
    if i != fake1 and i != fake2:
        print(height[i])

https://www.acmicpc.net/problem/2133

풀이 과정

https://greentea31.tistory.com/26

위와 비슷하게 DP로 풀기 위해 점화식을 세워서 문제를 해결할 수 있다.

문제를 보고 생각을 하다보면 3x2 블록을 채우는 경우의 수는 3개가 있으니 3x4는 3x2 블록 2개 붙이면 되겠고... 이런 생각이 들겠지만 밑에 힌트를 보면 3x2 블록 채우는 경우의 수를 2개 조합한게 아닌 3x4 블록을 채우는 방법이 존재함을 알게 된다.

3xi 에서 i가 2씩 늘어날 수록 기존의 방법의 조합이 아닌 새로운 방법이 2개씩 더 추가된다.

따라서 d[i]를 3xi 블록을 채우는 방법의 경우의 수라고 하면

d[i] = 3 * d[i-2] + 2 * d[i-4] + 2 * d[i-6] + ... + 2 * d[0]이 성립한다.

d[0]은 1로 초기값을 설정해놔야 정답을 얻을 수 있다.

소스 코드

import sys

N = int(sys.stdin.readline())
d = [1, 0, 3, 0, 11]
for i in range(5, 31):
    d.append(3*d[i-2])
    for j in range(4, i+1, 2):
        d[i] += 2*d[i-j]

print(d[N])