문제https://www.acmicpc.net/problem/1517풀이버블 소트에서 swap 되는 횟수를 세는 문제다.문제가 버블 소트라고 해서 버블 소트로 구현을 한다면 시간초과가 나는 문제다.버블 소트에서 swap 되는 조건을 이용하여 merge sort를 이용해야한다.소스코드#include using namespace std; #define MAX_N 500000 int n; int A[MAX_N]; int B[MAX_N]; long long solve(int start, int end) { if (start == end) return 0; int mid = (start + end) / 2; long long ans = solve(start, mid) + solve(mid + 1, end); in..
문제https://www.acmicpc.net/problem/1891풀이입력으로 좌표평면의 크기와 해당하는 좌표의 사분면 조각의 번호가 주어진다.이 문제는 처음에 주어진 사분면 조각의 번호가 해당하는 좌표를 구한 후 x, y값을 더한 좌표값의 조각의 번호를 출력하면 되는 문제이다.정답 비율이 24% 정도로 매우 낮은 문제였고, 제출자 또한 200명 정도로 너무 적어서 검색해도 잘 나오지 않는 문제였다.다른 사분면 문제와 같이 재귀호출로 푸는 문제였는데 d의 크기가 50까지여서 2^50까지 계산하기 때문에 자료형을 long long으로 해야하는 문제다.먼저 주어진 사분면 조각의 번호가 해당하는 좌표를 얻는 함수로 좌표를 얻고 해당 좌표에서 이동한 좌표의 사분면 조각의 번호를 출력하는 식으로 해결했다.정답 ..
문제https://www.acmicpc.net/problem/1074풀이분할정복과 재귀호출을 통해 해결하는 문제다. 한시간을 넘게 생각했는데 내가 생각한 방식으로 결국 구현을 하지 못했다.recursion을 구현하는게 너무 힘든 것 같다 ㅠㅠ 하…관련 강의를 찾아보니까 원리는 이해하겠는데 어떠한 것을 구현하려고 하면 머리가 터질 것 같다.문제를 구글링 해서 사람들이 올린 소스코드를 봐도 너무 이해하기가 힘들다.나중에 다시 한 번 풀어봐야겠다.소스코드#include using namespace std; int N, r, c; int x, y, ans; void solve(int x, int y,int n) { if (x == r && y == c) { cout = y) { solve(x, y, n / 2)..
문제https://www.acmicpc.net/problem/2263풀이과정트리의 순회 과정을 정확히 숙지하고 있어야 풀 수 있는 문제다.문제의 입력으로 인오더와 포스트오더가 주어지는데 출력으로 프리오더가 나오게 해야한다.인오더는 (왼쪽)(루트)(오른쪽) 으로 순회하고 포스트오더는 (왼쪽)(오른쪽)(루트)로 순회한다.잘보면 루트를 구하는 방법으로 포스트오더의 끝을 선택하는 방법이 쉬워보인다.한시간 반동안 뭔가 답에 근접한 생각을 한 거 같아서 계속 생각하고 구현해봤지만 결국 되지 않아서 답을 찾아봤다.내가 생각한대로 함수를 하나 만들고 왼쪽, 오른쪽으로 재귀호출을 통해 해결하는 문제였지만 스스로 해결하지는 못했다. 휴…post_order의 끝을 이용해 루트를 구하고 구한 루트를 in_order에서 찾아 ..
문제https://www.acmicpc.net/problem/11729풀이과정하노이 탑의 이동 횟수를 구하는 문제다. 하노이 탑의 개념은 알고 있었지만 코드로 구현하는건 처음이라 신기했다.분할 정복 문제라는 것을 알고 시작했지만 어떻게 해결해야될지 몰라서 조금 오래 걸린 것 같다. 답을 보는게 습관이 된 것 같다. 이제 한시간 안에 답을 보는건 그만 좀 해야겠다.solve(n,x,y) 를 n개의 원판을 x->y 로 옮기는 함수라고 하고 재귀호출로 풀면 해결이 된다.그리고 처음에는 원판을 옮길 때마다 횟수를 증가시켜서 마지막에 횟수를 출력했는데 검색을 해보니까 하노이 탑의 이동횟수에 대한 공식이 있었다.그래서 pow() 함수를 통해서 출력을 했는데 틀렸습니다가 떠서 왜 그런가 살펴봤더니 N이 커질수록 do..
문제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로 저장할 생각을 하지않고 또 다른 배열을 만들어서 저장하려해서 구현이 복잡해져서 각 정점까지의 거리를..