재원블로그 재원블로그

이 문제는 그리디 알고리즘으로 풀었다. 이 문제에서 핵심은 카드를 버리지 않는 것이다. 즉, 버리는 대신 어딘가 저장해둔 뒤에 필요할 때 코인을 주고 쓰는 것이다.이걸 인지하면 문제가 매우 쉬워지고, 단순 구현 문제로 바뀌게 된다. 그리디 알고리즘이 적용되는 부분은 N + 1을 만들 때 적용되는데, 우선순위를 다음과 같이 해서 문제를 풀었다.1. 내가 가진 카드만으로 n + 1 만들 수 있을 때2. 버린 덱에서 한 장 + 내가 가진 카드 한 장으로 만들 수 있을 때3. 버린 덱에서 두 장 모두 가져와야 할 때 매 라운드마다 카드를 두 장 뽑을 수 있는데, 바로 discard set에 넣어서 구현을 단순화했다. 주의할 점은 루프가 다 돌아서 끝나는 경우에는 answer + 1을 해줘야 한다는 점이다.#in..

이 문제는 BFS를 이용해서 풀었다. 이 문제에서 관건은 한 번만 꺾이는 경로를 찾는 것, 모두 없앨 수 있을 때 알파벳 순으로 빠른 순으로 출력하는 것이다. 한 번만 꺾이는 경로에 대해서는 Node 구조체를 만들어 y, x 좌표와 함께 방향, 꺾인 카운트를 추가하여 BFS로 구현할 수 있었다. 알파벳 순으로 빠른 순으로 출력하는 부분에 있어서는 약간의 생각이 필요했다.그러나 만약 A와 C가 동시에 경로가 존재하고, 이를 순서를 바꾼다고해서 뒤의 결과에 영향을 주지 않는다는 것을 알게 되었다.어떤 알파벳이 사라짐으로써 경로가 생길 수도 있지만, 이는 순서와 상관없이 그 알파벳이 없어지기만 한다면 경로가 생기기 때문이다.따라서 알파벳 순서로 루프를 돌면서 가장 먼저 제거할 수 있는 부분이 생기면 즉시 제거..

이 문제는 맵과 다이나믹 프로그래밍을 이용해서 풀었다. 이 문제를 처음에 그리디로 접근하려다가 다이나믹 프로그래밍 문제임을 알게 되었다.왼손과 오른손 모두 똑같은 가중치로 특정 숫자에 갈 때가 문제였는데, 이 때 임의의 손을 선택하게 된다면 다음 숫자들에 대해 결과가 달라지기 때문에 그리디로는 풀 수 없다. 따라서 완전 탐색을 사용해야하는데, 왼손이 위치하는 숫자, 오른손이 위치하는 숫자, 현재 숫자(눌러야하는 숫자) 총 세 개의 파라미터를 통해 하나의 독립적인 상태를 만들 수 있었다. 따라서 다이나믹 프로그래밍으로 속도를 빠르게 만들 수 있어 문제를 해결할 수 있었다. 이 문제에서 가장 까다로웠던 것은 키패드의 위치와 숫자를 매칭하고, 최단 거리를 찾는 로직 두 개였다. 키패드의 위치와 숫자를 매칭하는..

이 문제는 bfs와 유니온 파인드를 이용해서 풀었다. 이 문제를 요구사항 그대로 각 벽마다 bfs를 각각 수행하면 시간 초과가 나게 된다.따라서 반대로 빈칸을 bfs를 통해 덩어리의 개수를 미리 계산하고, 다음 루프에서 벽을 만나면 상하좌우로 더해주는 방식으로 사용했다. 여기서 문제는 같은 덩어리를 상하좌우 탐색에서 중복 계산할 수 있다는 점이다. 이를 없애기 위해 유니온 파인드로 한 덩어리를 그룹화하였고, 상하좌우를 탐색할 때 이미 탐색한 그룹이면 카운트하지 않게 구현했다.#include #include #include #include #include using namespace std;#define MAX 1000int N, M;int dy[] = { -1, 0, 1, 0 };int dx[] = { ..

이 문제는 유니온 파인드, 배낭 문제 알고리즘을 이용해서 풀었다. 한 아이의 사탕을 뺏으면 친구들의 사탕도 모조리 뺏는다는 조건을 보고 유니온 파인드를 떠올렸다.친구 그룹을 형성하여 총 사탕 수와 총 인원 수를 각각 candy, groupCount에 저장했다. 또한 각 그룹을 선택할지 말지에 대한 배낭 문제와 동일하다는 생각이 들어 배낭 문제의 알고리즘을 그대로 사용했다.이 때 주의할 점은 dp[i - 1]에 대한 비교가 계속되므로 i = 0일 때 i = -1인 지점을 찾게 되어 오류가 발생할 수 있다.따라서 i = 1부터 시작하도록 만들어 문제를 해결했다.#include #include #include #include using namespace std;#define MAX 30000vector> fr..

이 문제는 유니온 파인드를 이용해서 풀었다. 처음에는 dfs를 이용해서 그룹 수를 찾으면 되겠다고 생각했지만, 이는 정확한 정보를 주지 못한다.D L L LD UR R U와 같은 경우 만약 (0, 0)부터 탐색을 돌 경우 왼쪽 원에만 visited가 true가 되고 맨 오른쪽 L는 적용되지 않는다. 따라서 그룹이 2개가 나오게 된다. 그러나 전체가 그룹 하나로 이루어져야 정답이 된다. 따라서 이 같은 경우를 없애기 위해 유니온 파인드로 그룹화를 했다. 각 좌표에 대해 번호를 매기고, 이 번호를 토대로 그룹화를 하여 쉽게 문제를 풀 수 있었다. 주의할 점은 safe zone의 개수를 구할 때 set를 사용하면 시간 초과가 난다는 점이다. 단순히 for문 두개로 푸니 정답이 나왔다.#include #in..

이 문제는 최소 스패닝 트리를 이용한 문제이다. 최소 스패닝 트리는 모든 정점을 연결한 최소의 가중치의 부분 그래프를 의미한다.문제에서는 마을을 두 개의 분리된 마을로 분할해야 하고, 마을에는 집이 하나 이상 있어야 한다는 요구사항이 있다. 최소 스패닝 트리가 모든 정점을 연결한 최소 가중치의 부분 그래프라면, 크루스칼 알고리즘을 통해 MST를 만들 때 마지막으로 merge된 간선을 빼준다면 두 개의 부분 트리가 만들어 질 것이라고 예상하고 문제를 풀었고 정답을 맞출 수 있었다.#include #include #include using namespace std;#define MAX 100000struct Edge { int a; int b; int cost;};vector edges;int N, M;in..

이 문제는 백트래킹 문제이다. 시간 복잡도를 조금이라도 줄이려면 애초에 백트래킹 탐색을 할 때 사전식으로 앞서도록 탐색하게 만들면 된다. 어떤 좌표 (y, x)가 있을 때, 이를 3으로 나눴다가 3으로 곱하면 해당 칸의 시작 인덱스를 구할 수 있다. 이걸 이용하면 좀 더 쉽게 구현할 수 있다. 물론 이는 0부터 시작해서 8로 끝나는 인덱스를 이용할 때 활용 가능하다.#include #include #include using namespace std;#define SIZE 9int board[SIZE][SIZE];void input() { for (int y = 0; y > c; board[y][x] = c - '0'; } }}pair findStart(int y, int x) { y /= 3; x ..