재원블로그 재원블로그

이 문제는 구현 문제이다. 중간에 닉네임이 바뀌어도 결국 최종 결과를 리턴해야하므로, uid만으로 중간 저장을 해놓고, 마지막에 uid에 대한 닉네임을 붙여 리턴하면 된다. 입력이 작기 때문에 주어진 대로 구현만 하면 시간 초과가 나지 않고 정답을 맞출 수 있다. #include #include #include #include #include using namespace std; vector split(string input, char delimit) { stringstream ss(input); string temp; vector result; while (getline(ss, temp, delimit)) { result.push_back(temp); } return result; } struct no..

이 문제는 bfs를 이용해서 풀었다. 일단 가중치가 모두 1이므로 bfs로도 풀 수 있고, 플로이드 워셜을 생각했지만 n이 최대 100,000 이므로 O(n^3) 안에는 풀 수 없어 매 sources 마다 bfs를 돌리는 방식으로 구현했다. #include #include #include using namespace std; vector visited; vector edges[100001]; int bfs(int start, int dest, int n) { visited = vector(n + 1, 0); queue q; visited[start] = 1; q.push(start); while (!q.empty()) { int present = q.front(); q.pop(); if (present ..

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 저번에 풀었던 동전 1 문제와 완전히 동일하다. 동전에 대해서 먼저 루프를 돌리면 순서가 보장되므로 순서가 뒤바뀐 채로 경우의 수가 더해지는 일이 없다. 이 때에도 중요한 것은 dp[0] = 1로 초기화해줘야 한다는 것이다. #include #include using namespace std; long long dp[100001]; int solution(int n, vector money) { int answer = 0; dp[0] = 1; for (int i = 0; i < money.size(); i++) { for (int j = money[i]; j

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 일단 sequence 의 최대 길이가 500,000이므로 O(n) 이하의 알고리즘을 사용해야만 시간 안에 풀 수 있다. 부분 수열마다 펄스 배열을 곱해서 그 최대를 구하라는 문제였지만, 사실 각 숫자마다 1 아니면 -1이 무조건 곱해지게 된다. 따라서 -1을 처음에 곱한 배열과 1을 처음에 곱한 배열 두개에 대해 다이나믹 프로그래밍으로 풀면 정답이 나오게 된다. 나는 1, -1로 시작한 배열 두개에 대한 O(n) 알고리즘을 통해 풀 수 있다는 사실까지는 알아냈지만, 최댓값을 알아내는 알고리즘을 생각해내지 못했다. 처음에는 투 포인터를 생각했지만, 정렬이 되어있지 않은 배열 특성상 알아내기 어려웠다. 그래서 검색을 통해 다이나믹 프로그래밍을 이용하면 된다는..

이 문제는 구현 문제이다. 문자열을 주어진 delimiter로 split 하는 로직은 반드시 기억해놔야 한다. 입력이 작기 때문에 단순 탐색으로 시간 안에 완료할 수 있고, 문제에 주어진 조건대로 구현하면 정답이 나오는 쉬운 문제이다. #include #include #include #include using namespace std; vector split(string input, char delimit) { stringstream ss(input); string temp; vector result; while (getline(ss, temp, delimit)) { result.push_back(temp); } return result; } int carIn[10000]; int carResult[10..

이 문제는 진법 변환을 이용한 구현 문제이다. 일단 입력의 숫자가 크지 않아 완전 탐색으로 가능하다. 그래서 최대 나올 수 있는 인덱스를 계산하면 최대 인원 100명 * 구해야하는 최대 수들 1,000개 = 100만이 나왔고, 정확하지 않기 때문에 150만 정도의 여유를 두고 모두 탐색하였다. p - 1부터 시작해서 m씩 더해가면 해당 순서에 말해야하는 숫자가 numbers에 저장되어있으므로 answer에 추가해주면 시간 안에 풀 수 있다. #include #include #include using namespace std; string convert(int num, int n) { string result = ""; if (n >= 11) { while (num > 0) { int temp = num ..

이 문제는 맵을 이용한 구현 문제이다. 문제에 주어진 설명 그대로 구현하면 바로 시간 초과 없이 정답이 나온다. 왜냐하면 msg에 대해 루프를 돌리는데 사전에 없는 단어가 나올때의 그 문자부터 시작하므로 결국 O(N) 시간이 걸리고, msg의 최대 길이가 1,000 밖에 되지 않기 때문이다. 이 문제를 풀기 위해 다음과 같은 수도 코드를 작성하였다. temp += msg[index] 만약 dic[temp] == 0이라면// 사전에 없음 answer에 dic[prev] 추가 dic[temp] = pushIndex pushIndex++ index-- temp = "" prev = "" 0이 아니라면 // 사전에 있음 prev = temp; continue index++ 처음에는 while문 안에 for문이 ..

이 문제는 규칙성을 찾아 그대로 구현해서 푸는 문제이다. 일단 n의 최대 크기가 1,000만이므로 2차원 배열 자체를 만들 수 없다. 또한 n x n 배열을 1차원 배열로 만들어놓은 배열 또한 만들 수 없다. 그러므로 단순한 탐색 알고리즘으로는 불가능하고, 숫자에서 규칙을 찾아 문제를 풀어야 한다. 일단 right - left 가 최대 99,999 이므로 answer 배열의 최대 길이는 100,000이 될 것이다. 이 문제의 핵심은 left와 right로 주어진 숫자를 2차원 배열의 몇행 몇열인지를 한번에 찾아내는 것이다. 간단한 방법이 있었는데, 만약 숫자가 7이고, 4 x 4 배열이라고 가정하면 7 / 4 = 1, 7 % 4 = 3 으로 0번 인덱스부터 시작해서 1행 3열을 나타내는 수가 7이 되는 ..