TIL💡/Algorithms(157)
-
[Codeforces] Number of Groups(UnionFind, Greedy)
https://codeforces.com/contest/1691/problem/E Problem - E - Codeforces codeforces.com 이번 문제 풀이의 가장 큰 풀이는 크게 두 가지로 나눈다. 1. 그룹을 만든다. 2. 그룹의 수를 센다. 처음에는 크게 1번의 경우에는 Greedy 알고리즘, 2번의 경우에는 Union-Find 알고리즘이 쓰이면 좋을 것 같다는 떠오른다. starting and ending points를 set로 저장한다. 예를 들어 (0, 10)와 (11,12) 가 있다면 우리는 0, 10, 11, 12를 색상 상관없이 set에 저장한다. 그리고 이 점들을 오름차순으로 정렬한다. 우리는 색상별로 2개의 set를 가진다. 이 sets에서 starting index에는 ..
2022.06.03 -
[Codeforces] Max GEQ Sum(Stack + Segment Tree)
이번에는 D문제를 풀었다. DP 식으로 풀었는데 역시나 시간 초과가 발생했다. #include #include #include #include using namespace std; int main() { int t; cin >> t; while(t--) { int n; bool answer = true; cin >> n; vector sum(n, vector(n, 0)); vector maximum(n, vector(n, 0)); for(int i = 0;i > sum[i][i]; maximum[i][i] = sum[i][i]; } for(int l = 1;l < n;l++) { if(answer == false) { break; } for(int i = 0;i + l < n..
2022.06.02 -
[Codeforces] Sum of Substrings
대회에서는 C번부터는 문제를 읽지 못해서 그 다음날에도 쭉 풀고 있다. 우선 내가 계획한 풀이 방법은 단순한 DFS이다. 이미 탐색해본 string은 패스하고, string마다 $f$함수를 계산하여 최솟값을 찾아낸다. 그런데 최대 길이가 $10^5$이기 때문에 최대 시간인 1초를 넘어간다. 즉 더 효율적인 풀이 방법이 있다는 것이다. face value Hint 1. What is the contribution of each 1? Hint 2. At what position would 1 contribute less? 해당 string을 분해해보면 크게 sum에 기여하는 방식은 세 가지이다. 1. 맨 앞 자리에서의 수 이 경우에는 sum에 한 번만 기여한다. 즉 하나의 1에 10이 더해지는 셈이다. 2...
2022.06.01 -
[Codeforces] Shoe Shuffling
이제는 백준에서 더 나아가 영어로 알고리즘 풀이를 해보고 싶어서 망설임없이 코드 포스에 입문했다. 마침 코드 포스에 가입한 다음날에 열리는 대회에 참가해보았다. 결과는 확실히 망했다... 흑흑 그래도 첫 도전에 의미를 담으며...ㅎㅎ 대회 중간에 통과하지 못했던 Problem B를 대회 이후에 풀어보았다. 알고보니 어이 없는 잘못을 저질러서 실패했던 것이었다. https://codeforces.com/contest/1691/problem/B Problem - B - Codeforces codeforces.com 핵심 💚 학생들의 신발 사이즈 $s_{i}$가 비내림차순(non-decreasing)으로 정렬되어있다. 💚 학생들은 본인의 신발을 안 신고, 본인의 사이즈와 동일하거나 큰(greater than ..
2022.06.01 -
[백준] 11066: 파일 합치기(assert 사용으로 디버깅 🐛)
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 이 문제를 처음에 보면 앞뒤로 연속되게 합쳐질 수 있어서 일반적인 다이나믹 프로그래밍이 떠오르지 않을 수 있다. 그래도 중복 문제가 발생하기 때문에 다이나믹 프로그래밍으로 풀고 싶다는 욕구가 든다. 그렇다면 중복 문제는 어떻게 해결해야하는가? 어떠한 구간의 합이 궁금하다면 해당 구간을 임의로 두 부분으로 나누어서 왼쪽 부분과 오른쪽 부분을 합친 비용의 최솟값이 될 것이다. 두 부분을 나누..
2022.05.31 -
[백준] 1152: 단어의 개수
https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 문자열 조작은 항상 어려워서 브론즈 문제임에도 제대로 시도해보았다. cin.getline vs. 헤더의 getline 📌 cin.getline(char 배열, 최대 입력 사이즈) cin의 멤버 함수이다. char 배열에 스트림 사이즈만큼 마지막 글자에 NULL 문자가 포함된 한 줄의 문자 배열을 입력받는다. 📌 헤더의 getline(입력 스트림, string 객체, 구분자) 지정한 구분자(d..
2022.05.30