본문 바로가기

분류 전체보기

문제 풀이/Codeforces 2020. 8. 6. Codeforces Round #661 (Div. 3) A - Remove Smallest https://codeforces.com/contest/1399/problem/A codeforces.com \(n\)개의 원소를 가진 배열 \(a\)가 주어진다. 한 번의 연산으로, 배열의 서로 다른 두 인덱스 \(i,j\)를 고른다음, \(a_i\)와 \(a_j\)의 차이가 1 이하라면 둘 중 작은 값을 삭제할 수 있다. 두 값이 같다면 둘 중 아무거나 하나를 삭제한다. 이 연산을 반복해서 배열에 원소 1개만 남아있도록 하는 것이 가능한지 알아내야 한다. 배열을 정렬한다음, 인접한 두 원소를 각각 확인하자. 차이가 2 이상인 인접한 원소가 있다면 불가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..
알고리즘/문자열 2020. 8. 5. 해싱 두 문자열이 같은 문자열인지 확인하려고 합니다. 물론 두 문자열의 길이만큼 직접 비교하는 식으로 확인할 수 있지만, 두 문자열의 해시값이 같은지 확인하는 방식으로도 확인할 수 있습니다. 해시 함수에는 다양한 종류가 있지만, 이 문제에 나오는 해시 함수를 이용합니다. https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정� www.acmicpc.net 라빈-카프 알고리즘(Rabin-Karp Algorithm) 어떤 문자열 \(S\)가 주어졌을 때, 이 문자열의 일정한 \(L\)길..
문제 풀이/Codeforces 2020. 8. 3. Codeforces Round #660 (Div. 2) A - Captain Flint and Crew Recruitment Problem - A - Codeforces codeforces.com 정수 \(n\)이 주어진다. nearly prime은 서로 다른 두 소수의 곱으로 나타낼 수 있는 정수를 말한다. \(n\)을 서로 다른 4개의 양의 정수의 합으로 나타내야 하는데, 그 중 적어도 3개가 nearly prime일 수 있는지 여부를 알아내고, 가능하다면 실해를 출력해야 한다. 가장 작은 3개의 nearly prime인 6, 10, 14와 \(n-30\)을 하면 일반적으로 답이다. \(n-30\)이 6, 10, 또는 14와 같거나 양의 정수가 아닐 경우 각각 예외처리를 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..
잡담 2020. 8. 3. UCPC 2020 후기 UCPC 2020이 종료되었다. 원래 20~30위를 목표로 하고있었던 것에 비하면 조금 부족한 성과였지만, 이번 UCPC를 통해 개인적으로, 팀적으로 부족한 부분을 깨닫는 계기가 되었고, 다음 ICPC를 위해 준비해야 되는 것이 무엇인지 알 수 있는 계기가 되었다. 팀원 ANZ1217, ik_e, Envil_Saintan 타임라인 시작하고 우선 문제들을 쭉 훑었다. A번이 가장 쉬운 문제라고 판단했고, 바로 코딩에 들어갔다. 빠르게 정답을 맞을 수 있었다. 0:12 A정답 (ANZ1217) 팀원으로부터 G가 단순구현 같다는 말을 들었고, 바로 G번을 풀기 시작했다. 코드를 냈지만 시간초과를 받았고, 생각했던것 보다 최적화가 많이 필요하다는 것을 알게되었다.. 결국 다른 팀들이 많이 푼 문제를 보자고 얘기..
문제 풀이/Codeforces 2020. 7. 30. Educational Codeforces Round 92 A - LCM Problem Problem - A - Codeforces codeforces.com 정수 \(l, r\)이 주어진다. \(l \le x \lt y \le r\)을 만족하면서, \(l \le LCM(x,y) \le r\)을 만족하는 \(x,y\)가 존재하는지 알아내고, 존재한다면 출력해야 한다. 서로 다른 \(x,y\)에 대해서, \(LCM(x,y)\)가 가장 작아지는 경우는 \(y = 2x\)인 경우이다. \(2l \le r\)이면 \(l, 2l\)을 출력하면 되고, 그렇지 않다면 불가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef unsigned long l..
알고리즘/문자열 2020. 7. 23. 트라이 여러 문자열을 저장하는 자료구조인 트라이(Trie)에 대해 알아봅시다. 문자열 집합 { "ab", "abc", "acd", "bcd", "be"} 가 있다고 할 때, 트라이는 문자열을 다음과 같은 트리로 저장합니다. 문자열을 트라이에 저장하면 루트 노드에서부터 시작해서, 앞에서부터 한 글자씩 해당하는 자식노드를 따라가게 됩니다. 문자열을 모두 저장했다면, 현재 노드에 저장된 문자열이 있다는 표시를 해 주면 됩니다. (그림에서 짙은 노드) 시간복잡도는 문자열 삽입에 \(O(L)\), 탐색에 \(O(L)\)입니다. (\(L\) : 문자열의 길이) 문자열을 set등의 BST로 저장하는 것보다 삽입, 탐색이 훨씬 빠르고, 해싱으로 저장했을 때의 충돌이 없기 때문에 안정적으로 문자열을 찾고 저장할 수 있습니다. ..
문제 풀이/Codeforces 2020. 7. 22. Codeforces Round #658 (Div. 1, Div. 2) A - Common Subsequence Problem - A - Codeforces codeforces.com \(n\)길이의 수열 \(a\)와 \(m\)길이의 수열 \(b\)가 주어진다. 두 수열의 길이가 0보다 큰 공통 부분 수열이 존재하는지 알아내고, 존재한다면 가장 짧은 공통 부분 수열을 출력해야 한다. 두 수열의 공통되는 원소 하나가 존재하는지 찾으면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll..
알고리즘/문자열 2020. 7. 21. KMP 대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 단순하게, 문자열 \(S\)에서 문자열 \(T\)를 찾는 방법에 대해 알아봅시다. 문자열을 검색하는 가장 단순한 방법은, 이중 포문을 돌려 \(O(|S||T|)\)의 시간복잡도로 검색하는 것입니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 하지만 \(S\)와 \(T\)의 길이가 각각 최대 100만..

티스토리툴바