관심이 가는 개발 보물창고

문제 풀이 3차원에서 상범이가 탈출할 수 있으면 최단 경로를 리턴하고, 탈출할 수 없다면 Trapped!라고 출력하면 된다. 기존에는 2차원 배열에서 상,하,좌,우만 구현했다면 이번에는 위층과 아래층을 갈 수 있도록 만들어야 한다. const int dx[] = { 0,0,-1,1,0,0 }; const int dy[] = { 1,-1,0,0,0,0 }; const int dz[] = { 0,0,0,0,-1,1 }; 따라서 6방향으로 나눠서 구현해준다. 기존 BFS 코드를 3차원으로 구현해주기만 하면 문제를 해결할 수 있다. 주의할 점은 다른 칸으로 이동할 때 방문체크랑 '#'이 아닌 곳으로 가야 하면서 동시에 몇 번만에 그 위치에 왔는지 기록을 해야 한다. 아래의 구현은 i = Z, j = X(행), ..

문제 풀이 문제를 읽고 아래와 같이 요약을 했다. 1. 빙산을 언제까지 녹일 수 있을까? 2. 빙산을 어떻게 녹일까? 3. 언제 빙산이 2덩어리 이상으로 나누어질까? 1번부터 보자. 빙산을 언제까지 녹일 수 있을까? 빙산이 2차원 배열에서의 높이가 모두 0이 되어버리면 빙산은 다 녹았다고 판단할 수 있다. 간단하게 말해서 하나라도 0보다 큰 숫자(높이)가 있다면 아직 빙산이 다 녹지 않은 것이다. 2번을 보자. 빙산을 어떻게 녹일까? 빙산은 녹을 때 자신의 위치에서 상, 하, 좌, 우로 바닷물이 인접해있으면 그 수만큼 빙산의 높이를 줄이게 된다. 그런데 한 가지 주의할 점이 칸 마다 4방향을 확인하면서 녹이게 되면 안 된다. A라는 칸에서 4방향 해서 녹인 빙산으로 갱신하면 그 다음 B라는 칸에서 A 라..

문제 풀이 간단한 수학 문제다. 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태로 출력한다. 기약 분수 형태로 출력하고자 한다면 유클리드 호제법을 떠올리면 된다. 어떤 분수를 기약 분수 형태로 만들고 싶을 때 최대 공약수로 나누면 기약 분수 형태를 만들 수 있기 때문이다. 소스 코드 #include #include #include using namespace std; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector v(n); for (int i = 0; i ..

문제 풀이 재밌는 문제다. 1과 N을 제외한 진짜 약수가 모두 주어졌을 때, N을 구하는 문제. 12의 약수를 생각해보자. {1, 2, 3, 4, 6, 12} 문제에서 1과 N을 제외한 진짜 약수가 주어진다고 하면 아마 다음과 같을 것이다. {2, 3, 4, 6} 위의 수열은 섞여있을 수도 있다. 그렇지만 진짜 약수들만 주어지므로 요소는 똑같다. 어떻게 N을 찾을 수 있을까? 간단하다. 가장 작은 수랑 가장 큰 수를 곱하면 그것이 즉 N이다. 2 x 6 = 12 (우리가 구하려고 하는 N이다) 따라서 수열이 주어지면 가장 작은 수랑 큰 수를 곱하면 답이다. 소스 코드 #include #include #include using namespace std; int main() { ios_base::sync_w..

문제 풀이 (1, 1) 시작점에서 (n, n) 도착점에 도착하기 위해서 몇 번의 검은 방을 부셔야 하는지 최소의 횟수를 구하는 문제다. 단순히 BFS 알고리즘을 돌리기에는 에러가 있다. (3, 3) 의 좌표를 보자. 단순히 BFS를 돌리게 되면 (3,3)은 이전의 (2,3)이나 (3,2)로부터 부신 횟수에 + 1을 하여서 2가 될 수 있지만, 그림을 보면 (3,3)도 1번만 부셔서 갈 수 있는 곳이 된다. 기존에 방문을 했더라도 더 빠른 경로가 있다면 그 경로로 값을 바꿔주거나 갱신을 시켜줘야 한다는 것이다. 만약 내 앞의 방이 흰방이면, 방문을 했더라도 더 빠른 경로라면 더 빠른 경로로 갱신하고 다시 살펴본다. 만약 내 앞의 방이 검은방이면, 방문을 했더라도 더 빠른 경로라면 더 빠른 경로로 갱신하고 ..

문제 풀이 편의점의 후보와 집의 후보가 나열되는데, 이때 우리는 편의점이랑 가까운 집을 찾으려고 한다. 어떻게 찾을 수 있을까? 편의점으로부터 가까운 집을 고르는 것이기 때문에 이는 최단 경로를 구해야 된다. 그런데 그러한 경로는 다양하기 때문에 이러한 것들을 빠르게 찾아낼 수 있는 것이 바로 다익스트라다. 한 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있기 때문이다. 여기서 핵심은 역발상이다. 집이라는 후보가 정해져 있기 때문에 해당 편의점을 시작 지점으로 잡은 다음 출발하여 집의 후보를 발견했다면 그때의 경로와 집의 번호를 pair로 정답 배열에 저장한다. 이렇게 저장된 정답 배열을 오름차순으로 정렬하면 우리가 구하고자 하는 답이 나오게 된다. 시간 복잡도를 생각해보자. 다익스트라를 인접 리..

문제 풀이 다익스트라의 기본 개념을 알고 있는지 묻는 문제다. 출발점 X의 도시에서 다른 모든 도시까지의 최단 경로를 구한 다음에 어떤 도시에서 출발해서 어떤 도시의 도착하는 비용이 K와 같다면 정답 배열에 넣고 정답 배열을 정렬해서 출력하면 된다. 만약에 배열의 사이즈가 0이라면 도시가 없기 때문에 -1을 출력하면 된다. 소스 코드 #include #include #include #include using namespace std; const int MAX = 300000 + 1; const int INF = 987654321; typedef pair pii; int N, M, K, X; vector adj[MAX]; void dijkstra() { vector dist(N + 1, INF); prio..

문제 풀이 a b s 가 주어지면, b가 감염되면 s초 후에 컴퓨터 a가 감염된다. 이 말은 즉슨 b부터 감염을 시작하면 a까지의 도달하는 비용은 s초다. 출발 노드로부터 다익스트라 알고리즘을 순회하면 문제를 해결할 수 있다. 감염된 컴퓨터의 수는 dist 배열에서 INF가 아닌 컴퓨터를 카운팅 하면 된다. 모든 컴퓨터가 감염되기까지 걸린 시간 역시 INF가 아닌 dist 배열에서 가장 큰 수를 저장해서 출력하면 된다. 소스 코드 #include #include #include #include using namespace std; int t, n, d, c; const int INF = 987654321; typedef pair pii; vector adj[10001]; int dist[10001]; v..

문제 풀이 주어진 문자열을 3개의 문자열로 나눈 다음에 각각의 문자열을 뒤집고, 뒤집은 3개의 문자열을 다시 합치면 된다. 문제는 어떻게 3등분을 하는가이다. 문제에서 문자열을 나눌 때 최소한 문자열의 길이가 1을 보장해야 한다고 명시되어있다. 문제에서 주어진 예시(arrested)를 3등분한다고 한다면? 아래처럼 다양하게 나올 것이다. a / r / rested a / rr / ested a / rre / sted ... arrest / e / d 하나의 색종이를 2등분으로 만들고 싶다면? 가위로 한 번 자르면 된다. 하나의 색종이를 3등분으로 만들고 싶다면? 가위로 두 번 자르면 된다. 우리는 3등분을 원하므로 총 2번의 경계선만 구하면 된다. [문자열의 시작 지점 - i - j - 문자열의 끝 지점..

문제 풀이 정리해보면, 사전이 주어졌을 때 각 단어를 입력하기 위해 버튼을 눌러야 하는 최소의 횟수를 구해서 평균을 매기면 된다. 어떻게 하면 최소의 횟수를 구할 수 있을까? 사전에 아래와 같이 등록되었다고 생각해보자. hello hell heaven 문제에서 보았듯이 첫 글자는 무조건 버튼을 눌러야 한다. h를 눌러보자. h를 눌렀더니 자동적으로 e가 타이핑이 된다. 왜냐하면 사전에는 h 다음으로 등록되어 있는 것이 e가 공통이기 때문이다. 그런데 he에서 보자. he는 hello, hell, heaven 다 될 수 있기 때문에 자동적으로 등록되지 못한다. (선택 장애) 따라서 사용자는 어쩔 수 없이 버튼을 눌러야 한다. 만약에 l을 누른다고 해보자. l을 누르자마자 자동적으로 l이 추가되어 hell가..