노력의 천재 노력의 천재

알고리즘 문제풀이

• [백준/BOJ] 1600번 말이 되고픈 원숭이 (C++)

  알고리즘 문제풀이/백준 2021. 11. 4. 15:17

  https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 2206번 벽 부수고 이동하기를 응용한 것 같은 문제였다. 해당 문제를 해결했다면 어렵지 않았을 BFS 문제다. #include #include #include #include using namespace std; struct Pos { int x, y, cnt; }; int k, w, h; int map[201][201]; int visit[31][201][201]; int dx..

  Read More
• [백준/BOJ] 1527번 금민수의 개수 (C++)

  알고리즘 문제풀이/백준 2021. 11. 2. 16:51

  https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 간단한 완전탐색(브루트포스) 문제였다. 4와 7로 이루어진 1~9번째 자리의 숫자를 DFS로 모두 구해준 후, 이를 벡터에 저장했다. 그 후, 입력으로 들어온 a와 b 사이에 있는 값이 벡터에 몇개 들어있는지 찾으면 된다. #include #include #include using namespace std; int a, b, answer; vector v; void DFS(int cnt, int..

  Read More
• [백준/BOJ] 2573번 빙산 (C++)

  알고리즘 문제풀이/백준 2021. 11. 2. 16:28

  https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제의 조건을 정리하며 차례대로 구현하면 어렵지 않게 해결할 수 있는 BFS 문제였다. 1. map 입력을 받는다. 2. map[i][j] > 0, 현재 빙산과 접하는 바닷물의 수를 구하고, 이를 현재 빙산에서 빼준다. (그 뺀 값이 음수라면 0으로 바꿔주기) 3. 모든 map에 대해 2번 작업을 완료했다면, BFS를 통해 분리된 덩어리의 수를 구한다. 4. 분리된 덩어리의 수가 2보다 크거..

  Read More
• [백준/BOJ] 2206번 벽 부수고 이동하기 (C++)

  알고리즘 문제풀이/백준 2021. 10. 29. 15:04

  https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 벽 뚫기 사용의 유무를 체크하기 위해 3차원 배열을 이용해야 한다. 해당 아이디어만 잘 떠올린다면 어렵지 않게 해결할 수 있는 BFS 문제였다. #include #include #include #include using namespace std; int N, M; int map[1001][1001]; int visit[2][1001][1001]; int dx[4] = {-..

  Read More
• [백준/BOJ] 5014번 스타트링크 (C++)

  알고리즘 문제풀이/백준 2021. 10. 28. 17:26

  https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1697번 숨바꼭질 문제와 비슷한 BFS 문제였다. 그래서 어렵지 않게 해결 ㅎ (범위 처리만 잘 해주자) #include #include #include #include using namespace std; int F, S, G, U, D; int visit[1000001]; int BFS() { queue q; q.push(S); visit[S] = 0; while(!q.empty()) { int now ..

  Read More
• [백준/BOJ] 1543번 문서 검색 (C++)

  알고리즘 문제풀이/백준 2021. 10. 27. 14:40

  https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 간단한 문자열 탐색 문제였다. 풀이를 설명할 필요없이 코드를 보면 이해가 갈 것이다. #include #include using namespace std; int main(void) { freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false); cin.tie(0); string str, word; getline(cin, str); getl..

  Read More
• [백준/BOJ] 2146번 다리 만들기 (C++)

  알고리즘 문제풀이/백준 2021. 10. 26. 16:06

  www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 구현 부분에서 조금 애먹었지만 풀이 로직은 정확하게 맞은 문제 1년 후에 다시 풀었더니 한번에 맞췄다. ㅎㅎ BFS를 두번 사용해야하는데, 첫번째 BFS는 각 섬의 영역에 번호를 매기기 위해 사용하고, 두번째 BFS는 각 섬에서 다른 섬까지의 최소 거리를 구하는데 사용해서 문제를 해결했다. #include #include #include #include #include #include using namespace s..

  Read More
• [백준/BOJ] 2468번 안전 영역 (C++)

  알고리즘 문제풀이/백준 2021. 10. 13. 17:16

  https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net BFS 문제, map의 값이 전부 1일 때 답이 1이 나와야 하는데, 이를 주의해야 한다. (비가 안오는 경우도 있으므로) #include #include #include #include using namespace std; int n, answer; int map[101][101]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; bool visit[10..

  Read More