PS 빼고 다 하는 abra/동아리&과외
-
11월 5주차PS 빼고 다 하는 abra/동아리&과외 2022. 11. 28. 11:10
이번주는 수요일부터는 면접때문에 못하는 김에 수요일부터 2학년 시험볼때까지는 안하려고 한다. 즉, 월요일과 화요일만 할거다. 시간이 얼마 없기 때문에 문제는 두 문제만 준비했다. A. 버블 소트 (1517) 더보기 아마도 널리 알려진 버블 소트의 정렬하는 데 걸리는 스왑 횟수 구하기 결론부터 말하자면 버블 정렬의 스왑 횟수는 인버젼의 개수와 같다. 인버젼이란 0 a[j]인 것이라고 할 수 있다. 단순히 말하면 정렬을 하려할 때 뒤집힌(잘못된) 관계인 것이다. 버블 소트에서 스왑을 의미없게 사용하지는 않는다. 즉, 스왑을 한 번 할 때마다 인버젼의 개수가 1씩 감소하고, 인버젼의 개수가 0이 되었을 때가 정렬이 완료된 상태이므로 인버젼의 개수 = 스왑 횟수가 되는 것이다. 그럼 이제 인버젼의 개수만 세면 ..
-
11월 2주차PS 빼고 다 하는 abra/동아리&과외 2022. 11. 7. 11:45
11월 2주차지만 달력을 보니 슬슬 불안한 감이 든다. 다음주가 수능이라 일주일 내내 학교를 안가서 아마 못할 것 같고, 그 다음주는 3학년 시험이라 3학년은 집에 빨리 간다. 굳 그래서 그 다음주..로 가면 12월 1주차가 되어버리고 이제 슬슬 1,2학년의 시험기간이 다가온다. 시험 2주전부터는 쌤께서 하지 말라고 하실테니 12월 1주차가 끝이다. 근데 또 이때 면접도 있을 것 같다..1차 붙겠지..?응애 시험끝나면 한 1주일? 할 수는 있다. 우리학년 시험일 때 내가 담임쌤과 모의면접이 잡혀있어서 학교에 남긴 할텐데 요 이틀만이라도 시간 잘 맞춰서 해봐야겠다.. 그와중에 또 하루는 1,2학년이 모의고사라 시간이 맞을지 모르겠다. 이번주는 저번주에 하던 스위핑&좌표압축 문제를 다풀고 세그를 끼얹은 스위..
-
11월 1주차PS 빼고 다 하는 abra/동아리&과외 2022. 11. 1. 10:38
10월 31일 (월) 내가 학교를 안가서 안했다. 밤에 후배가 저번주에 못풀고 끝났던걸 푸려고 노력하는 영상을 보내줬다. 세그트리나 이런것도 알길래 스위핑은 알 줄 알았더니 몰라서 의외였다. 그래서 이번주?는 스위핑을 조금 집중적으로 해볼거다. 좌표압축도 모를 것 같아서 같이 연습하려고 한다. 그리고 영상을 보니, 문제를 읽고 시간복잡도나 공간복잡도를 따지지 않고 바로 구현으로 들어가는 것 같다. 쉬운 문제들은 이래도 됐었지만 어려워지면 풀이를 계속 개선시켜서 시간복잡도를 줄이거나 이래야 되므로 고쳐야 할 습관으로 보인다. 사소한 구현미스도 자주 있는 것 같아 어떻게 해결할 수 있을지 고민이다. 그냥 구현 연습시키는게 답인가.. 11월 1일 (화) A. 놀이공원 2594 더보기 N도 작고 입력이 시간이라..
-
10월 5주차PS 빼고 다 하는 abra/동아리&과외 2022. 10. 24. 10:40
시험기간이라 동아리 안했었는데 어느새 10월 막바지다;; 이제 한 한달?정도는 꾸준히 할 수 있을테니 우선 계획을 잡고 시작해야겠다는 생각이 들었다. 지금 가르치고 있는 후배가 2학년이기 때문에 희망하는 대학과 현실 사이에서 최대한 합리적인 선택을 할 수 있도록 얘기해봐야 할 것 같다. 또, 이제 1년밖에 안 남은 것이기 때문에 시간을 효율적으로 쓸 수 있도록 계획을 잡아야 한다... 일단 내년에 특기자전형 있는 대학들.. 1. 한양대 2. 국민대 소프트웨어 특기자: 소프트웨어학부 10명 / 인공지능학부 5명 3. 과기원 KAIST: 30명 UNIST: 15명 GIST: 10명 DGIST: 10명 대회...상을 받아야 특기자를 낼 수 있을텐데 KOI는 조금 어려울 수도 있고,, 국민대 대회는 만점도 장려..
-
9월 5주차PS 빼고 다 하는 abra/동아리&과외 2022. 10. 2. 11:39
동아리는 1학기로 끝나서 동아리라고 할 수는 없고 특기자가 되고 싶어하는 후배들을 데리고 점심시간마다 PS 공부를 하고 있다. 저번주까지는 원서접수로 바빠서 9월 마지막주부터 시작했다. 근데 이제 또 중간고사가 2주밖에 안 남아서 정보쌤(장소 제공자)께서 수요일까지만 하라고 하셨다. 그래서 3일만 공부하고 또 3주(시험까지 합쳐서)정도 쉬어야 되니까 본격적으로는 시험끝나고부터 하려고 한다. 보니까 2학년 후배가 웬만한건 알아서 공부했길래 모르는거 알려주려고 보니 계산기하쪽은 하나도 안 한것 같아서 CCW를 알려줬다. 문제는 총 4문제 넣어놨는데 하나는 그냥 몸풀기?로 DP 회문 문제를 넣어놨고 나머지 세개는 선분교차 2문제, 다각형 넓이 1문제로 구성했다. 다음부터는 빠르게 문제푸는 연습을 위해 골드정도..
-
2022 알고리즘 탐구반 #9PS 빼고 다 하는 abra/동아리&과외 2022. 6. 12. 13:59
계획 저번에 문제로 넣어놨던 '건포도', '동전0'과 관련이 있는 문제들을 추가했다. 그리고 좀 쉬운 DP 문제도 하나 넣어놨다. A. 구간 합 구하기 5 (BOJ 11660) 더보기 건포도 문제를 풀기 위해 필요한 2차원 누적합 연습 B. 건포도 (BOJ 5463) 더보기 무려 5차원 DP. n, m이 최대 50밖에 안돼서 좀 빡세보이지만 O(N^2 * M^2 * (N + M))도 돌아간다. (사실 엄밀히 말하면 N(N+1)/2 * M(M+1)/2 * (N+M)이니까 돌만하다. 그리고 반복문 속에 든게 워낙 간단해서 빠르게 처리된다.) 어떤 직사각형 영역에 대해 가로로 자르거나 세로로 잘라야 한다는 점을 이용해 DP를 생각해보자. 어떤 직사각형을 표현하기 위해서는 가장 왼쪽 위 점과 가장 오른쪽 아래 ..
-
2022 알고리즘 탐구반 #8PS 빼고 다 하는 abra/동아리&과외 2022. 6. 12. 12:25
계획 월요일마다 교내대회때문에 빠지면서 동아리 활동시간을 못 채울 것 같아서 점심시간에 하기로 했다. 사실 동아리는 1학년 한명, 2학년 한명 두고 하는건데 1학년 애가 점심시간에 수행이 있다고 해서 동아리를 제대로 못하겠다는 생각이 들었다. 시간도 짧기도 하고. 그래서 그냥 DP와 그리디 문제 하나씩 넣어놨다. DP는 차원이 높아질 수도 있다는 것을 보여주기 위해 '건포도'로 선택했고, 그리디는 그리디와 DP를 구분할 수 있는지 테스트하기 위해 거스름돈을 주기위한 최소의 동전개수를 구하는 문제이지만 동전이 배수관계로 주어지는 문제를 선택했다. 결과 시간이 30분정도밖에 안돼서 그냥 문제 풀이 생각까지만 하기로 했다. 그리디 문제는 쉽게 방법을 떠올려서 건포도만 잡고 있었는데, DP인듯한 감은 오지만 어..