세그먼트 트리에 대해 알아보자: 해결하는 문제와 데이터 구조, 작동 방식, 사용 사례, 자바 코드
개요세그먼트 트리는 효율적인 데이터 관리와 빠른 쿼리를 가능하게 해주는 데이터 구조이다. 특히, 누적 합 계산이나 특정 구간의 최대값, 최소값을 빠르게 처리해야 하는 경우 유용하게 쓰인다. 💡 이 글에서는 세그먼트 트리가 해결하는 문제와 그 이유, 작동 원리와 활용 사례에 대해서 살펴본다.문제 상황 🧐다음과 같은 배열 {1, 3, 5, 7, 9}를 생각해보자. 이에 대해서 다음과 같은 연산을 해야 하는 상황이다.구간 합 구하기예를 들어, 배열의 2번째부터 4번째 숫자의 합을 계산하려면 3 + 5 + 7 = 15이다.값 업데이트배열의 특정 값을 바꿔야 한다면 어떻게 될까요? 예를 들어, 5를 6으로 변경한다면 배열은 {1, 3, 6, 7, 9}로 변한다.이 배열에 대해, 직관적으로 구간 합을 구하거나 ..
2024. 12. 21.
요세푸스 문제의 마지막 남은 사람을 수학적 귀납법으로 도출한 점화식으로 찾아보자
이 글의 작성 배경요세푸스 문제를 다양한 방법으로 풀어보면서 배열, 큐, 링크드 리스트, 세그먼트 트리 등 여러 알고리즘적 접근을 시도해 보았다. 각 방법에서 최적화를 시도했지만, 시간 복잡도는 여전히 \( O(n^2) \) 정도였고, 세그먼트 트리를 사용해도 \( O(n \log n) \) 이 최대였다. 조금 더 최적화할 방법이 뭔가 있을 것 같은데... 고민하다가 문제를 가상의 순환 구조로 해석하면 어떤 규칙이나 패턴이 존재하지 않을까 하는 의문이 생겼다. 그러던 중, 점화식 풀이법을 알게 되며 이 방식에 주목하게 되었다. 점화식을 활용한 풀이법은 흥미로웠지만, 문제는... 어려웠다. 😭 특히, 이 점화식을 어떻게 유도할 수 있는지, 그 논리적 근거와 직관이 어떻게 도출되는지, 그리고 실제로 이 ..
2024. 10. 13.
