재원블로그 재원블로그

이 문제는 그리디한 방식으로 풀었다. 일단 이 문제에서 입력 배열이 최대 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 ..

이 문제는 맵을 이용해서 풀었다. 일단 입력이 매우 작으므로 단순 구현으로도 시간 초과가 나지 않는다. 시간 단축을 위해 map에서 skill에 나오는 알파벳을 true로 설정했다. skill_trees에 대해 반복문을 돌리면서, 해당 문자열 루프 안에서 mp[s]가 true일 때 skill에 알맞은 순서이면 index++을, 맞지 않으면 break를 통해 다음 문자열을 본다. 문제에 주어진 대로 구현하면 풀리는 문제이다. #include #include #include using namespace std; int solution(string skill, vector skill_trees) { int answer = 0; for (string& st : skill_trees) { int index = 0..

이 문제는 주어진 대로 구현하면 풀리는 문제이다. 일단 길에 대한 방문 여부를 map visited로 표현했다. 이는 y, x, ny, nx 총 4개의 정수로 이루어져있고, (y, x) 좌표에서 (ny, nx)로 가는 간선의 표현이다. y, x 각각 -5부터 5까지의 범위이므로 단순 배열로 표현하면 구현이 살짝 헷갈려서 map을 이용해서 풀었다. #include #include #include #include using namespace std; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, -1, 0, 1}; #define UP 0 #define LEFT 1 #define DOWN 2 #define RIGHT 3 bool inRange(int y, int x) { if (-5