Minhee Lee

(2020년 9월 6일에 작성한 글입니다.) Dashboard - Codeforces Round #657 (Div. 2) - Codeforces codeforces.com 학회 코드포스 스터디 Road to Expert에서 풀었다. ​ A. 아니 이 문제가 어떻게 A번일 수 있는가.. 싶을 정도로 A번 같지 않은 문제였다. abacaba가 하나만 존재해야 하기 때문에 물음표를 채우고 나서, 전체 문자열에서 abacaba가 하나밖에 없다는 걸 확인해야 하는데 여기서 나는 abacaba가 시작하는 지점을 indx라고 하면 indx + 4부터 시작하는 abacaba가 있는지만을 확인하면 되는 줄 알았다. 근데 아니었어. abacaba 앞에 abac가 있을수도 있고, 맨 마지막 a에 bacaba가 붙어서 생겼을..

(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..

3/31에 학회 초급 스터디에서 Divide & Conquer, Sorting, Binary Search를 강의했다. https://www.youtube.com/watch?v=V4RsRHcqUzw&feature=youtu.be (YouTube 설명란에서 강의 자료 확인하실 수 있습니다.) 지난 겨울에 기초 스터디에서 C++ 관련 내용을 간단하게 설명했던 것 외에는 강의 경험이 없는데 그때는 대부분 사용법을 알려주고 코드를 작성하는 걸 보여주면서 진행해서 발표 자료가 따로 없었고, 되게 가벼운 분위기었다. 근데 이번에는 본격적으로 알고리즘을 강의하니까 좀 부담됐고 그만큼 정말 잘 하고 싶었는데 강의 전에 준비가 완벽히 되어있었던 건 아니라서 강의를 하면서도, 하고 나서도 정말 아쉬웠다. 근데 학회에서 스터..

https://www.youtube.com/watch?v=pJtEyXLH6Vo 교내 오케스트라 ACES에서 방학마다 진행하는 앙상블 연주(ACES-E)에 퍼스트 바이올린으로 참여했다. ACES-E 공지가 올라왔을 때는 연주를 못 할거 같았는데 왠지 내가 오케스트라에서 연주하는 마지막 기회인 거 같아서 참여했다 여러 선택지가 있었는데 나는 이렇게 클래식이 아닌 곡을 연주하는 걸 좋아해서 이 곡을 골랐다 연습은 코로나 때문에 각자 하고 매주 줌으로 모여서 녹음한 걸 듣고 서로 피드백 했다 처음엔 줌으로 연습하려고도 했는데 이게 생각보다 정말 쉽지 않았다... 각자 메트로놈을 틀어놓고 동시에 연주를 시작하려고 해도 싱크가 잘 안 맞았고 또 연주하는 소리가 너무 커서 줌 소리가 안들렸다 그래서 각자 개인 연습을..