재원블로그 재원블로그

이 문제는 수학을 이용해서 푸는 문제이다. 일단 이 문제에서 주어지는 입력값 k, d 가 모두 [1, 1,000,000] 이므로 O(N) 이하 알고리즘을 고안해야 한다. 이 문제를 풀기 위해서 우선 1사분면에 반지름이 d인 원을 그려봤다. a * k, b * k 에서 a와 b가 정수로 주어지기 때문에 점이 모눈종이에 규칙적으로 그려질 수 있다. x^2 + y^2 = d^2 이기 때문에 y^2 = d^2 - x^2 이 되고, y = (d^2 - x^2)^(1/2) 가 된다. 이 값은 정수가 아닐 수 있으므로 double 로 계산하고, 이를 int로 캐스팅하면 정숫값이 나오게 된다. 이 정숫값을 k로 나누면 해당 x 값에서의 y가 d 이하인 y좌표의 개수가 나오고, 이를 반복문으로 돌려 계산하면 정답이 나온..

이 문제는 정렬을 이용한 문제이다. 문제의 요구사항을 그대로 구현하면 간단하게 풀리는 문제였다. 한 가지 주의할 점은 인덱스들이 전부 [1, N] 로 주어짐에 반해, data 는 [0, N - 1] 인 것만 헷갈리지 않으면 쉽게 풀 수 있다. #include #include #include using namespace std; int sortIndex; bool compare(vector& left, vector& right) { if (left[sortIndex] == right[sortIndex]) { return left[0] > right[0]; } return left[sortIndex] < right[sortIndex]; } vector makeSortedData(vector data) { s..

이 문제는 비례식을 이용해서 푸는 문제이다. 이 문제에서 핵심은 map을 사용하거나, vector를 사용해서 해당 비례식에 맞는 몸무게를 한번에 찾아내는 것이다. 첫번째로 1 : 1, 1 : 2, 2 : 3, 3 : 4 로 비례식이 좁혀진다는 것을 발견해야한다. 시소가 2m, 3m, 4m 씩 자리가 양 쪽에 있기 때문에, 나올 수 있는 경우의 수는 2:2, 2:3, 2:4, 3:2, 3:3, 3:4, 4:2, 4:3, 4:4 가 된다. 약분을 하고 중복된 가지수를 제거하면 1:1, 1:2, 2:1, 2:3, 3:2, 3:4, 4:3 이 나오는데, 순서만 바뀐 것도 제거해주면 최종적으로 1:1, 1:2, 2:3, 3:4 가 나온다. 두번째로 몸무게에 대해 개수를 세고, 몸무게에 대해 루프를 돌면서 상대방의..

이 문제는 유클리드 호제법을 이용해서 푸는 문제이다. 배열의 최대 길이가 50만이므로, O(n) 알고리즘을 사용해서 풀어야 한다. 철수나 영희가 가진 모든 숫자를 나눌 수 있고, 반대는 나눌 수 없는 가장 큰 수를 찾고, 없으면 0을 리턴하는 문제이다. 이 때 모든 숫자를 나눌 수 있다는 것에 집중했고, 그 중 가장 큰 수에 집중했다. 이 말이 곧 최대공약수를 나타내는 말이기 때문이다. 따라서 유클리드 호제법을 이용하여 gcd를 각각 구하고, 반대편의 배열에 루프를 돌며 나눌 수 있는지를 판단한다. 만약에 두 케이스 모두 나눌 수 있다면, 0을 리턴하도록 알고리즘을 구현했다. 최악의 경우에도 50만 + 50만 정도의 연산을 수행하므로, 1초 안에 문제가 풀린다. #include #include #incl..

이 문제는 그리디 알고리즘으로 풀었다. 일단 완전 탐색은 어림도 없다. 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 이 +, - 각각 존재하므로 버튼의 총 수는 18개가 될 수 있는데, 18^7 만 해도 약 6억번의 연산을 수행해야 하므로 1초가 훌쩍 넘는다. 다이나믹 프로그래밍은 메모리 문제가 발생할 수 있고, 숫자의 범위가 커 애초에 잘 겹치지도 않아 시간이 오래 걸린다. 이 문제의 핵심은 1의 자리부터 각 자리의 해당 숫자를 보고 올릴지 말지를 판단하는 아이디어로 접근하는 것이다. 가령 16이라면 1의 자리부터 시작하면 6이고, 올렸을 때 4번, 내렸을 때 6번을 통해 해당 자리를 0으로 만들 수 있다. 따라서 올리고, 20이 되었을..

이 문제는 다이나믹 프로그래밍의 아이디어를 통해 푼다. 이 문제를 고민하다가 아무런 아이디어가 떠오르지 않아 검색을 하고 풀었다. 이 문제의 핵심은 현재 위치를 (y, x) 라고 한다면 현재 위치의 숫자가 1인 경우, 왼쪽, 왼쪽 위, 위쪽이 모두 1이어야 한 변의 길이가 2, 넓이가 4인 정사각형이 된다는 사실이다. 한 변의 길이가 3인 2차원 배열에서의 예시를 보면 // 초기 상태 1 1 0 1 1 1 1 1 1 // (1, 1) 부분의 계산 1 1 0 1 2 1 1 1 1 // (1, 2) 부분의 계산 1 1 0 1 2 1 1 1 1 // (2, 1) 부분의 계산 1 1 0 1 2 1 1 2 1 // (2, 2) 부분의 계산 1 1 0 1 2 1 1 2 2 와 같이 나타낼 수 있다. 각 배열의 요소..

이 문제는 최단 경로 알고리즘을 사용해서 풀었다. 집의 개수가 최대 50개이고, 1번 집부터 모든 각 집까지의 비용이 K 이하인 모든 집을 찾는 문제이다. 플로이드 워셜 알고리즘은 O(N^3) 이므로, 50^3 = 125,000 이므로 1초 내에 충분히 풀 수 있다. 한 가지 유의할 점은 같은 집 쌍에 대해 여러 도로가 존재할 수 있다는 것이다. 이 경우 여러 도로 중 가장 cost가 작은 도로를 해당 집 쌍의 비용으로 정하면 쉽게 풀 수 있다. #include #include #include using namespace std; #define HOUSE_MAX 50 #define INF 1000000000 int dist[HOUSE_MAX + 1][HOUSE_MAX + 1]; void floydWars..

이 문제는 다이나믹 프로그래밍을 사용하여 최적해를 구한 뒤, 최적해로 다다르는 경로의 개수를 세는 문제이다. 이 문제에 대해 경로의 개수를 세는 부분이 어려웠는데, 앞서 구했던 dp 배열을 통해 구할 수 있다는 힌트를 얻었다. 바로 아래와 아래 오른쪽 둘 중 dp 배열의 값이 큰 쪽으로 재귀를 호출하며, 만약 같을 경우에는 둘 다 최적해 경로일 가능성이 있으므로 둘 다 호출한 뒤 더해주면 된다. 이미 dp 배열을 사용하는데 왜 countDP가 따로 필요할 까 의문이 들었는데, 만약 삼각형의 모든 수가 같다면 재귀 호출을 매우 많이 하게 된다. 이를 방지하기 위해서는 coundDP가 또 필요하게 된다. #include #include using namespace std; #define MAX 100 int..