재원블로그 재원블로그

이 문제는 맵을 이용해서 풀었다. 일단 입력이 매우 작으므로 단순 구현으로도 시간 초과가 나지 않는다. 시간 단축을 위해 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

이 문제는 구현 문제이다. 중간에 닉네임이 바뀌어도 결국 최종 결과를 리턴해야하므로, 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 ..