Minhee Lee

(2020년 9월 5일에 작성한 글입니다.) Dashboard - Codeforces Round #667 (Div. 3) - Codeforces codeforces.com A. 놀랍게도 1분만에 풀었다. 그래서 div3 역시 쉽구나 그런 생각을 했다.​ int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; int a, b; cin >> T; while (T--) { cin >> a >> b; if (a > b) { swap(a, b); } cout T; while (T--) { cin >> A >> B >> X >> Y >> N; a = A; b = B; x = X; y = Y; n = N; if (a - n >= x) { a = a..

class KMP { public: string str, pat; vector table; vector ans; void getTable() { table.resize(pat.length()); int left = 0; for (int i = 1; i 0 && pat[left] != pat[i]) { left = table[left - 1]; } if (pat[left] == pat[i]) { table[i] = left + 1; left++; } } } void getAns() { getTable(); int patIdx = 0; for (int strIdx = 0; strIdx < str.length(); strIdx++) { whil..

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 학회 스터디 강의할 때 다룬 문제 이 문제를 잘 설명하고 싶어서... ppt.. 정말 열심히 만들었다. 이분탐색을 접목해 가능한 높이 중 일부만 확인하는 게 포인트. int arr[1000000]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; int left, right, maxH = 0..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 학회 스터디 강의할 때 다룬 문제 이분 탐색을 구현해서 푸는 코드와 STL 사용하는 코드 모두 보여드렸다. int arr[100000]; bool search(int left, int right, int key); int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n; f..

학회 스터디 강의할 때 다룬 문제 작년에 학교 수업에서 수를 정렬하는 게 과제로 나왔는데 O(nlogn) 정렬을 C언어로 구현해야 해서 오랜만에 Merge Sort를 짰었다. 그리고 또 오랜만에. 강의할 때 이거 잘 보여드리고 싶어서 ppt 되게 열심히 만들었는데 여기 그걸 다 첨부하기엔 양이 많고 또 워낙 유명한거니까 코드만 적어야겠다 int arr[1000000], sorted[1000000]; //전역변수. 벡터를 사용하면 더 간단하게 표현 가능 void Sort(int left, int right);//정렬 함수 void Merge(int left, int right);//Merge Sort 과정에서 분할한 두 배열을 합치는 함수 int main() { ios::sync_with_stdio(0);..

www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 학회 스터디 강의할 때 다룬 문제 우선 N*N 크기의 행렬로 표현되는 종이인지 확인한다. 만약 그렇다면 개수를 업데이트 해주고, 그렇지 않다면 종이를 아홉 등분하여 각각에 대해 또 다시 확인하면 된다. 풀이 자체가 문제를 세 줄로 요약한 거랑 다를 바가 없는데, 결국 이걸 어떻게 구현할 것인지가 관건인 것 같다. #include using namespace std; int arr[7000][7000]..

www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 나는 팰린드롬을 매우 좋아한다 팰린드롬 그 자체도 좋고 관련 문제도 좋고 팰린드롬을 확인하는 코드는 다양한 방법으로 구현할 수 있지만 이번 주 초급 스터디에서 Divide & Conquer를 강의했는데 이 문제를 Divide & Conquer의 관점에서 바라볼 수 있을거 같아서 준비했다. 설명은 그림 위주라 생략하고 코드만 넣어야겠다 bool Palin(int left, int right, string& s); int main() { ios::sync_with_st..

학교 수업 중 과제로 똑같은 문제가 나와서 풀게 됐다. www.slideshare.net/Baekjoon/baekjoon-online-judge-3015?next_slideshow=1 여기서 백준님 풀이를 보면 1과 n 사이가 아닌, a와 b 사이에서의 개수를 구하는걸로 문제를 바꿀 수 있다. 이때 a의 일의 자리수가 0이 될 때까지 a++, b의 일의 자리수가 9가 될 때까지 b-- 해주고 그 과정에서 거치는 수들에 대해 각 숫자의 개수를 업데이트 해준다. 그리고 a, b 사이의 0~9의 개수는 각각 (b/10 - a/10 + 1) * digit 이다. digit은 지금 a, b의 일의 자리수가 원래는 어느 위치였는지를 알려준다. 즉 지금 a, b의 일의 자리수의 값이 원래는 digit 자리수였다는 거..

Dashboard - Codeforces Round #560 (Div. 3) - Codeforces codeforces.com 학회 코포 스터디에서 버추얼을 돌았다 너무 오랜만의 코포/PS라서 어색했다 결과도 별로 좋지 않다 A. 편하게 생각할 수 있도록 string을 뒤집었다. 문자열 변수를 s라고 할 때 ans += s[0] ~ s[x-1] 중 1의 개수 s[x]가 0이면 ans++ ans += s[x+1] ~ s[y-1] 중 1의 개수 한 뒤 ans를 출력하면 된다 int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, y, x; cin >> n >> y >> x; string s; cin >> s; reverse(s.begin(..