전체 글41 [PS를 위한 자료구조 2강] 세그먼트 트리의 구현(재귀) PS를 위한 자료구조 1-2강 # 세그먼트 트리의 구현(재귀) # 에 대해 알아보겠습니다. 우선 세그먼트 트리의 구조에 대해 좀 더 이해해봅시다. 앞선 강의의 그림을 그대로 가져오겠습니다. 위 그림에서 볼 수 있는 특징을 정리하겠습니다. 1. 계층이 존재한다. 2. 한 층 내려갈 때마다 구간이 절반으로 쪼개진다. 3. 이 방식을 계층의 구간이 단 하나의 원소가 될 때 까지 반복된다. 이 특징을 정리해보면 아이디어가 하나 떠오를 겁니다. 바로 '재귀'입니다. 2번 특징은 현재 내가 쪼개고 있는 구간이 무엇인지 상관이 없죠. 그저 쪼개기만 하면 됩니다. 이것을 재귀로 간단하게 나타내면 다음과 같이 쓸 수 있습니다. def 함수(시작 : int, 끝 : int) -> None: if 시작 =.. 2022. 3. 24. [PS를 위한 자료구조 1강] 세그먼트 트리의 원리와 시간복잡도 PS를 위한 컴퓨터 자료구조 강의 1강 # 세그먼트 트리의 원리와 시간복잡도 # 에 대해 알아보겠습니다. 강의에 들어가기에 앞서 모든 의사 코드는 파이썬의 문법을 모방하여 전해드리겠습니다. [구간 합 구하기 4] https://www.acmicpc.net/problem/11659 [구간 합 구하기 5] https://www.acmicpc.net/problem/11660 혹시나 위의 문제를 해결하지 못하신 분들을 위해 해설해드리면 위 문제의 지문을 곧이 곧대로 구현하면 TLE(Time Limit Error)를 받게 됩니다. ex) for (Q번 반복) : i, j = 인풋() print(sum(A[i:j])) 이 경우, 한 번의 쿼리당 최대 100000번의 연산이 발생하므로, 발생할 수 있는 최대 연산의 .. 2022. 3. 24. 패스트캠퍼스 챌린지 최종 후기 패스트캠퍼스 챌린지 데일리 미션을 모두 성공하고 최종 후기를 쓰게 되었다..! 환급 받으면 또 좋은 강의를 수강해야겠다..! 히히 >visit += 1; end = idx; return; } for (auto &p : child) { if (p.first == s[i]) { p.second->visit += 1; p.second->insert(s, i + 1, idx); return; } } child.push_back(make_pair(s[i], new Node())); child.back().second->visit += 1; child.back().second->insert(s, i + 1, idx); } int find(string &s, int i) { if (s.size() == i) retu.. 2021. 12. 8. 패스트캠퍼스 챌린지 30일차 드디어 오늘 마지막...! 한 달 동안 챌린지를 진행해봤다. 솔직히 쉽지 않았다.. ㅎㅎ 이게 단 하루도 빠짐없이 게시글을 올린다는 게 도통 쉽지 않다는 건, 블로그나, 혹은 유튜브를 하시는 모든 분들이 공감하실 것이다. 데이트할때도~ 급한일이 있어도~ 반드시 올려야했기 때문에 솔직히 힘들었다. 하지만 그만큼 했기에 c++강의를 이 만큼 들을 수 있었던 것 같다. 물론 아직.. 다 듣진 못했지만..! 2/3 이상은 수강해서 나름 플레티넘 문제도 풀어보고, FFT도 구현해보고 할 수 있었다. 챌린지가 끝나더라도 아직 STL부분이 남아있고, 그 부분을 상당히 기대하고 있기 때문에, 더 공부를 진행할 예정이다. 그리고 c++이 솔직히 많이 흥미로워서, 앞으로도 주력 언어 중 하나로 사용할 것 같다. 이 강의를.. 2021. 11. 30. 이전 1 2 3 4 5 6 ··· 11 다음
