재원블로그 재원블로그

이 문제는 재귀를 이용해서 풀었다. 이 문제에서 핵심은 상하좌우로 이동할 때 장애물 또는 벽에 부딪힐 때까지 움직인 것을 한 번의 움직임으로 치는 걸 구현하는 것이다. 백준 삼성 SW 역량 테스트 기출 중에 판을 기울여서 구슬 두 개 빼는 문제가 있는데 그와 같은 방식이다. 또한 어떤 점을 도달했을 때 그 점을 처음 도달했다고 해서 반드시 최단 횟수로 도착한 것이 아니라는 점도 굉장히 중요하다. 따라서 visited 배열을 단순히 bool 로 선언하여 true면 재귀 호출하지 않는 방식으로 구현하면 테스트 케이스 1번이 7이 아닌 9가 나오게 된다. 이 때 약간의 다익스트라 알고리즘 개념을 사용했는데, 다익스트라에서는 거리 배열에 이미 유효한 값이 저장되어 있더라도 지금 경로의 비용이 더 작으면 값을 바..

이 문제는 수학을 이용해서 푸는 문제이다. 일단 이 문제에서 주어지는 입력값 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..