애송이의 유산

문제 풀이 처음에는 그래프나 탐색형 문제로 생각했다. 그러나 이것은 방법도 난해했고, 시간 복잡도도 기본적으로 벡터 최대 크기가 1000 * 1000 인데, 그 안에서 또 정사각형인지 체크하는 방식도 최대 1000 * 1000 만큼 걸릴 수 있기에, 1000 * 1000 * 1000 * 1000으로 시간초과가 난다는 점이 문제였다. 이 문제는 dp 문제였다. 정사각형을 탐색할 때 나는 board에서 1을 찾으면 왼쪽 위의 1로 생각해서 밑으로 내려갈 생각을 했는데, 1을 왼쪽 위가 아닌 오른쪽 아래로 두고 계산을 하는 것이 방법이였다. 왜 dp 인가?? 그림을 그려서 확인해보면, (3, 2)의 1을 오른쪽 밑 꼭짓점으로 두는 정사각형 중 가장 큰 정사각형을 찾으려면, board[2 - 1][3], boa..

문제 풀이 문제는 이해하기 쉽지만, 아이디어를 떠올리는 것이 굉장히 어려웠다. number 최대 길이는 1000000이기에 조합을 위해 dfs를 쓰거나 하면 시간 초과가 날 것이다. 그리디(greedy)한 , 즉 매 순간 최선의 결과를 반환하는 걸 고르는 방법을 통해 문제를 풀어야한다. 한 번 예제를 따라가면서 방법을 찾아보도록 하자. 위 그림은 0이 10개 있는게 아니라, 무작위 숫자가 10개 있는 걸 나타낸 그림이다. k는 4로 주어진 상태이다. 이 상태라면 우리는 10개의 숫자 중 총 4개의 숫자를 제거해서 최대의 숫자를 만들어야한다. 최대의 숫자는 당연하게도 자리수가 크거나, 앞자리 숫자가 제일 큰 숫자일 것이다. 여기서 자리수는 고정되니, 앞자리 숫자가 최대한 크도록 숫자를 골라야 할 것이다. ..

문제 풀이 numbers의 길이가 7 이하이니, 완전 탐색을 고려할 수 있다. numbers에서 몇 개 뽑아 나열해서 숫자를 만든다는 것은 순열을 떠올리게 만든다. numbers가 최대 7자이니 순열 공식 7 * 6 .. 2 * 1 = 2520인데, 만약 소수 판별 부분에서 2부터 나눠가는 방식을 사용한다면 어떻게 될까? 7자리면 숫자 크기가 1000000을 넘어갈 수 있는데, 이러면 2520 * 1000000 = 2520000000으로 시간 초과가 발생할 위험이 있다. 즉 소수를 구하는 식을 에라토스테네스 체를 이용해야한다. 순열을 구하는 방식은 재귀함수를 이용한 완전 탐색을 이용하거나, c++에서 제공하는 next_permutation이 있다. 코드 #include using namespace std..

문제 풀이 예제로 봐도 처음에는 문제가 이해가 잘 되지 않았다. 문제에 다리를 지나는 시간은 1초에 1씩 간다는 얘기만 있어도 좋았을 것 같다. 즉 트럭 하나가 bridge_length 가 2인 다리를 지나는 시간은 2초가 걸리는 것이다. 다른 사람이 작성한 표를 보니, 문제 이해가 단박에 되었다. 예시를 표로 작성해서 가져온 것이다. 7이 다리에 있는 동안 그 뒤의 4는 들어오지 못할 때, 7만 계속 전진해서 2초 뒤 빠져나가는 것이다. 이걸 보고 문제를 이해할 수 있었다. 위의 방식을 그대로 코드로 구현했다. #include using namespace std; int solution(int bridge_length, int weight, vector truck_weights) { int answer..

문제 풀이 문제에도 언급했듯, 총합을 구하고 반 나눈 수가 각 큐 안에 든 수들의 합이 되도록 해야한다. 두 큐에 든 숫자들의 합이 30이면, 각 큐의 합은 각 각 15가 되도록 맞추는 것이다. 그렇다면 언제 -1이 나오게 되는가? 1. 두 큐의 합이 홀수면 반으로 나눌 수 없으니, 어떻게 해도 두 큐의 합이 같도록 할 수 없다. 2. queue 사이즈 만큼의 횟수를 두 번 이상 반복하면, 각 큐에 들어있던 수가 서로 뒤바뀐다. 즉, 그 이상 반복하면 의미가 없다. int answer = 0; long long sum1 = 0; long long sum2 = 0; long long sum; queue q1; queue q2; for(int i = 0 ; i < queue1.size(); i++){ sum..

문제 풀이 처음에 생각한 풀이방법은 xor 비트 연산을 이용하는 것이었다. 문제 예시로 7과 8 사이의 다른 비트 개수를 셀 때 xor를 사용하면 4개라는 사실을 쉽게 알 수 있었기에 그런 생각이 들었다. 문제는 xor을 이용해서 numbers[i]보다 큰 수들을 차례로 찾아가니 시간 초과가 발생했다. 문제에서 numbers의 최대 원소 크기는 10의 15승으로, 반복문을 30번 정도로 설정해도 한 번 xor 비트 연산 시 꽤 많이 비교하는 작업이 발생했다. 이 때문에 numbers의 길이 100000 x 반복문 대략 50번 (bit를 1씩 왼쪽 쉬프트 연산하며 1 개수를 셈) x 내부에서 비트 연산 횟수 (xor 연산하는데 걸리는 시간) 을 계산하면 1억을 넘어가게 되었다... 그래서 다른 방법을 찾아..