재원블로그 재원블로그

이 문제는 다익스트라를 이용해서 풀었다. 이 문제에서 핵심은 +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;..

이 문제는 문자열, 구현 문제이다. 주요 포인트는 대소문자 구별 X, 알파벳을 제외한 모든 문자가 구분자가 되는 단어들 파싱, 내 링크 및 외부 링크 찾기이다. 대소문자 구별을 하지 않는 방법은 전부 대문자나 소문자로 바꿔놓는 것이다. 이는 간단하게 구현할 수 있다. 알파벳을 제외한 모든 문자가 구분자가 되는 단어들을 파싱하기 위해 for문을 돌리면서 'a'

이 문제는 완전 탐색으로 풀 수 있다. 이 문제를 정말 그대로 구현하면 24 * 60 * 60 * 1000 * 1000 = 86,400,000,000 번의 연산이 필요하여 시간 초과가 난다. 로그 배열의 최대 크기는 2,000 이므로, O(N^2) 이하의 알고리즘을 구현하면 시간 초과가 나지 않는다. 그래서 각 로그에 대해 루프를 돌면서 다른 로그들을 순회하는 방식의 알고리즘을 생각했다. 1초의 인터벌을 가지는 구간은 총 4개가 나올 수 있는데, start 왼쪽, start 오른쪽, end 왼쪽, end 오른쪽 이다. 그래서 각 로그마다 해당 4개의 구간을 설정하여 다른 로그들이 이 안에 들어올 경우 각각에 대해 1을 더해주고, 마지막에 네 개 중 가장 개수가 많은 것을 저장하는 방식으로 정답을 맞출 수..

이 문제는 백트래킹을 이용해서 풀었다. 이 문제에서 핵심은 각 행과 열이 최대 한 번씩만 뒤집는 경우로 제한하는 것과 뒤집는 순서가 바뀌어도 결과가 같다는 것이다. 우선 아래의 숫자에서 2행 -> 1열 을 뒤집고, 같은 숫자에서 1열 -> 2행을 뒤집으면 같은 결과가 나온다. 1011110111 0101010101 10001->2행10001 0100101001 1010110101 1열1열 0011100111 1101000101 00001->2행00001 1100111001 0010100101 이를 파악함으로써 뒤바뀐 순서를 다시 탐색하지 않도록 count를 두어 순서를 강제함으로써 속도를 높일 수 있다. 두 번째로 같은 행, 열을 2번 뒤집으면 원래 모양이 나오기 때문에 딱 1번만 뒤집는 경우로 최대 뒤..