재원블로그 재원블로그

이 문제는 구현 문제인 것 같다. 처음에는 입력 숫자의 최대 크기가 1,000,000 이고, 이에 대한 이진수는 1111 0100 0010 0100 0000 이고, 다음 큰 수는 대략 1111 0100 0010 1000 0000 으로 1,000,064가 되어 최대 시간 복잡도가 2^20 * 20 = 약 1억이라고 생각해 완전 탐색으로 구현하려고 했다. 그러나 생각을 더 해보면 n + 1 부터 시작해서 1의 개수가 같은 이진수가 나오는 숫자까지 반복하면 훨씬 짧은 수의 반복문으로 해결할 수 있을 것 같았다. 다음 큰 숫자가 생각보다 멀리 있지 않다는 점을 이용해서 풀었고, 정답을 맞출 수 있었다. #include #include #include using namespace std; string toBina..

이 문제는 다이나믹 프로그래밍 문제이다. 입력 n의 최대가 100,000 인데, 이를 단순히 재귀 함수로 구현해서 풀면 너무 많은 콜 스택으로 인해 프로그램이 작동하지 않는다. 이를 줄이기 위해서 점화식을 이용한 다이나믹 프로그래밍을 사용하면 풀 수 있다. 피보나치 수의 점화식은 fib[0] = 0 fib[1] = 1 fib[n] = fib[n - 1] + fib[n - 2] (n >= 2) 이므로 fib 값을 저장하기 위한 배열을 선언하고, 점화식에 쓰여진 대로 반복문을 돌리면 된다. 값을 1234567로 나눈 값을 저장해야 하므로, (a + b) % n = (a % n + b % n) % n 을 이용해서 문제를 풀었다. #include #include using namespace std; #defin..

이 문제는 투 포인터를 이용해서 푸는 문제이다. 입력이 최대 10,000 인 자연수이기 때문에, 벡터에 숫자들을 넣어서 풀기에도 충분했다. 숫자 배열에는 1부터 n까지만을 넣으면 되는데, n보다 더 큰 숫자들이 들어가면 음수가 있지 않는 이상은 절대 n을 만들 수 없기 때문이다. 투 포인터에서 왼쪽에서 둘 다 출발하는 방식으로 구현했다. 이 때 유의해야 할 점은 acc가 적용되는 범위를 [left, right]로 할 것이냐 [left, right) 로 할 것이냐였는데, 더 직관적인 전자를 선택해서 구현했다. 이 때 right을 먼저 더하고 해당 인덱스에 대한 숫자를 더하는데, right++을 한 상태에서 배열 범위를 벗어나면 오류가 발생하므로 매 분기마다 확인해줘야 한다. #include #include..

이 문제는 구현 문제이다. 십진수를 이진수로 바꾸는 방법만 알면 어렵지 않은 문제이다. 이 문제의 입력에서 최악의 경우는 "11111...." 로 15만 길이일 때인데, 15만을 이진수로 바꾸면 10 0100 1001 1111 0000 이 나오므로 시간 초과의 문제는 전혀 없다. #include #include #include using namespace std; string toBinary(int num) { string result = ""; if (num == 0) { return "0"; } while (num > 0) { result += to_string(num % 2); num /= 2; } reverse(result.begin(), result.end()); return result; } ..

이 문제는 정렬을 이용한 문제이다. 길이가 같은 두 배열에서 하나씩 숫자를 뽑아 두 수를 곱하고, 이를 누적하여 합한 값이 가장 최소가 되게 하는 문제인데, 곱셈의 값은 두 수의 차가 클수록 작아지는 경향이 있다는 사실을 이용하면 쉽게 풀 수 있다. #include #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; sort(A.begin(), A.end()); sort(B.begin(), B.end(), greater()); int length = A.size(); for (int i = 0; i < length; i++) { int a = A[i]; int b = B[i]; answer += ..

이 문제는 구현 문제인 것 같다. 이 문제에서 중요한 것은 어떤 걸 중심으로 잡아서 구현할지이다. 나는 처음에 시간을 중심으로 반복문을 돌려서 문제를 풀었는데, 이렇게 풀면 풀이가 어려워지고 오답이 나올 가능성이 높다. 그래서 검색을 한 결과 버스를 기준으로 반복문을 돌리면 굉장히 풀이가 직관적이고 쉽게 나오게 된다. 처음에 버스가 도착하는 시간을 계산하여 벡터에 넣고, 이에 대해 반복문을 돌리면서 해당 버스에 탈 수 있는 인원을 체크한다. 그 인원이 한 버스 당 최대 인원보다 적으면 버스가 오는 시간 정각에 가는게 가장 늦게 탈 수 있고, 그렇지 않으면 마지막 인원보다 1분 더 일찍 와야 해당 버스를 탈 수 있다. #include #include #include #include #include #inc..

이 문제는 완전 탐색과 투 포인터를 이용한 문제이다. 일단 문자열의 최대 길이가 2500이므로, O(n^2) = 6,250,000 이 되므로 1초 안에는 가능하다. 내가 처음 생각한 알고리즘은 모든 부분 문자열에 대해서 팰린드롬인지 아닌지를 판단하고, 만약 팰린드롬이면 answer를 갱신하는 방식이었다. 거의 다 잘 작동했지만, 문제는 효율성 검사 2 에서 시간 초과가 발생한다는 것이었다. 시간 초과를 줄이기 위해서 cnt에 대한 루프를 주어진 문자열 길이부터 1까지로 줄여나가는 방향으로 하고, 만약 답을 찾으면 그 즉시 리턴하는 것이다. 약간 그리디한 방식인데, 결국 문제에서 찾아야 하는건 가장 긴 팰린드롬이므로 바로 리턴하는 것이 최적해를 낼 수 있다. 여기서 주의할 점은 길이가 1인 문자열은 당연히..

이 문제는 이분 탐색을 이용해서 푸는 문제이다. 사람의 수가 최대 10억이므로 O(n)으로도 불가능하다. 따라서 O(log n) 시간 정도의 알고리즘이 필요하고, 그래서 이분 탐색이 필요하다. 이 문제의 핵심은 무엇을 이분 탐색의 기준으로 삼느냐인데, 나는 정답으로 제출해야하는 모든 사람이 심사를 받는데 걸리는 시간으로 잡았다. 예시로 나왔던 28을 기준으로 보면, 28 / 7 = 4, 28 / 10 = 2 이므로 둘의 합이 6으로 n과 일치하므로 정답이 나오는 것을 알 수 있었다. 만약 27을 기준으로 보면 27 / 7 = 3, 27 / 10 = 2 이므로 아직 6이 되지 않아 숫자를 늘려야함을 알 수 있다. 주의해야 할 점은 만약 합이 n보다 크더라도 일단 정답으로 넣어야 한다는 것이다. 왜냐하면 정..