재원블로그 재원블로그

이 문제는 투 포인터와 맵을 이용해서 풀었다. gems 배열의 최대 크기가 100,000 이므로 O(n) 시간 이내의 알고리즘을 구상해야 한다. 구간에 대한 정답을 도출해야 하므로 투 포인터를 떠올렸고, 개수에 상관없이 종류가 모두 들어가야하므로 맵을 떠올렸다. 일단 투 포인터를 사용하는 방식에는 한쪽에서 모두 시작하는 것과 양쪽에서 서로 시작하는 것이 있는데, 최소 구간이 같을 경우 시작 진열대 번호가 같아야하므로 왼쪽에서 모두 시작하는 쪽이 더 직관적이라고 생각했다. 처음에는 구간을 찾고 모든 보석의 종류가 들어있는지를 확인하기 위해 mp을 순회하면서 개수를 세는 쪽으로 하려 했으나, 이 방식은 시간 초과가 날 것이다. 만약 입력 배열이 10만이고 각 원소가 모두 다른 보석이라면, 10만 * 10만의..

이 문제는 맵, 백트래킹, 정렬을 이용해서 풀었다. 일단 입력으로 주어지는 배열들이 매우 작으므로, 백트래킹을 사용해도 시간 초과가 나지 않는다. 이 문제는 단순히 문제에서 주어진 대로 구현하면 되지만, 몇 가지 주의할 사항이 있다. 첫번째로 백트래킹을 할 때, temp와 limit가 같아질 때 cnt 맵에 +1을 하게 되는데, 이 때 temp는 정렬되어 있어야 한다. 만약 temp가 XW인 경우에, WX가 카운트되어야 하는 것이다. 두번째로, 모든 연산이 끝난 후에도 answer 배열이 한번 더 정렬되어야 한다. 이 두개만 주의한다면 구현은 어렵지 않게 할 수 있다. #include #include #include #include #include using namespace std; map cnt; v..

이 문제는 그리디한 방식으로 풀었다. 일단 이 문제에서 입력 배열이 최대 30만의 길이를 가지고 있다. 즉, O(n) 이하의 알고리즘을 선택해야하고, 그리디, dp, 이분 탐색 등 O(n) 이하의 시간을 사용하는 알고리즘 중에 그리디가 이 문제와 맞다고 생각했다. dp를 사용하기에는 입력 배열의 크기가 너무 커 dp 배열을 만들 수 없을 것이라 판단했고, 정렬이 불가능하므로 이분 탐색도 불가능하다고 판단했다. 일단 base case로 두 배열의 총 합이 홀수면 절대 같게 나눌 수 없으므로 -1을 리턴한다. 그 다음 처음부터 두 배열의 각 합이 같으면 바로 0을 리턴했다. 이 문제에서 핵심 아이디어는 두 배열 중 더 합이 큰쪽에서 작은 쪽으로 숫자를 보내줘야한다는 것이다. 그리고 어떻게 해도 같게 만들지 ..

이 문제는 규칙성을 찾아서 구현하는 문제이다. 일단 n의 최댓값이 1,000이고, 마지막 숫자는 1000 * 1001 / 2 = 500,500이 될 것이므로 O(n)의 알고리즘으로 충분히 가능하다. 내가 활용한 규칙성 첫번째는 (n - 1) / 3 + 1 이 총 삼각형의 개수라는 것이다. 각각 n이 1, 4, 7, 10일 때 삼각형 1, 2, 3, 4개이다. 두번째는 각 삼각형의 시작 위치가 0,0부터 시작해서 y좌표는 2씩, x좌표는 1씩 증가한다는 것이다. 이 두가지 규칙을 활용해서 fill 함수를 만들었고, dist는 몇번째 삼각형인지를 나타낸다. fill 함수는 해당 삼각형의 외곽에 대한 숫자를 집어넣는 함수로 생각하여 구현했다. endY와 endX를 구할때 실수만 없다면 구현도 쉽고, 문제도 쉽..

이 문제는 분할 정복을 이용해서 풀었다. 일단 이 문제에서 이차원 배열의 최대 크기는 1,024 * 1,024 = 1,048,576 이다. 그리고 범위 내 모든 수가 같지 않을 시, 즉 최악의 경우 0101...과 같은 형태일 경우 log4 (1,048,576) = 10이므로 시간 안에 풀 수 있다. 문제에서 주어진 순서가 있는데, 그 순서 그대로 짜면 정답이 나오는 쉬운 문제이다. 내가 고안한 수도코드는 다음과 같다. 1. 영역 안에서 모든 수를 카운트함 2-1. 만약 모든 수가 같다면 그 같은 수에 대한 answer++ 함수 리턴 2-2. 그렇지 않다면 정확히 4개의 영역으로 자른 것에 대한 재귀 호출 수행 위 수도코드를 그대로 구현하면 정답을 도출해낼 수 있다. #include #include us..

이 문제는 완전 탐색과 자료구조를 이용해서 풀었다. 일단 이 문제는 배열의 크기가 최대 30 * 30 이고, 구현을 어느 정도 최적화한다면 충분히 완전 탐색으로도 충분히 가능하다고 판단했다. 반복문은 2 * 2가 모두 같은 경우가 없을 경우에만 break 하도록 구현했고, 그 안의 내용은 다음과 같은 수도 코드를 짜서 구현했다. 1. 순회 - 4개 만족하는거 true로 바꿈 2. true의 개수를 세며 answer++ - 해당 블록 ' '로 바꿈 3. 이동 - 위에서 아래로 내려옴 - 여기가 중요 4. 다시 1로 -> 하나도 없을 때까지 1번과 2번은 단순히 구현하면 되는 부분이라 쉬웠지만, 3번을 구현하는 방법을 떠올리는게 어려웠다. 처음에는 temp라는 벡터를 하나의 x마다 만들어 빈칸이 아닌 부분을..

이 문제는 규칙성을 찾아서 푸는 문제이다. 일단 입력 배열의 길이가 최대 100,000 이고, 배열 원소의 최대 크기는 10^15이다. 즉, 1,000,000,000,000,000 이고, 이를 이진수로 바꾸면 11 1000 1101 0111 1110 1010 0100 1100 0110 1000 0000 0000 0000 최대 길이 50의 이진수가 나온다. 따라서 100,000 길이 배열의 모든 원소가 10^15인 숫자를 이진수로 바꾸는데까지는 시간 초과가 걸리지 않는다. 처음에는 배열의 한 숫자에 대해서 해당 숫자 + 1부터 루프를 돌려 이진수로 바꾸고, 비트가 맞지 않는 수를 세어 처음으로 2 이하인 수를 리턴했으나, 이런 식으로는 시간 초과가 난다. 단적인 예로 1111 1111 1111 1111 1..

이 문제는 주어진 대로 구현하여 푸는 문제이다. 이 문제에서 중요한 건 HEAD와 NUMBER이고, TAIL은 정렬 기준에 아예 없으므로 구하지 않아도 된다. 일단 가장 중요한 조건은 HEAD와 NUMBER까지 같을 때, 처음 순서 그대로 유지되어야 한다는 것이다. 처음에는 이를 무시하고 일단 넣고 정렬하면 알아서 그대로 될 것이라 생각했지만, 오답이 나왔다. 나는 구조체를 이용해서 index들을 저장했지만, 다른 방식을 사용하더라도 반드시 그대로 넣는 로직이 들어가야 한다. 이 문제에서는 STL sort를 사용할 때 compare 함수를 선언하여 정렬 기준을 설정할 수 있다는 사실과, string을 그대로 비교할 수 있다는 사실만 알고 있으면 어렵지 않게 풀 수 있다. #include #include ..