Segment Tree란?

세그먼트 트리는 특정 구간의 합, 곱, 최대값, 최소값 등을 효율적으로 구하는 자료구조입니다.
이진 트리의 형태를 띄고 있으며 naive한 방식보다 훨씬 효율적으로 작업을 처리할 수 있습니다.

문제 링크

• https://www.acmicpc.net/problem/4008

문제 링크

• http://icpc.me/15885

문제 링크

• http://icpc.me/15885

문제 링크

• http://icpc.me/15889

문제 링크

• http://icpc.me/15888

문제 링크

• http://icpc.me/15886

이 알고리즘은 출발점부터 도착점까지의 최단 경로(정확히는 최단 경로에 근접한 결과)를 알아내는 알고리즘입니다.

이 글에서는 유클리드 호제법의 증명과 원리를 다룹니다.

제4장. 클래스와 객체의 심화

가. copy and swap idiom

스마트 포인터와 같은 리소스를 관리하는 모든 클래스는 The Big Three라 불리는 것들을 구현해야 한다. 복사 생성자와 소멸자의 목표와 구현은 간단하지만 복사 할당 연산자는 어렵다. 이를 해결하기 위한 해결책이 복사 및 교환 관용구(copy and swap idiom)이며, 할당 연산자가 코드 중복(Code Duplication)을 피하고 강력한 예외 보장(Strong Exception Guarantee)을 제공하는 두 가지 작업을 지원한다.
작동 방식을 알아보자. 개념적으로 복사 생성자의 기능을 이용하여 데이터의 복사본을 만든 뒤, 복사된 데이터를 swap함수로 가져와 이전 데이터를 새 데이터로 바꾼다. 그 후, 임시 복사본이 삭제되고 이전 데이터가 삭제된다. copy and swap idiom을 사용하기 위해서는 복사 생성자, 소멸자, swap함수 3가지가 필요하다. swap함수는 클래스의 두 개체를 서로 바꿔주는 함수이다. swap함수를 직접 구현하지 않고 std::swap함수를 사용하고 싶을 수도 있겠지만, 이것은 불가능하다. std::swap은 구현 내에서 복사 생성자와 복사 할당 연산자를 사용하여 궁극적으로 할당 연산자를 자체적으로 정의하려 한다.