반응형 알고리즘 썸네일형 리스트형 2021 신촌 연합 알고리즘 여름 캠프 강사 후기 & PS 휴식기 약 1달 반의 강의 일정이 모두 끝났다. 길면서도 짧았던 기간이었는데, 꽤나 의미 있던 활동이어서 아직 캠프 자체가 끝나진 않았지만 까먹기 전에 후기를 남긴다. 좋은 강의는 못되더라도 뭔가 하나라도 수강생들이 얻어가는 게 있었으면 좋겠다. 지극히 개인적인 의견이나 생각이 있을 수도 있으니 불편하신 분들에게 미리 사과드립니다.... [목차] 1. 신촌 연합 알고리즘 캠프란? 2. 강사진 신청 3. 캠프 시작 전 4. 강의 목표 5. 강의 진행 6. 후기 & 아쉬운 점 7. PS 휴식기 1. 신촌 연합 알고리즘 캠프란? 운영진이 아니라 캠프에 대해 잘 이해하고 있는지는 잘 모르지만, 그래도 캠프에 대해서 조금 설명하고자 한다. 정확한(?) 명칭은 신촌지역 대학교 프로그래밍 동아리 연합(ICPC Sinchon.. 병렬 이분 탐색(Parallel Binary Search) 주어진 문제의 답이 단조성을 갖는 경우에는 Parametric Search를 이용하여 해당 문제를 해결할 수 있다. Parametric Search에 대해서 이미 잘 알고 있다면 스크롤을 아래로 내리자. 예를 들어 "N명의 사람이 나이순으로 정렬되어 있을 때, 20세 이상이면서 나이가 가장 작은 사람의 나이를 구하시오"와 같은 문제가 있다고 하자. 앞에서부터 다 확인한다면 O(N)의 시간이 걸리게 되지만, Parametric Search를 이용하면 O(logN)만에 해결할 수 있다. 먼저, 답이 될 수 있는 범위의 중간지점을 확인한다. 19는 20세 미만이므로 답이 될 수 없다. 그러면 현재 위치보다 왼쪽에 있는 나이들은 당연히 19 이하이기 때문에 답이 될 수 없다. 따라서 왼쪽은 더 이상 볼 필요가 .. Atcoder Beginner Contest 206 (ABC 206) 풀이 A. Maxi-Buying 단순 계산 문제이다. N을 입력받고, 1.08*N을 정수단위로 올림 했을 때 206과 대소 비교하는 문제이다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); double n; cin >> n; n *= 1.08; int ans = (int)n; if (ans == 206) cout = n) { cout > n; map mp; for (int i = 0; i > a; mp[a]++; } ll ans = 0; for (auto [a, b] : mp) { ans += 1LL * b * (.. [BOJ 1396] 크루스칼의 공 [문제] https://www.acmicpc.net/problem/1396 1396번: 크루스칼의 공 첫째 줄에는 그래프의 정점의 개수 n과 간선의 개수 m이 주어진다. 그리고 두 번째 줄에서 m+1번째 줄까지는 a b c의 형태로 a와 b를 잇는 간선의 고유값이 c라는 의미이다. m+2번째 줄에는 알고 싶은 www.acmicpc.net [난이도] - Platinum I (21.06.10 기준) [필요 개념] - Union-Find - Parallel Binary Search (병렬 이분 탐색) or LCA [풀이] 이 문제는 크게 두 풀이로 나뉜다. 첫 번째로는 PBS(병렬 이분 탐색)이다. 흔히 PBS의 대표 예제 문제로 알려져 있는데, 조만간 PBS에 대한 글을 따로 작성할 예정이라 자세한 풀이는 .. Platinum DP 문제들 풀이 (1) 요즘 DP에 약한 기분이 많이 들어서, 플래티넘 DP 문제 중 특별한 기법이나 최적화를 이용하지 않는 문제들을 푼 사람 수로 정렬해서 안 푼 문제들을 선별하여 조금씩 풀고 있다. 푼 사람 수로 정렬한 문제라 이미 남들에겐 웰논일지도 모른다. 많이 풀린 문제들답게 플래티넘임에도 불구하고 꽤 잘 풀리는 것도 있는 반면 해설 없이는 못 풀었을 문제들도 많았다. 아마 DP라는 걸 모르고 풀었다면 체감 난이도가 훨씬 높았을 것 같다. [BOJ 1126] 같은 탑 (Platinum III) N = 50개의 블록을 이용하여 높이가 같은 두 개의 탑을 만든다. 모든 블록을 사용할 필요는 없으며, 각 블록의 높이는 최대 50만이고, 모든 블록의 높이의 합이 50만 이하이다. 이때, 만들 수 있는 탑의 높이의 최댓값을 구.. [Python] 7. 모듈(Module) [목차] 1. 모듈이란? 2. 모듈 만들기 & 불러오기 3. if __name__ == "__main__" 1. 모듈(Module)이란? 모듈(Module)이란, 함수나 변수 또는 클래스를 모아놓은 파이썬 파일이다. 이미 파이썬에서 아주 많은 표준 라이브러리 모듈을 제공하고 있고, 사용자가 직접 모듈을 만들어서 이용할 수도 있다. 여러 파일에서 동일한 클래스나 함수 등이 이용되는 경우에, 공통되는 부분을 따로 빼내어 하나의 파일로 만들어두면 매번 새로 정의할 필요 없이 가져오기만 하면 되므로 코드도 짧아지고 훨씬 편리하다. 2. 모듈 만들기 & 불러오기 이제 모듈을 어떻게 만들고 불러오는지를 알아보자. # file name : calculate.py def add(a, b): return a+b def .. Google Kickstart Round A 2021 풀이 Rank = 861 (KR 37) 1. K-Goodness String (12 pts) 길이가 N인 문자열 S가 주어지고, 각 글자를 원하는 만큼 변경할 수 있다. 1≤i≤N/2 인 i에 대해서 S[i] != S[N-i+1]인 i의 개수가 K가 되기 위한 최소 변경 횟수를 구하는 문제이다. 단순 구현 문제이다. S[i]나 S[N-i+1] 둘 중 하나를 바꾼다면 상태를 바꿀 수 있으니 처음 문자열에서 S[i] != S[N-i+1]인 i의 개수를 구한 다음 K와의 차이만큼 문자를 바꿔주면 된다. (멍청하게도 S[i] == S[N-i+1]이면 점수를 얻는다고 생각해서 1WA를 받았다. 왜 하필 예제 답이 같아서...) [소스 코드] #include using namespace std; int main(void.. [Codeforces] Round #709 (div. 2) A ~ D 풀이 2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844) 테크노컵은 뭔가 항상 어려운 느낌이다... 생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. A. Prison Break (*800) 모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다. 답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자. 벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상.. 이전 1 2 3 4 ··· 7 다음
