재원블로그 재원블로그

이 문제는 투 포인터를 이용해서 푸는 문제이다. 입력이 최대 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보다 크더라도 일단 정답으로 넣어야 한다는 것이다. 왜냐하면 정..

이 문제는 플로이드 워셜을 사용해서 푸는 문제이다. 정점의 개수가 최대 200개로, O(n^3) = 800만이므로 시간 안에 충분히 계산이 가능하다. INF 값을 적절히 할당하는 것이 중요한데, 정점 개수가 최대 200개이고 간선의 가중치가 최대 10000 이므로 2억이라고 단순 계산했다. 따라서 그것보다 큰 3억으로 INF를 설정했고, 정답을 맞출 수 있었다. 처음에는 그래프와 가중치가 나와서 다익스트라를 생각했지만, 여러 쌍의 경우를 전부 알아야 하므로 플로이드 워셜이 효율적이라 생각해서 문제를 풀었다. #include #include #include using namespace std; #define INF 300000000 int dist[201][201]; void init() { for (in..

이 문제는 그리디를 이용해서 푸는 문제이다. 매 테스트 케이스마다 최대 100000만의 입력이 주어지므로, O(n) 이하의 알고리즘으로 풀어내야 한다. 즉, O(n^2) 알고리즘으로는 절대 풀 수 없다. 그래서 그리디를 떠올렸고, 처음에는 서류 기준으로 정렬해서 최고의 점수를 낸 사람의 두 점수를 기준으로 한번 거르고, 그 다음에는 면접 기준으로 걸러서 정답을 제출했는데 틀렸다. 결국 도저히 안 풀려서 검색을 통해 도움을 받았다. 내가 간과한 것은 최고의 점수를 낸 사람의 기준으로만 탐색을 돌렸다는 것이다. 그럴 필요 없이 한 가지에 대해 정렬하면 일단 그 기준에 대해서는 첫번째 인덱스를 제외하고는 전부 탈락 위기라는 것이다. 이 때 다른 한 가지 기준을 만족하는지 보고, 만족할 경우 그 값으로 최고 점..