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://leetcode.com/problems/trapping-rain-water/

풀이 과정

다음과 같은 input이 들어올 때, 고이는 물의 총부피를 구하는 문제이다.

가장 높은 바닥을 기준으로 왼쪽 영역과 오른쪽 영역으로 나눠서 생각하면 풀이 방법이 빠르게 떠오른다.

왼쪽 영역은 왼쪽에서부터, 오른쪽 영역은 오른쪽에서 부터 읽어 나가면서, 여태 나왔던 바닥의 최대 높이를 저장하고, 바닥의 최대 높이 - 현재 바닥의 높이만큼 물이 고일 것이므로 그만큼을 정답 변수에 더해주면 된다.

소스 코드

class Solution:
    def trap(self, height: List[int]) -> int:
        left_max, right_max = 0, 0
        max_height_index, max_height = 0, 0
        answer = 0
        
        for i in enumerate(height):
            if max_height < i[1]:
                max_height_index, max_height = i[0], i[1]
                
        for i in range(0, max_height_index):
            if left_max < height[i]:
                left_max = height[i]
            else:
                answer += left_max - height[i]
        
        for i in range(len(height)-1, max_height_index, -1):
            if right_max < height[i]:
                right_max = height[i]
            else:
                answer += right_max - height[i]
        
        return answer

https://leetcode.com/problems/two-sum/

풀이 과정

합이 target이 되는 배열 값을 가리키는 인덱스 2개를 구하라는 문제이다.

완전 탐색을 돌려서 O(N^2)로 답을 구할 수 있다. 그런데 후속 조치로 O(N^2) 보다 적은 시간 복잡도를 가진 알고리즘으로 해결할 수 있냐는 질문이 달려있다.

1. 투 포인터로 풀기

입력된 리스트에 enumerate로 index 붙여주고, x:x[1]에 대해 정렬시킨 뒤, 포인터를 배열의 시작, 끝부분에 위치시키고 포인터에 해당하는 배열의 합이 타겟보다 작으면 left += 1, 아니면 right -= 1 시켜가면서 답을 구했다.

정렬이 O(NlogN)이고 투포인터로 배열 탐색이 O(N) 걸리니 알고리즘의 시간 복잡도는 O(NlogN)이다. 105ms의 실행시간을 가지는 효율적 방법이다.

2. 딕셔너리로 풀기

딕셔너리[값] = 인덱스를 저장해나가면서, 타겟 - 값을 키로 갖는 밸류가 딕셔너리에 존재하는지 살펴본다. 배열을 1회만 탐색하면 되므로 O(N)인데 실행시간이 112ms가 나와 투 포인터보다 의미 있게 빠르진 않았다.

소스 코드

투 포인터

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        s_nums = sorted(enumerate(nums), key=lambda x:x[1])
        
        while (left < right):
            sum = s_nums[left][1] + s_nums[right][1]
            if sum == target:
                return [s_nums[left][0], s_nums[right][0]]
                break
            elif sum < target:
                left += 1
            else:
                right -=1

딕셔너리

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], i]
            dic[num] = i

https://leetcode.com/problems/group-anagrams/

풀이 과정

문자열을 애너그램 단위로 묶어서 출력하는 문제이다.

애너그램을 판단하려면 정렬해서 비교하면 된다.

딕셔너리의 키 값을 정렬된 문자열, 밸류를 문자열로 해서 딕셔너리에 보관하면 애너그램 단위로 쉽게 묶어서 출력할 수 있다.

ex) abc bca cab는 모두 정렬하면 abc

       abc: [abc, bca, cab]가 저장되게 됨

소스 코드

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = collections.defaultdict(list)
        for str in strs:
            s_str = ''.join(sorted(str))
            dic[s_str].append(str)
        return list(dic.values())

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;
}