문제https://www.acmicpc.net/problem/1780풀이과정분할정복의 기초 문제이다. 문제의 규칙을 보면 1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. 2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 라고 하고있다. 규칙을 통해 문제 해결법을 생각해보면 종이는 항상 같은 숫자들로만 이루어져있어야 한다. 아니면 9개의 종이로 잘라야 된다.문제는 (0,0)부터 가로로 n개, 세로로 n개의 종이 개수를 파악해야한다.하지만 이를 작은 문제로 나눠보면 (x,y)부터 가로로 n개, 세로로 n개의 종이개수를 파악하는 것으로 생각할 수 있다.말로 설명을 잘 못하겠다. 소스코드를 보는 편이 더 이해가..
문제https://www.acmicpc.net/problem/11728풀이과정머지소트 과정 중 두 개의 정렬 된 배열을 합치는 과정을 구현하는 문제이다.처음에는 벡터를 이용해 구현하려 했지만 시간초과가 났다.그 후에 머지소트에서 merge 과정대로 구현을 했고 맞을 수 있었다.문제를 풀이하면서 또 하나 배운 사실이 있다. 나는 cin, cout의 사용이 더 편리하다고 생각해서 cin, cout을 쓰는데 속도 때문에 ios::sync_with_stdio(false)를 항상 맨 위에 쓰고 시작하는데 속도를 위한거라면 이것말고도 cin.tie(0)을 해줘야 된다고 한다.실제로 cin.tie(0) 만을 추가해봤는데 속도가 더 빨라졌다 앞으로는 두 개를 무조건 맨 위에 쓰고 시작해야겠다.소스코드#include #..
문제https://www.acmicpc.net/problem/10816풀이과정전에 풀었던 숫자 카드는 그냥 카드뭉치에 숫자가 존재하는지의 여부만 판단하면 됐는데 이 문제는 카드뭉치에서 숫자가 몇 개 존재하는지까지 알아야되는 까다로운 문제다.역시 이진탐색을 이용해서 풀어야되며 내가 전부터 헷갈려 하던 lower_bound와 upper_bound를 쓰면 쉽게 해결할 수 있는 문제다.예제의 입력을 보자. 6 3 2 10 10 10 -10 -10 7 3 이러한 카드뭉치(vector card)가 있을 경우 lower_bound(card.begin(),card.end(),10)은 10이 존재하는 처음의 위치를 반환하게 된다.그리고 upper_bound는 10이 마지막으로 존재하는 위치 + 1 을 반환하게 된다.문제..
문제https://www.acmicpc.net/problem/10815풀이과정하나의 카드뭉치와 카드뭉치 속 카드들의 숫자가 주어진다. 그리고 또 다른 입력으로 숫자들이 들어오고 그 숫자들이 카드뭉치에 있는지 없는지 판단해서 출력하는 문제이다. 이 문제는 이진탐색으로 풀어야되는 문제이다. 이진탐색 구현은 쉽게 했지만 이상하게 시간초과가 나서 당황했었다. 이진탐색을 해서 숫자가 존재하면 cout // printf 사용 #include #include using namespace std; #define MAX_N 500001 int N, M; int card[MAX_N]; bool Binary_search(int target) { int left, right; left = 0; right = N - 1; wh..
문제https://www.acmicpc.net/problem/1167풀이과정이제는 DFS, BFS 구현에 대해 좀 감이 오나 싶었는데 아직도 구현이 서툰 것 같다. 기본적인 구현문제들을 다시 한 번 풀어봐야겠다. 이 문제는 트리의 지름을 구하는 문제로 트리의 지름을 구하는 방법은 정해져있다. 먼저 임의의 정점부터 모든 정점까지의 거리를 구하여 가장 먼 거리를 가진 정점을 구한다. 그 후에 그 정점으로부터 모든 정점까지의 거리를 다시 구해서 그 거리들 중 가장 먼 값이 트리의 지름이 된다.시간제한 1시간을 잡고 풀었는데 DFS로 풀어야할 것 같다고 생각하여서 한시간동안 개뻘짓을 했다. 또 가중치를 pair로 저장할 생각을 하지않고 또 다른 배열을 만들어서 저장하려해서 구현이 복잡해져서 각 정점까지의 거리를..
문제https://www.acmicpc.net/problem/11725풀이과정각 노드의 연결 상태를 입력으로 받고 각 노드의 부모노드 번호를 출력하는 문제이다. 트리의 입력을 그래프처럼 인접리스트로 받은 후에 BFS로 탐색하며 parent 배열에 부모노드 번호를 저장하면 된다.처음 예제입력을 BFS로 탐색해보면 처음 1 다음에는 큐에 4와 6이 들어가며 parent[4]와 parent[6]의 값은 부모노드 번호인 1이 들어가게 된다. 다음 과정을 살펴보면 큐의 front값이 4이므로 parent[2]와 parent[7]의 값은 부모노드 번호인 4로 된다. 이렇게 BFS를 통하여 부모노드를 저장하는 방법으로 해결할 수 있는 문제였다.소스코드#include #include #include using name..
문제https://www.acmicpc.net/problem/1991풀이과정기본적인 트리의 순회과정 구현을 묻는 문제다. 전위 순회(preorder)는 root->left->right 중위 순회(inorder)는 left->root->right 후위 순회(postorder)는 left->right->root어떻게 구현을 해야할지 조금만 생각해보면 쉽게 풀 수 있는 문제다. 문제에서 입력되는 트리는 자식을 최대 2개로 가지는 이진 트리이므로 배열로 트리를 표현할 수 있다. a[26][2] 라는 배열을 선언하여 각 알파벳을 부모노드로 가지는 자식을 저장하면 된다. 각 순회의 구현은 재귀호출을 통해 구현하였다.소스코드#include using namespace std; int a[26][2]; int N; v..
문제https://www.acmicpc.net/problem/2146풀이과정단지번호붙이기와 토마토 문제를 합친 개념으로 보면 된다. 제한시간을 한시간으로 두고 풀어보려고 했지만 섬이 있는 곳들을 그룹으로 만드는거 이후 거리를 계산하는 방법이 떠오르지 않아서 검색을 통해 해결했다. 섬들을 그룹으로 묶어서 g 배열에 저장한다.각 그룹마다 BFS를 통해 거리를 계산해 grup_dis 배열에 저장한다.원래 입력값으로 저장되어있는 a 배열과 그룹으로 나누어 저장한 g 배열을 이용하여 현재 그룹의 아닌 다른 섬까지의 거리를 계산한다.최소값을 출력한다. 3번 과정을 구현하는 소스코드를 보고도 이해하기 힘들었다. DFS, BFS 활용 문제는 정말 필수로 나오는 문제이니 관련 문제를 찾아서 더 많이 풀어봐야겠다.소스코드..
문제https://www.acmicpc.net/problem/7576풀이과정BFS로 해결할 수 있는 문제. 익은 토마토부터 BFS를 시작하여 거리를 재는 식으로 풀이하면 된다. 문제에서 토마토가 모두 익지 못할 경우 -1을 출력하라고 했는데 이 예외를 까먹고 하지 않아서 몇 번 틀렸다.소스코드#include #include using namespace std; #define MAX 1000 int N, M; int map[MAX][MAX]; int tomato[MAX][MAX]; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; int main() { ios::sync_with_stdio(false); cin >> M >> N; queue q; for (int ..
문제https://www.acmicpc.net/problem/2178풀이과정시작점부터 이동할 수 있는 칸을 이용해서 (N,M)까지 가야한다. 주어진 칸을 최소한으로 이용하며 도착할 수 있을 때 최소 칸 수를 출력 해야한다.기본적인 BFS 문제라고 한다. DFS로는 풀 수 없는 문제다. 문제를 풀다가 DFS와 BFS를 어떨 때 써야 좋을까 라는 생각이 들어서 검색해봤다.DFS는 사이클 탐지, 위상정렬 BFS는 최소신장트리, 최단경로소스코드#include #include #pragma warning(disable:4996) #define MAX 100 using namespace std; int map[MAX][MAX]; int ans[MAX][MAX]; bool chk[MAX][MAX]; int N, M;..