본문 바로가기

전체 글

[코드포스 Practice15] D. Queue 처음에 문제 이해 못하고 92 뒤에 31 있는거 아녀? 그런데 왜 답이 저렇지?? 생각했는데 임의의 사람 앞에 있는게 92 뒤에 있는 게 31이었다. 더 모르겠다.. 이걸 풀 수 있다고? 아 약간 링크드리스트처럼 앞-뒤 비교하면서 연결하는게 생각나긴 하는데 배고파서 내일 해야겠다. 지금 생각나는건 일단 O(N2^2)번 돌고.. queue 배열을 n개 만듬 그 다음 N^2번 돌면서 queue의 front랑 back이랑 같은지 비교함. 같다면 연결하고 queue없앰 이런식으로 쭉 돌면 마지막에 queue가 2개이거나 1개 남을 것 같은데 1개라면 그대로 출력 2개라면 징검다리로 두 개 있을테니 0으로 시작하는 걸 선두로 각각 하나씩 출력~ 문제는 이럼 제곱만큼 돌고 n은 20만이라 터질 것 같다. 음... .. 더보기
[코드포스 Practice15] C. Odd sum 음.. 풀다가 왜맞틀하다 끝난 문제 지우는 건 가능하되 순서 바꾸는 건 불가하다. 하지만 결국 순서 섞어서 선택해도 똑같은거 아닌가 싶었음. 그래서 정렬해서 투포인터로 앞에 것부터 뺐다. 하지만 틀렸길래.. 예시 하나하나 돌려 봤는데 -999 -998 이런 경우에서 틀렸다. 이거 답은 -999인데 내 코드로는 -1997이 나온다. 생각해보니 값 하나하나 비교하지 않은 것 같아서 값 하나씩 비교하는 걸 추가했다. 그래도 결국 12에서 계속 틀림.. 이제 콘테스트로 끝났으니 12를 확인해봅시다.. 10 4836 -2331 -3456 2312 -1574 3134 -670 -204 512 -5504 내 답은 6015가 나오는데 정답은 8563이 나온다. 오 확인해보니 이런 문제가 있었다. 그 다음 생각한 걸로는.. 더보기
[코드포스 Practice15] B. Chtholly's request 음~ 회문 (뭔지알지) 음 ~ 짝수로? 오케~~ 회문을 다 찾으라고?? mod로 나누라고??? 헉 어렵군 몰겠서 패스 한 문제였다. 이것도 어렵게 생각했던 거였는데 간단히 정리하면 반만 생각하면 된다. 반이 1부터 100000까지 숫자이고 이걸 대칭으로 붙이면 되니 1 ~ 100000 반복문 -> 숫자를 문자열로 바꿈 -> 문자열을 뒤집어서 붙임 -> 다시 숫자로 바꿔서 sum으로 합친다 끝~~ 정말 간단한 문제였다.... k까지 회문을 구해서 더하면 되는 문제... 이걸 내가 어디서 겁먹었나 생각해보면 (ㅋㅋ 지금 생각하면 좀 웃기다) 뭔가 회문 구하는 게 귀납법을 써야할 것 같다! (내가 잘 못쓰는 기법으로 풀 것 같음) 더하는데 mod로 나눈다고? 더할 때 오버플로우 나지 않을까? - 그래서 mod.. 더보기
[코드포스 Practice15] A. Alphabetic Removals 알파벳 개수를 센 다음 a부터 k개수 만큼 뺀다. 그 다음 남은 개수만큼 출력하면 될 꺼라 생각했음.. 하지만 제출하고 생각해보니 이렇게 짜면 앞에서 남은 개수만큼 출력하게 된다. #include #include #include #include #include #include using namespace std; using i64 = long long; int main() { int n, k; scanf("%d %d", &n, &k); string s; cin >> s; vector alpha(26, 0); vector origin(26, 0); for (int i = 0; i < n; i++) { alpha[s[i] - 'a']++; origin[s[i] - 'a']++; } int count = 0;.. 더보기
[코드포스 Practice15] 후기 악ㅋㅋㅋ 1문제 맞췄다 저번 글에 음~ 이제 적응한 듯 ^~^ 했는데 바로 한문제 맞춰버리네 ^////^ 이번 후기를 적으면.. A번은 좀 빨리 풀었는데 문제 이해를 잘못해서 다시 고친다고 시간 걸렸고 B는 이걸 어떻게 접근해야할지 몰라서 넘기고 C는 12번 테케가 틀려서 ㅋㅋ 원인 못 찾고 끝나고 D도 어떻게 풀어야 할지 몰랐다. 시간을 보면 A (30분) -> B (10분) 문제읽고 바로 못풀 것 같아 패스 -> C (30분) 코딩하고 제출했지만 틀림 -> 이 이후로는 D문제 풀려고 깔작거리다가 계속 C만 잡았음 다시 풀어봐야겠다ㅎㅠ PS길은 빡세구나 미래의 나에게 혹시 퍼플까지 갔니 퍼플까지 갔다면 넌 맨날 퍼플 부심 부리고 다니겠지 오늘 1솔브를 했다는 걸 잊지마렴... 더보기
15809 전국시대 1717번 풀면서 음~ 쉽네 하다가 조금 응용 나오니 어려웠다ㅋㅋ 처음 쓰는 자료구조라 낯설음 #include #include #include using namespace std; vector parent; vector num; void init(int n) { parent.resize(n + 1); num.resize(n + 1); for (int i = 1; i num[y]) { num[x] -= num[y]; parent[y] = x; } else if (num[x] < num[y]) { num[y] -= num[x]; parent[x] = y; } else { num[x] = 0; num[y] = 0; } } int main() { int n, m; scanf("%d %d", &n, &m); in.. 더보기
1717 집합의 표현 union find 연습문제로 풀었던 거 #include #include using namespace std; vector parent; void init(int n) { parent.resize(n + 1); for (int i = 0; i 더보기
Union-find (disjoint set) 새로운 걸 배웠다 코드가 간단해서 너무 좋다 더보기