greentea31's Note

큐를 활용해 너비 우선 탐색을 시행하는 예시 코드이다.

C++ - Flood Fill BFS

// BFS 예시 코드

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

int board[502][502];
bool vis[502][502];
int n = 7, m = 10; // n은 가로 길이, m은 세로 길이
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

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

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

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        cout << '(' << cur.second << ", " << cur.first << ") -> ";
        for (int dir = 0; dir < 4; dir++) {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[ny][nx] || board[ny][nx] != 1) continue;
            vis[ny][nx] = true;
            Q.push(make_pair(ny, nx));
        }
        
    }
    
    return 0;
}

Python - 인접 리스트로 주어진 그래프에 대한 BFS

import collections

graph =[[], [1], [1, 3]] # 인접 리스트로 주어진 그래프


def bfs(start_v):
    discovered = [start_v]
    queue = collections.deque([start_v])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

연결되어 있고 방문하지 않은 정점들을 전부다 큐에 넣고 방문 처리한다.

큐가 빌 때 까지 큐의 맨 앞의 정점에 대해 이를 반복한다.

출처

C++ 코드

https://blog.encrypted.gg/941?category=773649 

Python 코드

https://book.naver.com/bookdb/book_detail.nhn?bid=16406247 

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

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

int output[10];

void go(int index, int selected, int max_number, int length) {
    if (selected == length) {
        for (int i = 0; i < length; i++) {
            cout << output[i] << ' ';
        }

        cout << '\n';
        return;
    }

    if (index > max_number) return;
    output[selected] = index;
    go(index+1, selected+1, max_number, length);
    go(index+1, selected, max_number, length);
}

int main() {
    int N, M;
    cin >> N >> M;
    go(1, 0, N, M);
}

위의 코드와 같이 재귀로 조합을 구현할 수 있다.

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

위의 문제의 정답 코드이기도 하다.

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

int discovered[10];
int output[10];

void go(int index, int max_number, int length) {
    if (index == length) {
        for (int i = 0; i < length; i++) {
            cout << output[i] << ' ';
        }

        cout << '\n';
        return;
    }

    for (int i = 1; i <= max_number; i++) {
        if (discovered[i]) continue;
        discovered[i] = 1;
        output[index] = i;
        go(index+1, max_number, length);
        discovered[i] = 0;
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    go(0, N, M);
}

중복을 허용하지 않는 순열을 재귀를 이용해 작성한 코드이다.

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

위의 문제의 정답 코드이기도 하다.

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