재원블로그 재원블로그

이 문제는 구현 문제이다. 각 2N개의 길이 경사로를 설치하여 갈 수 있는 길인지를 체크하는 문제이다. N이 100으로 아주 작기 때문에 요구사항만 구현하면 문제가 풀린다. 현재와 다음 블럭을 비교했을 때 같은지, 더 높은지, 더 낮은지에 대한 분기문을 작성하여 문제를 해결했다. 다만 주의할 점은 경사로를 설치할 수 있는 높이 차는 최대 1이기 때문에 이를 체크해주지 않으면 오답이 나온다. #include #include #include using namespace std; #define MAX 100 int N, L; int matrix[MAX][MAX]; int absolute(int num) { if (num < 0) { return -num; } return num; } bool rowCheck(..

이 문제는 시뮬레이션 문제이다. 시뮬레이션 문제 특성상 문제 요구사항이 복잡한 대신 구현만 제대로 되면 정답이 바로 나온다. 주사위를 길이가 6인 배열로 구성하고, 각 인덱스에 대해 실제 위치를 상수로 정해서 가독성을 높였다. 주사위는 6개 면밖에 없기도 하고, 규칙성을 빠르게 찾아내지 못해 굴리는 방향에 따라 직접 수정을 해주는 방식으로 구현했다. #include #include using namespace std; #define MAX 20 #define RIGHT 1 #define LEFT 2 #define UP 3 #define DOWN 4 #define ABOVE 0 #define BELOW 1 #define EAST 2 #define NORTH 3 #define WEST 4 #define SO..

이 문제는 시뮬레이션 문제이다. 입력 배열이 최대 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