ALiNew ALiNew

ALicademy 👩‍🏫👨‍🏫/알고리즘

• 유클리드 알고리즘 - 두 수의 최대공약수는?🤨

  ALicademy 👩‍🏫👨‍🏫/알고리즘 2021. 7. 4. 23:55

  🚀Intro 치맥의 고장인 맥치마을에서는 매년 치맥축제🍗🍺를 엽니다. 올해는 축제를 위해 치킨 4,500마리🍗와 맥주 7,500잔🍺을 준비했습니다. 이것들을 최대한 많은 사람들에게 남김없이 똑같이 나누어 주려고 할 때, 1️⃣ 최대 몇 명에게 나누어 줄 수 있으며 2️⃣ 한 사람 당 치킨 몇 마리와 맥주 몇 잔을 받을 수 있을까요? 문제를 모두 맞추셨나요? 여러분이 이미 알고 계시듯이 1️⃣번 문제의 답은 4,500과 7,500의 '최대 공약수(Greatest Common Divisor)'인 150명입니다. 또한 2️⃣번 문제의 답은 치킨 4,500마리와 맥주 7,500잔을 최대 공약수인 150으로 나눈 3마리와 5잔입니다. (한 사람당 치킨 세 마리🐓🐓🐓와 맥주 5잔🍺🍺🍺🍺🍺이라니... 정말 좋은 축제..

  Read More

• 🌲 Segment Tree 2 - 더 빠른 update를 위한 Lazy Propagation!

  ALicademy 👩‍🏫👨‍🏫/알고리즘 2020. 9. 1. 19:27

  원본은 링크를 통해 확인하실 수 있습니다. Intro 🚀 이전 글 마지막에 말씀드렸듯이 segment tree에서 특정 구간을 update할 때 leaf node를 일일이 방문해서 update하면 중복해서 방문하는 노드가 생깁니다. 이 때문에 정말 많은 update 연산을 해야 하는 경우 시간이 오래 걸릴 수 있습니다. 그래서 오늘은 더 빠른 udpate를 위한 기법인 Lazy propagation😴 에 대해 배워 보겠습니다! Lazy Propagation 😴 지금부터 여러분이 노드를 직접 update하는 일꾼👷‍♀️👷이라고 생각해봅시다! 여러분은 아래 예제와 같은 segment tree를 돌아다니면서 노드를 udpate합니다. 만약 arr의 0번째부터 2번째 인덱스까지 update하라는 작업이 들어오면..

  Read More

• 🌲 Segment Tree 1 - Segment Tree란?

  ALicademy 👩‍🏫👨‍🏫/알고리즘 2020. 8. 31. 16:33

  원본은 링크를 통해 확인하실 수 있습니다 😃 Intro 🚀 스마트폰을 켜서 SNS를 들어가봅시다. 지난 한 달 동안 여러분이 받은 좋아요👍 의 합을 구하고 싶으면 어떻게 하면 될까요? 아마 여러분이 저와 비슷하다면 가장 먼저 '모든 게시물 중 지난 한 달 동안의 게시물에서 받은 좋아요 수를 일일이 더하면 되지 않을까요?' 라고 말씀하실지도 모릅니다. 이 방법을 사용했을 때 게시물의 수가 $n$개이고 특정 기간 동안 받은 좋아요 수의 합을 묻는 query를 $m$개 처리해야 한다면 시간 복잡도는 $O(mn)$입니다. 이 방법도 나쁘지 않지만 더 효율적인 방법은 없을까요? 그래서 오늘 우리가 배울 것은 바로 구간의 합/ 차/ 최대값/ 최소값 등을 효율적으로 구하기 위해 쓰이는 자료 구조인 🌴Segment T..

  Read More