재원블로그 재원블로그

이 문제는 시뮬레이션 문제이다. 입력 배열이 최대 50 x 50 으로 작기 때문에 구현만 한다면 정답이 나오는 문제이다. 1. 현재 칸이 청소되지 않은 경우, 현재 칸 청소 2. 현재 칸 주변 4칸 중 청소되지 않은 빈칸이 없다면 2-1. 바라보는 방향 유지한 채로 한칸 후진할 수 있다면 한칸 후진 후 1번 돌아감 2-2. 바라보는 방향 뒤쪽이 벽이라 후진 불가능하면 작동 멈춤 3. 현재 칸 주변 4칸 중 청소되지 않은 빈칸이 있다면 3-1. 반시계 방향으로 90도 회전 3-2. 바라보는 방향 기준 앞쪽 칸이 청소되지 않은 빈칸일 경우 한 칸 전진 3-3. 1번으로 돌아감 이라는 조건을 만족하도록 로직을 구성하면 바로 정답이 나온다. #include #include using namespace std; ..

이 문제는 구현 문제이다. 문제 제목 보고 1억 * 1억 배열이라 다른 방법을 사용할 줄 알았는데 입력으로 주어지는 e가 최대 5백만이라 배열로 만들 수 있었다. 가장 처음 나오는 이중 for문에 5,000,000을 넣고 카운트해보면 약 7,800만 정도의 연산을 수행하게 된다. 따라서 1초 안에 cnt를 모두 셀 수 있다. 범위를 세는 부분이 언뜻 시간을 초과할 것처럼 보이지만, starts 배열을 내림차순 정렬한 뒤 각 루프마다 구간을 계산하면 이전 결과를 활용할 수 있어 O(N)이면 해결된다. 이 때 정렬을 해도 원래 위치를 알 수 있어야 하기 때문에 pair를 사용하였다. #include #include #include #include #include using namespace std; #def..

이 문제는 bfs, 트리를 이용해서 풀었다. 이 문제에서 노드의 수가 n일 때 간선의 수가 n - 1개이고, 모든 임의의 두 점은 연결되어있으므로 입력 그래프는 트리이다. 트리는 아무 점이나 루트로 잡아도 트리이므로, 1을 루트로 잡았다. bfs를 이용해서 노드들의 depth를 계산한다. bfs 이후에는 depth가 깊은 순서대로 내림차순 정렬 후 루프를 돌린다. depth가 가장 깊은 리프 노드부터 자신의 부모를 확인한다. 이 때 자신이 이미 켜져있는 경우에는 continue한다. 만약 자신의 부모가 등대가 켜져있지 않다면 켜주고 answer++하는 방식으로 정답을 구할 수 있다. 문제에서 입력 그래프가 트리일 경우에는 bfs나 dfs를 이용한 풀이가 적용되는 경우가 많았던 것 같다. #include ..

이 문제는 다익스트라를 이용해서 풀었다. 이 문제에서 핵심은 +1, -1, *2를 수행할 때 현재와 목적지와의 관계를 비교하지 않는 것이다. 이는 예제에서 말해주고 있다. 출발지가 5이고, 도착지가 17인데, 10에서 9로 가는 선택이 들어간다. 내가 했던 실수는 여기서 현재가 도착지보다 작을 경우, 0이 아니면 *2, +1 을 수행하고, 0이면 +1을 수행하는 식의 로직이 추가되었다는 점이다. 이러면 10에서 9로 가는 로직이 형성되지 않는다. 현재와 목적지까지의 상대 위치를 판단하지 않으면 큐에 너무 많은 숫자가 들어오게 되는데, 이를 방지하기 위해 다익스트라 알고리즘을 사용할 수 있다. 다익스트라를 이용하면 항상 현재 비용이 가장 적은 것부터 수행하기 때문에, 정답에 도착했을 때 바로 리턴해도 그것..

이 문제는 bfs를 이용해서 풀었다. visited 배열에 이미 벽을 하나 부쉈는지에 대한 여부 정보를 추가하면 쉽게 풀 수 있다. 결론적으로 가중치가 1인, 즉 단순히 이동한 거리에 대한 최소를 구하면 되므로 가장 먼저 (N, M) 에 도착한 것을 리턴해주어도 정답이 나올 수 있다. #include #include #include #include #include using namespace std; #define MAX 1000 #define INF 1000000000 #define NOT_DESTROY 0 #define DESTROY 1 int N, M; int matrix[MAX + 1][MAX + 1]; int dy[] = { -1, 0, 1, 0 }; int dx[] = { 0, -1, 0, 1..

이 문제는 백트래킹을 이용해서 풀었다. 프로그래머스에도 이 문제가 있지만, N 이 최대 12까지이다. 그러나 백준에서는 14까지 확장된다. 그래서 기존 알고리즘으로는 14에서 시간이 너무 오래 걸린다. 그래서 생각한 것은 N이 짝수일 경우, 절반까지만 탐색하고 그 결과에 x 2를 하면 정답이라는 것이다. 절반까지 탐색한 것을 좌우대칭 시키면 똑같은 그림이 나오기 때문이다. 그래서 이를 구현하면 정답이 나오게 된다. #include #include using namespace std; int N; int dy[] = { -1, 1, 1, -1 }; int dx[] = { -1, -1, 1, 1 }; int board[15][15]; bool inRange(int y, int x) { if (0 N; cout

이 문제는 bfs와 백트래킹을 이용해서 풀었다. 우선 단순히 상하좌우, Ctrl + 상하좌우 총 8가지 움직임이 가능하다. visited와 같은 방문 여부 배열을 처음부터 사용할 수는 없다. 하나의 쌍을 완료한 후에 다음 최단 거리를 위해서는 이미 방문했던 위치로 또 가야할 수 있기 때문이다. 따라서 단순히 완전 탐색을 수행하면 O(8^N) 이 되므로 N이 9만 되어도 1억이 넘어가게 된다. 생각을 다시 해본 결과 전체 로직을 bfs로 넣을 수는 없지만, 일부 로직에서는 bfs를 적용할 수 있다는 생각을 하게 되었다. 한 점에서 단순히 다른 점으로 이동하는 데에는 bfs를 이용해서 최소 비용을 구할 수 있기 때문이다. 그래서 움직임을 담당하는 함수 minMove() 를 통해 한 점에서 다른 점으로 이동하..

이 문제는 multiset을 이용해서 풀었다. 문제 제목대로 진짜 우선순위 큐 두 개 만들어서 하면 시간 초과가 난다. 문제에서 중복된 숫자가 들어올 수 있기 때문에 set이 아닌 multiset을 사용했다. set, multiset은 기본적으로 오름차순 정렬이 되어있기 때문에 문제의 요구사항을 쉽게 해결할 수 있다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; for (int test = 0; test > k; multiset numbers; for (int command = 0;..