Little Jay

string을 잘 split하고 reverse 하면 풀 수 있는 문제 #include #include #include #include #include using namespace std; vector split(string input, char delimiter) { vector answer; stringstream ss(input); string temp; while (getline(ss, temp, delimiter)) { answer.push_back(temp); } return answer; } int main() { int n; cin >> n; cin.ignore(); for (int i = 0; i < n; i++) { string s; getline(cin, s); vector v = sp..

dfs로 간단하게 풀 수 있는 문제이다. 1번 컴퓨터를 통해 감염되는 컴퓨터의 개수를 출력하면 되기 때문에, 탐색을 할 노드를 1번 노드로 고정을 해놓고, 1번 노드를 통해 다시 재귀로 탐색을 할 때마다 감염된 컴퓨터의 수를 하나씩 증가시켜주면 된다. #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; int infected = 0; void dfs(int node) { check[node] = true; for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { infe..

간단한 이진탐색 문제 참 메모리라는게 아속하다 문제의 태그에는 set 혹은 map이 달려있어서 처음에는 당연히 set으로 풀었는데 시간초과가 발생해버렸다. 아무래도 set이나 map이나 기능적으로 이진트리의 모습을 만들어야하기 때문에 계속해서 sort해주는 부분에서 메모리를 많이 잡아먹은 것 같다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; for (int i = 0; i > n; vector v; for (int j = 0; j > temp; v..

스택을 활용하는 전형적인 문제 처음에 커서라는 단어를 봤을 때 이걸 환영 링크드 리스트로 구현을 해야되나라고 생각을 했었는데 생각을 해보니까 커서를 기준으로 왼쪽, 오른쪽으로 스택을 나누어 풀면 쉽겠다라고 생각했다. #include #include #include using namespace std; int main() { string s; cin >> s; int n; cin >> n; string temp; stack left; stack right; for (int i = 0; i > temp; if (temp == "L") { if (left.empty()) con..

'{'가 들어오면 push하고 '}'가 들어올 때는 먼저 stack이 비었는지 확인하고 비어있으면 '{'로 바꿔주고 바꾼 횟수를 늘려준다 만약 empty가 아니라면 pop해주면 된다 스택이 비었으면 return change 스택이 차 있으면 return change + st.size() / 2 #include #include using namespace std; int main() { string s; int test = 1; while (true) { cin >> s; int change = 0; if (s[0] == '-') break; stack st; for (int i = 0; i < s.length(); i++) { if (s[i] == '{') st.push(s[i]); else { if (..

브루트포스 문제 for 문을 돌면서 자신보다 큰 값이 있으면 rank를 하나씩 올려주면 된다. #include #include #include using namespace std; pair arr[50]; int main() { int n, rank = 1; cin >> n; for (int i = 0; i > arr[i].first >> arr[i].second; } for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { if (arr[i].first < arr[k].first && arr[i].second < arr[k].second) { rank += 1; } } cout

마지막에 조건으로 이름을 사전순으로 출력해야 되는것을 제대로 못보고 왜 틀렸는지 하루종일 보고 있었다..... 일단 맵이나 해쉬로 풀지 않았다. 이거 같은 경우는 그냥 벡터를 계속 정렬해주면서 binary_search로 빠르게 이름을 찾으면 되는 문제인 것 같다. #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector v(n); v.resize(n); string s; for (int i = 0; i > v[i]; } sort(v.begin(), v.end()); vector ..

hash_table로 풀려고 했지만 채점서버에서 내 코드를 읽지 못해서 vector의 pair기능을 활용해서 다시 풀었다 이것 때문에 많이 문제를 채점해서 좀 그렇다 vector을 두개 사용했는데, 첫 번째 벡터는 바로 번호만 넣으면 출력이 되도록하는 도감으로 만들었고, 두 번째 벡터는 pair을 사용해서 이름과 번호를 같이 넣어서 sort해준 다음 이름순으로 정렬해서 이분탐색하여 찾았다. #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector v1(n + 1); vector v2; v1.push_back(..

쉽게 풀 수 있어 보이는 문제지만 우리는 항상 테스트케이스에 대해서 생각을 해야한다. 무지성으로 임시 변수에 계속 값을 더하면 테스트케이스를 전부 감당할 수 없을 정도의 값이 입력되어 시간초과로 틀릴 수 있는 가능성이 크다 이럴 때는 구간 합 알고리즘을 사용하면 된다. 구간 합 알고리즘은 간단히 설명하자면 어떤 배열이 주어졌을 때, 다른 임시 배열을 만들어서 그 임시 배열에 원래 배열의 부분 합을 더해주면 된다. 흡사 다이나믹 프로그래밍과 비슷하다고 생각하면 된다. #include using namespace std; int arr[100001]{ 0, }; int sarr[100001]{ 0, }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout..

sort를 잘 사용하면 되는 문제 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector v; v.resize(n); int total = 0; for (int i = 0; i > v[i]; } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) { for (int j = 0; j