겜돌이의 개발일지

문제 백준 2206 C++ 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 일반적인 BFS 문제였습니다. 다른 문제들과 거의 비슷한데, 벽을 1번까지는 뚫을 수 있으므로 방문체크를 3차원으로 합니다. (x, y, 벽 부순 횟수) 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4..

문제 백준 1987 C++ 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 0, 0 지점부터 DFS를 실행하여 최대 깊이를 구해줍니다. 해당 지점을 방문했는지를 저장하는 mapvisited 배열과 해당 문자열을 방문했는지를 저장하는 charvisited 배열을 모두 사용하여 방문 체크를 합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ..

문제 백준 14719 C++ 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 블록을 검은색, 빗물이 차는 곳을 파란색이라고 하면 예시 1 양 쪽 끝에 검은 영역이 있을 때, 그 사이의 모든 영역이 파란 영역이 됩니다. 예시 2 마찬가지로 양쪽 끝에 검은 영역이 있으면, 그 사이의 모든 영역이 파란 영역이 됩니다. 따라서 map을 전부 순회하면서, 블록과 블록 사이의 영역을 모두 구해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..

문제 백준 13398 연속합 2 C++ 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 점화식을 이용하여 문제를 해결합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include using namespace std; int arr[100000]; int dp[100000][2]; int main() { ios::sync_with_stdio(false); cin.tie(0)..

문제 백준 2660 회장뽑기 풀이 각 정점마다 bfs를 해준 뒤 깊이를 비교합니다. 깊이가 더 작으면 갱신해주고, 같으면 추가해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include #include #include #include #include using namespace std; vector v[51]; bool visited[51]; int N; i..

문제 백준 5582 공통 부분 문자열 C++ 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 예제 입력을 보겠습니다. A B R A C A D A B R A E C 1 A 1 1 1 1 1 D 1 A 1 1 1 1 1 D 1 A 1 1 1 1 1 B 1 1 R 1 1 B 1 1 C 1 R 1 1 D 1 A 1 1 1 1 1 R 1 1 A 1 1 1 1 1 s1를 문자열 1의 길이, s2를 문자열 2의 길이라고 하면 dp[0][0] 부터 dp[s2-1][s1-1] 까지 루프를 돌면서 s1과 s2..

문제 백준 13023 ABCDE C++ 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 깊이가 4이상인 노드가 있는지 확인하는 문제입니다. 각각의 노드에서 DFS를 실행하여 깊이가 4가 이상이 되는지 확인합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include using namespace std; vector v[2000]; bool visited[2000]; bool ispossible; void ..

문제 백준 1038 감소하는 수 C++ 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 감소하는 수의 순서는 다음과 같습니다. 한 자리 : 0 (0번째) -> 1 (1번째) ~ ... ~ 9 (9번째) 두 자리 : 10 -> 20 -> 21 -> 30 -> 31 -> 32 -> ... -> 98 세 자리 : 210 > 310 -> 320 -> 321 -> ... -> 987 네 자리 : 3210 -> ... -> 9876 ... 열 자리 : 9876543210 각 자리 수가 0~9 이기 때..

문제 백준 6593 상범 빌딩 C++ 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 2차원 배열로 bfs, dfs 문제를 푸는 경우가 많은데 이 문제는 3차원 배열로 풀어야해서 꽤 신선했습니다. 특별할 건 없고, 2차원 배열로 풀던걸 3차원으로 적용시키면 됩니다. 이동할 수 있는 지점은 상 / 하 / 좌 / 우 / 위 / 아래 (동서남북상하)의 6가지 경우입니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..

문제 백준 17471 게리맨더링 C++ 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 N까지의 노드를 0과 1로 양분합니다. 0과 1을 양분할 수 있는 모든 경우의 수에 대해 실행합니다. (조합 이용) 0과 1로 양분할 수 있게 영역이 결정되면, 각 영역을 서로 0은 0끼리, 1은 1끼리 연결할 수 있는지 확인힙니다. 연결이 가능하다면, 각각의 합을 구한 후 차를 구하고, 최솟값과 비교하여 갱신합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..