Welcome to booknu's Blog!

PS & Algorithm 공부, 테크 리뷰

토비의 스프링 vol.1 1장 정리 (오브젝트와 의존관계)

2020-03-03

booknu

Spring_토비

Spring 토비의스프링

스프링이 추구하는 것
DAO 리팩토링
원칙과 패턴
제어의 역전 (IoC)
스프링의 IoC
- 애플리케이션 컨텍스트 예제
- 애플리케이션 컨텍스트의 동작 방식
싱글턴 레지스트리와 오브젝트 스코프
의존관계 주입 (DI)
XML을 이용한 설정

이 문서는 토비의 스프링 3.1 세트 책에 소개되는 개념들을 정리한 문서입니다.

스프링이 추구하는 것

단순함 : 자바의 잃어버린 객체지향 언어적 장점을 다시 살릴 수 있도록 도와주는 도구 (POJO 프로그래밍)
유연성 : 뛰어난 확장성으로 다른 많은 프레임워크 등과 쉽게 결합하여 사용할 수 있도록 할 것

“항상 프레임워크 기반의 접근 방법을 사용하라” 라는 것은 OOP의 장점을 최대한 살린 것이 스프링이고, 이것을 기반으로한 접근 방법을 사용하면 스프링이 추구하던 아키텍처, 설계의 근간이 흔들릴 일 없이 확장되어 결국은 확장된 코드마저도 스프링과 같이 확장성이 뛰어나고 유지보수가 쉬운 코드가 되기 때문

DAO 리팩토링

DAO

Data Access Object : DB를 사용해 데이터를 조회, 조작하는 기능을 전달하는 객체

JavaBean

원래는 비주얼 툴에서 조작 가능한 컴포넌트, 그러나 현재에는 다음 2가지 관례를 따라 만들어진 객체를 지칭

Default Constructor을 갖고 있음 (툴/프레임워크에서 Reflection을 통해 오브젝트를 생성하기 때문)

Property: Setter, Getter을 이용해 수정/조회할 수 있음

Naive한 구현의 경우

DAO에서 다음과 같은 일들을 한 메소드 안에서 전부 시키면 어떤 문제점이 발생할까?

DB Connection을 가져오고
SQL을 담을 Statement를 만들고 정보를 바인딩시켜 실행하고
작업이 끝나면 사용한 리소스를 해제한다.

만약 DB 계정의 id/pw를 바꾸는 등 사소한 수정 사항이 생기는 경우에도 전체 코드의 여러 곳을 산발적으로 수정해야 하는 문제가 생긴다. 이를 해결하기 위해 관심사의 분리를 해야 한다.

관심사의 분리 (Sepration of Concerns)

관심이 같은 것끼리는 하나의 객체 혹은 친한 객체로 모이게 하고, 관심이 다른 것끼리는 가능한 떨어뜨려 영향을 끼치지 않게 만드는 것.

이 경우 Connection을 얻어오는 부분을 다른 메소드로 빼는 방식으로 리팩토링을 하면 위에서 말한 문제는 해결된다.

메소드 추출 (Extract Method)

공통 기능을 그것을 담당하는 메소드로 중복된 코드를 뽑아내는 것

DB Connection의 분리

위와 같이 메소드 추출을 하면, 어느 정도의 문제는 해결된다. 하지만 사용하는 DB 자체를 바꿀 경우에는 어떻게 할 것인가?

물론 getConnection() 메소드를 조금만 수정하면 되는 일이지만, UserDao 자체는 클래스 바이너리 파일로 사용하고 싶으면 소스 자체를 고칠 수는 없는 일이다.

이 경우 getConnection()을 abstract method로 수정하고, 그 구현부를 상속을 받아 구현하는 식으로 리팩토링 할 수 있다.

템플릿 메소드 패턴 (Template Method Pattern)

슈퍼클래스에서 기능의 일부를 abstract method 혹은 overriding 가능한 protected method로 만든 뒤 서브클래스에서 필요에 따라 메소드를 구현하도록 하는 패턴

abstract method : 서브 클래스에서 반드시 구현해야 하는 기능

hook method : 서브 클래스에서 overriding을 통해 확장을 할 수 있는 기능

이 때 Dao의 getConnection() 메소드는 어떤 Connection 클래스를 생성할지 결정하는 방법이라고도 볼 수 있고, 이를 팩토리 메소드 패턴이라고 한다.

팩토리 메소드 패턴 (Factory Method Pattern)

템플릿 메소드 패턴과 원리는 같으나, 구체적인 오브젝트 생성 방법에 대해 결정하게 하는 것. 주로 Interface 타입 오브젝트를 반환하므로 서브 클래스는 다양한 방법으로 오브젝트를 생성하는 메소드를 작성 할 수 있다. 이 때 오브젝트 생성 방법과 클래스를 결정할 수 있도록 미리 정의해둔 메소드를 팩토리 메소드라고 한다.

자바에서는 어떤 오브젝트를 생성하는 메소드를 일반적으로 팩토리 메소드라고 하는데, 이것을 팩토리 메소드 패턴의 팩토리 메소드와 헷갈리면 안 된다.

데이터 액세스 로직을 어떻게 만들 것인가
DB 연결을 어떻게 할 것인가

두 가지 관심을 상하위 클래스로 분리시키는데는 성공을 했지만, 여전히 문제가 남아있다.

클래스의 분리

Dao 객체 자체에 팩토리 메소드를 만들어버리면 다른 목적으로 Dao를 상속시키지 못한다는 단점이 있다. 또한 상속을 통한 상하위 클래스 관계는 긴밀하게 결합된다 것도 문제이다. 분명 Connection만을 가지고 오고 싶었을 뿐인데, 불필요한 결합이 생겨버리는 것이다. 마지막으로 이 Dao 객체 뿐 아니라 다른 Dao 객체도 getConnection()이 필요한데, 이 때문에 또 중복되는 코드가 생긴다.

이를 해결하는 간단한 방법이 있다. ConnectionMaker와 같이 아예 DB Connection을 얻어오는 전용 객체를 따로 만드는 것이다. 이렇게 하면 다중 상속 문제와 코드 재사용 문제가 동시에 해결된다.

단, ConnectionMaker를 구현할 때 getConnection() 메소드에 직접 구현을 때려박는다면 Dao 객체에 직접 구현했을 때와 마찬가지의 문제점이 생긴다. 따라서 당연히 ConnectionMaker는 인터페이스로 선언돼야하고, 직접적인 구현부는 그것의 서브클래스에 맡겨야한다. 즉, Dao에는 인터페이스로서 ConnectionMaker가 추상화되어 변수로 선언되어 있어 그 구현부가 바뀌어도 신경 쓸 일이 없어진다.

관계설정 책임의 분리

하지만, 선언은 인터페이스인 ConnectionMaker로 하더라도, Dao 안에서 인터페이스를 구현한 객체를 직접 생성한다면 여전히 문제는 존재한다! 즉, Dao 안에 new MyConnectionMaker() 라는 문장이 있는 한 여전히 구현부에 따라 Dao도 바뀌어야 할 것이다.

여태까지 Connection에 대한 관심을 다른 클래스로 모두 뺀 것처럼 보이지만, 여전히 Dao 안에는 Connection에 대한 관심이 존재하기 때문에 이런 현상이 발생한다. new MyConnectionMaker() 자체는 짧기만, 그 자체에 MyConnectionMaker을 사용하여 연결한다는 관심이 함축되어 있는 것이다. 이것은 즉, Dao의 ConnectionMaker로는 MyConnectionMaker을 쓴다는 관계 설정에 대한 관심이다.

이런 관계 설정은 실제로 Dao를 사용하는 Client Object에서 하도록 분리하는 것이 가장 좋다. connectionMaker = new MyConnectionMaker(); 이라는 코드는 MyConnectionMaker 객체의 레퍼런스를 connectionMaker이라는 변수에 넣어 사용하게 함으로써 이 두 개의 객체가 “사용”이라는 관계를 맺도록 하는 것이다!

요약하자면, 객체의 Dynamic Type을 Dao를 실제로 사용하는 코드(클라이언트)에서 정하여 객체를 생성하고, 그것을 Dao에게 파라미터 등의 수단으로 전달하여 관계를 연결해주면 된다. (다형성 = Polymorphism)

클래스 사이에 만들어지는 관계 : 클래스 코드에 다른 클래스 이름이 나타나기 때문에 맺어지는 관계

객체 사이에 만들어지는 관계 : Runtime에서 객체의 Static Type과 Dynamic Type 사이에 맺어지는 관계

이로써 Dao 객체는 본래의 관심사인 데이터 액세스를 위한 SQL 생성, 실행에 집중할 수 있게 됐고 Connection을 설정하는 부분은 ConnectionMaker에, ConnectionMaker와 관계 설정을 하는 부분은 클라이언트에 떠넘길 수 있게 됐다.

요약

요약하자면 다음과 같은 과정을 통해 리팩토링을 하였다.

Naive하게 모든 구현을 Dao 메소드에 때려박는다.
공통적으로 등장하는 코드를 메소드 추출을 통해 리팩토링한다.
Dao 자체에 팩토리 메소드 패턴을 적용하여 추상화를 통한 확장성을 높인다.
Dao의 다른 목적을 위한 상속 문제 해결을 위해 팩토리 메소드를 다른 새로운 클래스에게 구현하도록 한다.
Dao의 Static Type에 Dynamic Type을 관계시키는 책임을 클라이언트에게 전가한다.

원칙과 패턴

개방 폐쇄 원칙

OCP(Open-Closed Principle)

클래스나 모듈은 확장에는 열려 있어야 하고, 변경에는 닫혀 있어야 한다.

그 예로, 인터페이스를 사용하면 확장을 위해서는 개방되어 있지만, 인터페이스를 이용하는 클래스는 확장으로 인한 변화는 불필요하게 일어나지 않도록 닫혀있다.

객체지향 설계 원칙 (SOLID)

SRP(Single Responsibility Principle) : 단일 책임 원칙
OCP(Open Closed Principle) : 개방 폐쇄 원칙
LSP(Liskov Substitution Principle) : 리스코프 치환 원칙
ISP(Interface Segregation Principle) : 인터페이스 분리 원칙
DIP(Dependency Inversion Principle) : 의존관계 역전 원칙

높은 응집도와 낮은 결합도

높은 응집도

변화가 일어날 때 해당 모듈에서 변하는 부분이 크다는 것. 이렇게 되면 바뀌지 않는 부분들에 대해 신경 쓸 필요가 없다.

즉, 하나의 모듈이 하나의 관심사에만 집중되어 있다는 것

낮은 결합도

관심사가 다른 모듈끼리는 느슨한 연결을 유지하는 것. 모듈끼리의 독립성을 높인다는 것이고, 하나의 모듈에 대해 신경 쓸 때는 다른 모듈에 대해 최소한의 정보만 알아도 된다는 것이다.

이를 통해 변화에 대응하기 쉬워지고, 구성이 깔끔해진다.

즉, 결합도란 하나의 모듈의 변화에 대해 관계를 맺는 다른 모듈에게 변화를 요구하는 정도

전략 패턴

자신의 기능(맥락 = Context)에서 필요에 따라 변경이 필요한 알고리즘을 인터페이스화 하여 통째로 외부로 분리시키고, 이를 구현한 구체적인 알고리즘 클래스를 필요에 따라 바꿔서 사용할 수 있게 하는 패턴.

알고리즘

독립적인 책임으로 분리가 가능한 기능

그 예로, Dao에서 getConnection() 알고리즘을 통째로 분리시켜 ConnectionMaker라는 인터페이스로 정의하고, 이를 구현한 클래스에 따라 전략을 바꿔가면서 사용할 수 있게 분리하였다.

제어의 역전 (IoC)

Ioc(Inversion of Control)

지금까지 리팩토리한 Dao도 괜찮지만, 아직 개선 사항이 남았다. Dao를 사용하는 클라이언트에서는 본래 관심사가 아닌 일을 두 가지나 하고 있다.

ConnectionMaker 객체의 생성
생성된 객체와 Dao의 객체를 연결 (관계 주입)

따라서 이 두 가지 기능 역시 따로 분리되어야 한다.

팩토리

위의 두 기능을 DaoFactory 라는 객체를 새로 만들어서 맡기도록 하자. userDao() 라는 함수에서 이런 기능을 맡게 될 것이며, 결과적으로 생성된 Dao를 반환하게 될 것이다.

팩토리

객체를 생성하여 반환하는 클래스. 오브젝트를 생성하는 쪽과 생성된 오브젝트를 사용하는 쪽의 역할과 책임을 분리하기 위해서 도입 된 개념.

클라이언트는 팩토리 객체를 통해 Dao를 생성할 것이며, 두 가지 기능이 분리되었다.

이로써 Dao와 ConnectionMaker은 각각 핵심적인 데이터로직, 기술 로직을 담당하고 있고, DaoFactory는 객체들을 구성하고 관계를 정의하는 책임을 담당하게 되었다.

즉, 전자는 실질적인 로직을 담당하는 컴포넌트, 후자는 컴포넌트의 구조와 관계를 정의한 설계도 같은 역할이라고 볼 수 있다.

오브젝트 팩토리의 활용

DaoFactory 에서 여러 Dao를 생성한다면 어떻게 될까?

각 팩토리 메소드마다 ConnectionMaker을 생성하는 코드가 중복되서 나타난다. 코드 중복이 발생하면 이 코드를 수정할 때 의미없이 반복적으로 같은 코드를 수정해야 하기 때문에 이 부분 역시 DaoFactory 안의 새로운 메소드로 빼내는 것이 좋다.

제어관계 역전

일반적인 프로그램에서는?

main() 에서 시작해 여기에서 사용할 객체를 결정하여 생성하고, 해당 객체를 사용하는 것이 재귀적으로 반복된다.

제어의 역전이란?

객체가 사용할 객체를 스스로 선택하거나 생성하지 않는다.
객체 자신도 어떻게 만들어지고 어디서 사용되는지 알 수 없다.

이것이 가능한 이유는, 모든 제어의 권한을 자신이 아닌 다른 대상에게 위임하기 때문이다.

예시

서블릿의 경우 서블릿의 코드를 직접 실행할 수 있는 수단은 없지만, 그 제어 권한을 가진 컨테이너가 서블릿 객체를 만들고 사용하게 된다.
getConnection() 의 경우도 제어권을 상위 템플릿 메소드에 넘기고 그 자신은 필요할 때 호출되어 사용되는 구조를 가진다.
프레임워크도 작성한 애플리케이션 코드가 상위 개념인 프레임워크에 의해 사용되는 구조이다.

라이브러리 vs 프레임워크

라이브러리 : 애플리케이션 코드가 직접 흐름을 제어하고, 라이브러리는 단순히 사용될 뿐이다.

프레임워크 : 애플리케이션 코드는 프레임워크에 의해 사용되기만 할 뿐, 흐름의 제어는 프레임워크가 한다.

이런 관점에서, DaoFactory 역시 하나의 IoC 프레임워크라고 볼 수도 있다.

스프링의 IoC

빈 (Bean)

Spring Container가 제어권을 가지고 직접 생성하고 관계를 부여하는 대상이 되는 객체

SpringBean은 JavaBean과 비슷하게 객체 단위의 애플리케이션 컴포넌트이다. 동시에 Spring Container가 생성/관계설정/사용 등을 제어해주는 IoC 개념이 적용된 객체이기도 하다.

빈 팩토리 (Bean Factory)

Bean의 생성/관계설정 등의 제어를 담당하는 IoC 객체

빈을 등록/생성/조회/반환/관리 하는 기능을 담당하며, 보통은 빈 팩토리를 확장한 애플리케이션 컨텍스트를 사용한다.

애플리케이션 컨텍스트 (Application Context)

Bean Factory를 상속하여 확장한 것으로 IoC 방식을 따라 만들어진 일종의 Bean Factory. Bean Factory와 동일함.

단, 코드 내에 제어에 관한 정보가 들어있는 것이 아니라 별도의 설정 정보를 담은 무언가를 가져와 활용하는 IoC 엔진.

즉, 스프링이 제공하는 각종 부가 서비스를 추가로 제공하는 것이다.

빈 팩토리 vs 애플리케이션 컨텍스트

기본적으로 둘은 동일한 개념을 가리키는 말이지만, 중점을 두는 부분이 다르다.

빈 팩토리 : 빈을 제어하는 IoC 기본 기능에 초점이 맞춰진 것.

애플리케이션 컨텍스트 : 애플리케이션 전반에 걸쳐 모든 구성요소의 제어를 담당하는 IoC 엔진이라는 의미가 부각된 것.

설정 정보 (Configuration, Metadata)

애플리케이션 컨텍스트가 IoC를 적용하기 위해 사용하는 메타정보로, 컨테이너의 어떤 기능을 세팅하거나 조정하는 경우에도 사용하지만 보통 IoC 컨테이너에 의해 관리되는 객체를 생성하고 구성할 때 사용된다.

컨테이너 / IoC 컨테이너

애플리케이션 컨텍스트나 빈 팩토리를 이르는 말이다.

IoC 컨테이너의 경우 주로 빈 팩토리 관점에서 이야기할 때 쓰이며, 그냥 컨테이너/스프링 컨테이너라고 할 때는 애플리케이션 컨텍스트를 추상적으로 가리킬 때 사용한다.

애플리케이션 컨텍스트가 이름이 길기 때문에 스프링 컨테이너라고 부르기도 하며, 스프링이라고 부르기도 한다. 이 때는 “스프링에 빈을 등록하고” 라는 식으로 말하기도 한다.

스프링 프레임워크

IoC 컨테이너, 애플리케이션 컨텍스트를 포함해서 스프링이 제공하는 기능을 통틀어 말할 때 사용한다.

애플리케이션 컨텍스트 예제

설정 정보 생성

@Configuration : 이 클래스는 애플리케이션 컨텍스트가 사용할 설정 정보라는 것을 알림
@Bean : 오브젝트 생성을 담당하는 IoC용 메소드라는 표시

@Configuration
public class DaoFactory {
	@Bean
	public UserDao userDao() {
		UserDao dao = new UserDao(connectionMaker());
		return dao;
	}

	@Bean
	public ConnectionMaker connectionMaker() {
		ConnectionMaker connectionMaker = new DConnectionMaker();
		return connectionMaker;
	}
}

어노테이션은 자바 코드인 것 같지만, 사실은 XML 같은 스프링 전용 설정 정보이다.

애플리케이션 컨텍스트 생성

public class UserDaoTest {
	public static void main(String[] args) throws ClassNotFoundException, SQLException {
		AnnotationConfigApplicationContext context 
      = new AnnotationConfigApplicationContext(DaoFactory.class);
		UserDao dao = context.getBean("userDao", UserDao.class);
    // ....
  }
}

AnnotationConfigApplicationContext는 ApplicationContext를 구현한 클래스 중 하나로, @Configuration이 붙은 자바 코드를 설정 정보로 사용하기 위해 쓰인다.

getBean()은 ApplicationContext가 관리하는 오브젝트를 요청하는 메소드이다.

getBean()의 반환 타입은 Object이므로 형변환이 필요하지만, Java5 이상부터는 제네릭 메소드 방식을 통해 리턴 타입을 제공 받는 식으로 더 깔끔하게 구현할 수 있다.

애플리케이션 컨텍스트의 동작 방식

왜 오브젝트 팩토리를 사용하지 않는가?

직접 구현한 오브젝트 팩토리는 제한적으로 객체 생성/관계설정을 하지만, 애플리케이션 컨텍스트는 애플리케이션에서 IoC를 적용해 관리할 모든 객체에 대한 생성/관계 설정을 한다는 차이가 있다.

또한 애플리케이션 컨텍스트는 객체를 직접 생성하고 할당하는 코드가 없는 대신에 그것에 대한 정보를 별도의 설정 정보를 통해 얻는다. (떄로는 외부의 오브젝트 팩토리에 그 작업을 위임하고 결과를 사용하기도 한다.)

애플리케이션 컨텍스트 = 오브젝트 팩토리 = IoC 컨테이너 = 스프링 컨테이너 = 빈 팩토리

정확히는 ApplicationContext가 BeanFactory 인터페이스를 상속한다.

동작 방식

@Configuration 등이 붙은 클래스를 설정 정보로 등록해두고
@Bean이 붙은 메소드들의 이름을 가져와 이름과 메소드를 매핑해둔 Bean List를 생성해둔다.
getBean()이 호출되면 Bean List에서 해당되는 이름의 메소드를 찾아 호출하고 그 결과를 클라이언트에게 반환한다.

장점

클라이언트가 필요할 때마다 팩토리 클래스를 구현할 필요가 없다.

직접 코드를 작성하는 대신, 어노테이션, XML 등의 간단한 방법으로 IoC 설정을 할 수 있다.
종합 IoC 서비스를 제공한다.

생성/관계 설정 뿐 아니라 생성 방식/시점/전략 등을 설정할 수 있고 자동생성/후처리 등 다양한 기능을 제공한다. 또한 빈이 사용할 수 있는 기반 기술 서비스나 외부 시스템과의 연동 등을 컨테이너 차원에서 지원해주기도 한다.
빈을 검색하는 다양한 방법을 제공한다.

메소드 이름 뿐만이 아니라 타입, 특수 어노테이션 등으로 설정된 빈도 찾을 수 있다.

싱글턴 레지스트리와 오브젝트 스코프

직접 구현한 DaoFactory에서 객체를 여러번 생성하는 것과 ApplicationContext를 통해서 객체를 여러번 생성하는 것에는 무슨 차이가 있을까?

당연하게도 DaoFactory를 사용하는 경우는 그 안쪽의 구현으로 인해 새로운 객체가 계속 생성되어 나온다. 하지만, ApplicationContext를 사용하는 경우는 놀랍게도 같은 객체가 반환된다!

동일성 (Identity) : 객체의 주소가 같은지, 즉 물리적으로 같은 객체인지?

동등성 (Equality) : 객체의 주소는 다르지만 동등의 판단 기준에 따라 값이 같은지?

싱글턴

위와 같은 현상이 발생하는 이유는, ApplicationContext가 싱글턴을 저장하고 관리하는 싱글턴 레지스트리이기 때문이다.

별다른 설정을 하지 않으면, 내부에서 생성하는 빈 객체를 모두 싱글턴으로 만든다.

디자인 패턴에서의 싱글턴과 개념은 비슷하지만, 구현 방식은 완전히 다르다.

이와 같이 처리되는 이유는 스프링이 서버 환경을 고려하여 설계되었기 때문이다. 서버에서는 TPS라는 용어가 있을 정도로 초당 수많은 요청이 들어오는데, 이 요청을 처리할 때마다 객체를 생성하는 것은 굉장한 낭비일 수 있다. 그래서 엔터프라이즈 분야에서는 서비스 오브젝트라는 개념을 일찍부터 사용해왔고, 자바에서는 서블릿이 기본이고, 이 역시 싱글턴으로 존재한다.

싱글턴 패턴 (Singleton Pattern)

프로그램에서 객체가 단 하나만 존재하도록 강제하는 패턴. 주로 여러 애플리케이션에서 공유하는 경우에 사용된다.

단, 싱글턴 패턴은 여러 문제점을 발생시킬 수 있기 때문에 굉장히 조심해서 사용해야 한다.

싱글턴 레지스트리

일반적인 싱글턴 패턴을 Dao 객체에 적용했을 때 다음과 같은 문제점이 발생한다.

private 생성자 때문에 DaoFactory에서 Dao를 생성하여 반환할 수 없다.
private 생성자 때문에 상속을 시킬 수 없다.
생성자를 통해 객체에 동적으로 정보를 주입할 수 없기 때문에 테스트하기 힘들다.
전역 변수와 같은 문제점을 발생시킬 수 있다. 특히 OOP에서는 더욱 문제가 된다.

서버 환경에서 싱글턴을 쓰고는 싶은데 싱글턴 패턴과 private 생성자를 이용한 비정상적인 방법은 쓰기 힘들기 때문에 스프링에서는 싱글턴 레지스트리를 지원한다.

싱글턴 레지스트리 (Singleton Registry)

스프링이 직접 싱글턴 객체를 만들고 관리하는 기능을 제공하는 것.

이것은 평범한 public 생성자를 가진 자바 클래스를 싱글턴으로 활용할 수 있게 만들어준다. 그렇게 할 수 있는 이유가 클래스의 제어권을 IoC 방식의 컨테이너에게 넘기면 해당 컨테이너가 객체 생성에 대한 모든 권한을 가지고 있기 때문에 객체가 싱글턴으로 존재할 수 있게 관리를 할 수 있기 때문이다.

즉, IoC 컨테이너의 제어 역할을 통해서 빈을 싱글톤으로 만드는 것이다.

싱글턴과 오브젝트 상태

서버 환경에서는 여러 요청이 멀티스레딩으로 처리되므로 싱글턴 객체의 상태를 다룰 때 주의해야한다. 서비스 형태의 오브젝트로 사용되는 경우 내부에 변하는 상태를 갖지 않는 Stateless로 만들어져야 한다. 이 때 요청에 따라 달라지는 값에 대한 정보는 파라미터, 지역 변수, 반환 값 등을 이용하면 된다.

스프링 빈의 스코프

Default Scope : 싱글턴

강제로 제거하지 않으면 스프링 컨테이너가 존재하는 동안 계속 유지됨
Prototype Scope : 빈을 요청할 때마다 새로 생성
Request Scope : HTTP 요청이 생길 때마다 생성
Session Scope : 웹의 세션과 스코프가 유사
…..

의존관계 주입 (DI)

IoC라는 용어는 매우 느슨하게 정의되어 폭 넓게 사용된다. 따라서 스프링이 제공하는 IoC 방식의 중점을 짚어주기 위해서 의존관계 주입이라는 용어가 등장했다.

의존관계 주입 (Dependency Injection = DI)

오브젝트 레퍼런스를 외부로부터 주입 받고, 이를 통해 여타 오브젝트와 동적으로 의존관계가 만들어지는 것.

런타임 의존관계 설정

의존관계란 방향성이 존재하고, $A\rightarrow B$라는 의존관계가 있다면 $B$가 변하면 $A$도 영향을 받는다는 것을 뜻한다.

Dao와 ConnectionMaker 또한 이러한 관계이다.

이 때 ConnectionMaker가 인터페이스가 아닌 일반 클래스라면 강하게 의존하고 있다는 뜻이 되고, 코드가 조금이라도 변한다면 Dao에서도 신경을 써야할 것이다.

그러나 아래 그림과 같이 인터페이스에 대해서만 의존관계를 만들어두면 인터페이스 구현 클래스와는 관계가 느슨해지며 변화를 덜 받는 상태가 된다.

하지만 이와 같이 UML에서 말하는 의존관계는 설계 모델의 관점에서 보는 것이고, 이를 통해 드러나지 않는 의존관계가 존재한다.

런타임 시에 만들어지는 의존관계이다.

예를 들어 Dao에서는 코드 작성 시점에 어떤 ConnectionMaker와 관계를 맺을 지 알 수 없다. 그것은 클라이언트 측의 선택에 따라서 달라지기 때문이다.

의존관계 주입이란 이렇게 구체적인 의존 오브젝트와 그것을 사용할 주체(일반적으로 클라이언트) 오브젝트를 런타임 시에 연결해주는 작업을 말한다.

의존 오브젝트 (Dependent Object)

런타임 시에 의존관계를 맺는 대상

즉, 의존관계 주입은 다음 세 가지 조건을 충족하는 작업이다.

Static한 클래스 모델, 코드에는 드러나지 않다가 런타임에 의존관계가 드러나야한다. 이를 위해 인터페이스에만 의존해야 한다.
런타임 시점의 의존관계는 컨테이너나 팩토리 같은 제 3자가 결정한다.
의존관계는 사용할 오브젝트에 대한 레퍼런스를 외부에서 주입해줌으로써 만들어진다.

2번의 좋은 예시로 Dao에서 직접 MyConnectionMaker를 생성하던 것을 제 3자인 클라이언트나 팩토리, 애플리케이션 컨텍스트에게 맡긴 것을 생각하면 된다. 이러한 제 3자들은 DI 컨테이너라고 부를 수 있다.

DI 컨테이너

두 객체 사이의 런타임 의존관계를 설정해주는 의존 관계 주입 작업을 주도하는 존재.

오브젝트 생성/초기화/제공 등의 작업을 수행함.

이처럼 DI는 자신이 사용할 객체에 대한 선택, 생성 제어권을 외부로 넘기고, 수동적으로 주입 받은 객체만을 사용한다는 점에서 IoC의 개념과 잘 들어맞는다.

의존관계 검색과 주입

의존관계 검색 (Dependency Lookup = DL)

객체 스스로 검색하여 의존관계를 맺는 것.

의존관계를 맺을 대상 객체를 결정하고 생성하는 작업은 외부 컨테이너에게 IoC로 맡기지만, 이를 가져올 때는 메소드나 생성자를 통한 주입 대신 스스로 컨테이너에게 요청하는 방법을 사용한다.

예를 들어 다음과 같은 코드는 의존관계 검색에 해당된다. 적어도 의존관계를 가져올 때는 스스로 요청하는 것이다.

public UserDao() {
  DaoFactory df = new DaoFactory();
	this.connectionMaker = df.connectionMaker();
}

DaoFactory 대신 ApplicationContext가 쓰였다면 미리 정해놓은 이름을 전달해서 해당되는 오브젝트를 찾게 될 것이다.

public UserDao() {
  AnnotationConfigApplicationContext context =
    new AnnotationConfigApplicationContext(DaoFactory.class);
  this.connectionMaker = context.getBean("connectionMaker", ConnectionMaker.class);
}

보통의 경우 일반적인 의존관계 주입을 사용하는 것이 단순하고 깔끔하다. 의존관계 검색의 경우 객체 코드 안에 팩토리 클래스나 Spring API가 나타나는데, 이는 해야할 일에 집중해야하는 객체에게 있어 바람직하지 않은 구현 방식이다.

그러나 언젠가는 한 번 의존관계 검색 방식이 등장해야하기는 한다. 스태틱 메소드인 main()에서는 DI를 통해 객체를 주입 받을 방법이 없기 때문이다.

서버에는 main()메소드는 없지만, 이와 비슷하게 요청을 받을 때마다 비슷한 역할을 하는 서블릿에서 한 번쯤 DL 해야하나, 서블릿은 스프링이 미리 만들어 제공하기 때문에 직접 구현할 필요는 없다.

또 한 가지 특징으로는 DL에서는 검색을 하는 주체 객체는 꼭 스프링 빈일 필요가 없다는 것이다. DI를 받기 위해 스프링 빈이 되어야 했지만, 이제는 아무 관계도 주입받지 않고 스스로 관계를 맺기 때문이다.

반면 DI에서는 주입 받는 객체가 반드시 스프링 빈 객체여야한다.

의존관계 주입의 응용

기능 구현의 교환

일반적으로 개발을 할 때 개발용 DB와 운영용 DB가 분리되어 사용된다. 그런데 DI를 하지 않는다면 배포할 때 DB를 사용하는 코드 모든 부분을 고려해야하는 의미없는 수고가 필요하고, 배포 후 개발용 코드로 돌릴 때도 마찬가지이다.

하지만 DI를 이용한다면 ConnectionMaker을 상속한 클래스만 하나 따로 만들어주고 DI를 하는 부분에서 사용하는 Dynamic Type만 살짝 바꿔주면 해결이 된다.

부가기능 추가

DB 연결 횟수를 카운팅하는 기능을 추가하고 싶을 때는 어떻게 하면 될까? 모든 DAO의 getConnection() 메소드에 카운팅 기능을 추가하려면 엄청난 노력이 필요할 것이다.

그러나 DI를 이용하면 아주 간단해진다. Dao와 ConnectionMaker 사이에 CountingConnectionMaker을 하나 더 추가하면 된다. 물론 이 때, CountingConnectionMaker을 getConnection 부분을 직접 구현하게 하면 안 된다. 이 또한 ConnectionMaker을 주입 받도록 만들어 CountingConnectionMaker가 본업인 연결 횟수를 카운팅하는데만 집중할 수 있도록 만들어줘야 한다.

public class CountingConnectionMaker implements ConnectionMaker {
  int cnt = 0;
  private ConnectionMaker realCM;
  public CountingConnectionMaker(ConnectionMaker realCM) {
    this.realCM = realCM; // CM을 DI받게 만들어 카운팅에만 집중한다!
  }
  public Connection getConnection() throws ClassNotFoundException, SQLException {
    ++this.cnt; // 여기에만 집중
    return realCM.getConnection(); // 실제 연결을 만드는건 주입 받은 객체가
  }
}

결과적으로 다음과 같은 의존관계가 생성된다.

Dao를 생성하는 부분도 DI를 주입하는 부분만 바꾸면 된다.

@Configuration
public class CountingDaoFactory {
  @Bean
  public UserDao userDao() {
    return new UserDao(connectionMaker()); // DAO 설정 부분은 바뀌지 않았다
  }
  @Bean
  public ConnectionMaker connectionMaker() {
    return new CountingConnectionMaker(realConnectionMaker()); // DI 받는 부분만 바뀌었다
  }
  @Bean
  public ConnectionMaker realConnectionMaker() {
    return new MyConnectionMaker();
  }
}

의존관계 주입을 하는 방법들

생성자
Setter 메소드 (수정자)
일반 메소드

Setter 메소드의 경우 이름이 set으로 시작해야하고 한 개의 파라미터 밖에 가지지 못한다는 제약이 있다.

반면 일반 메소드를 사용하면 여러개의 파라미터를 한꺼번에 받을 수 있고 Overloading을 통해 다양하게 파라미터를 받아올 수 있다는 장점이 있다.

XML을 이용한 설정

XML을 통해서도 DI를 구성할 수 있다. 어노테이션을 사용하는 경우 DI 정보를 수정하는 경우 재빌드를 해야하지만, XML을 이용하면 그럴 필요가 없다.

XML 설정

<beans>
	<bean id="myConnectionMaker" class="<pakage>.MyConnectionMaker" />
  <bean id="yourConnectionMaker" class="<pakage>.YourConnectionMaker" />
  <bean id="productionConnectionMaker" class="<pakage>.ProductionConnectionMaker" />
  <bean id="userDao" class="<pakage>.UserDao">
  	<property name="connectionMaker" ref="myConnectionMaker" />
  </bean>
</beans>

<beans> : @Configuration 역할 / XML의 루트 엘리먼트 / 안에 여러 개의 <bean>을 정의할 수 있다.
<bean> : @Bean 역할

	Java Code	XML
빈 설정파일	`@Configuration`	`<beans>`
빈 이름	`@Bean methodName()`	`<bean id="methodName"`
빈 클래스	`return new BeanClass()`	`class="package.BeanClass">`
Setter DI	`dao.setValue(value)`	`<property name="value" ref="value" />`

DTD, 스키마

XML 문서는 미리 정해진 구조에 따라 작성됐는지 검사할 수 있는데, 이러한 정의 방법에는 DTD와 스키마가 있다.

DTD (Document Type Definition)
<!DOCTYPE beans PUBLIC "-//SPRING//DTD BEAN 2.0//EN"
	"http://www.springframework.org/dtd/spring-beans-2.0.dtd">
하지만 스프링에서 특별한 목적을 위해 별도의 태그를 사용할 수 있는 방법을 제공하는데, 이런 대그들은 별개의 스키마 파일에 정의되어 있고 독립적인 네임스페이스를 사용해야 한다. 따라서 이런 태그들을 사용하려면 DTD 대신 네임스페이스 기능이 있는 스키마를 사용해야 하고, 이런 이유로 대부분의 경우 스키마를 쓰는 것이 바람직하다.

스키마 (Schema)
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
                           http://www.springframework.org/schema/beans/spring-beans-3.0.xsd"></beans>
<beans>태그를 기본 네임스페이스로 하는 스키마 선언이다.

XML을 이용한 애플리케이션 컨텍스트

DaoFactory 대신 XML 설정정보를 활용하려면 GenericXmlApplicationContext를 사용한다.

applicationContext.xml

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
                           http://www.springframework.org/schema/beans/spring-beans-3.0.xsd">
  <bean id="connectionMaker" class="package.MyConnectionMaker" />
  <bean id="userDao" class="springbook.user.dao.UserDao">
  	<property name="connectionMaker" ref="connectionMaker" />
  </bean>
</beans>

GenericXmlApplicationContext

ApplicationContext context = new GenericXmlApplicationContext("applicationContext.xml");

ClassPathXmlApplicationContext

ApplicationContext context = new ClassPathXmlApplicationContext("daoContext.xml", UserDao.class)

경로 정보 기준을 UserDao로 설정할 수 있어 좀 더 편하게 xml 파일 위치를 적을 수 있다.

DataSource 인터페이스로 변환

Java에는 우리가 직접 구현한 ConnectionMaker과 같이 DB 커넥션을 가져오는 기능을 추상화 한 DataSource 인터페이스가 있다.

그러나 DataSource에는 getConnection() 외에도 많은 메소드가 있기 때문에 직접 구현하기에는 부담이 있는데, 다행히도 이미 구현되어 있는 클래스가 있으니 그걸 쓰면 된다.

@Setter
public class Dao {
  private DataSource dataSource;
  public void add(User user) throws SQLException {
    Connection con = dataSource.getConnection();
    // ...
  }
}

DataSource를 DI 받았을 때는 위와 같이 ConnectionMaker을 사용하듯이 쓰면 된다.

@Bean
public DataSource dataSource() {
  SimpleDriverDataSource dataSource = new SimpleDriverDataSource();
  dataSource.setDriverClass(com.mysql.cj.jdbc.Driver.class);
  dataSource.setUrl("jdbc:mysql://localhost/spring?serverTimezone=UTC");
  dataSource.setUsername("user name");
  dataSource.setPassword("password");
  return dataSource;
}
@Bean
public Dao dao() {
  Dao dao = new Dao();
  dao.setDataSource(dataSource());
  return dao
}

DaoFactory의 경우 테스트 환경에서 간단하게 사용할 수 있는 SimpleDriverDataSource를 사용해서 구현하였다.

<bean id="dataSource" class="org.springframework.jdbc.datasource.SimpleDriverDataSource" />

새로 생긴 dataSource() 빈도 XML에 추가해줘야한다.

프로퍼티 값 주입

위와 같이 했을 때 XML에서 dataSource()에서 사용한 SimpleDriverDataSource의 Setter로 넣어준 접속 정보는 들어있지 않다는 문제점이 생긴다.

UserDao와 같이 다른 빈에 의존하는 경우 <property> 태그와 ref 속성으로 의존할 빈 이름을 넣어주면 되지만, SimpleDriverDataSource의 경우 Setter가 일반 클래스나 스트링 값이 파라미터로 들어오는데 어떻게 해야할까?

다행히도 Setter에는 빈 뿐만 아니라 객체, 스트링 등의 값도 넣어줄 수 있다. 즉, 다른 빈 객체의 레퍼런스가 아니어도 Setter로 데이터를 줄 수 있다는 소리이다. 하지만 이 때는 DI처럼 Dynamic Type을 자유자재로 바꾸려는 목적이 아닌 단순한 값을 주입하려는 목적이다. 이것도 일종의 DI라고 볼 수 있는데, Dynamic하게 정보가 바뀌지 않지만, 객체의 특성을 외부에서 변경할 수 있기 때문이다.

<property name="driverClass" value="com.mysql.cj.jdbc.Driver" />
<property name="url" value="jdbc:mysql://localhost/spring?serverTimezone=UTC" />
<property name="username" value="user name" />
<property name="password" value="password" />

이와 같이 하드코딩 되어있던 설정 정보를 XML을 통해 주입해줄 수 있게 됐다.

즉, DataFactory를 사용하는 것이 아닌 XML을 사용해서 DI를 할 수 있는 것이다.

이 때 스프링이 프로퍼티 값을 Setter 메소드의 파라미터 타입으로 자동 형변환 해주기 때문에 "com.mysql.cj.jdbc.Driver"와 같이 객체를 String으로 줘도 되는 것이다.

실제 내부에서는 다음과 같이 코드가 변환된다.
Class driverClass = Class.forName("com.mysql.cj.jdbc.Driver");
dataSource.setDriverClass(driverClass);

이 떄 형변환은 Class, URL, File, Charset, List, Map, Set, Properties 등등으로도 가능하다.

Read All

ICPC 본선 대비 팀 노트

2019-11-07

booknu

알고리즘

PS 대회

Network Flow
Graph
- 2-SAT + SCC
- Cut-Vertex
String
Math
Segment Tree
Miscellaneous

ICPC 2019 Seoul Regional을 준비하며 만든 팀 노트입니다.

koosaga님을 비롯한 DeobureoMinkyuParty 팀 노트를 참고하며 만들었습니다.

PDF 버전 + TEX

Network Flow

Dinic’s Algorithm

/*
	1. build level graph with bfs ( O(E) )
	2. flow blocking flow in level graph ( O(VE) )
	In each step, level grows at least by 1, and eventually grows upto O(V)
	So total time complexity is O(V^2E)
*/
struct dinic { // O(V^2 E)
	struct edg { int v, c, r; };
	int n;
	vi dis, itr;
	vector<vector<edg>> g;
	dinic(int n) : n(n), g(n, vector<edg>()), dis(n), itr(n) {  }
	void addedge(int u, int v, int c) {
		g[u].pb({ v, c, sz(g[v]) });
		g[v].pb({ u, 0, sz(g[u])-1 });
	}
	bool bfs(int s, int t) { // build level graph
		dis.assign(n, 0), itr.assign(n, 0);
		queue<int> q;
		q.push(s);
		dis[s] = 1;
		while(q.size()) {
			int u = q.front(); q.pop();
			for(auto& [v, c, r] : g[u]) {
				if(c > 0 && !dis[v]) {
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
		return dis[t] > 0;
	}
	int dfs(int u, int t, int f) { // get blocking flow
		if(u == t) return f;
		for( ; itr[u] < g[u].size(); itr[u]++) {
			auto& [v, c, r] = g[u][itr[u]];
			if(c > 0 && dis[v] == dis[u] + 1) {
				int w = dfs(v, t, min(f, c));
				if(w) {
					g[u][itr[u]].c -= w;
					g[v][r].c += w;
					return w;
				}
			}
		}
		return 0;
	}
	i64 nflow(int s, int t) { // network flow
		i64 ret = 0;
		while(bfs(s, t)) {
			int r;
			while(r = dfs(s, t, 2e9)) ret += r, debug("-----");
		}
		return ret;
	}
};

Hofcroft-Karp Bipartite Matching

/*
    - alternating path: path consists of (x, y, x, y, x) for X = { x | x is matched edge}, Y = { y | y is not mathed edge } 
    - augmenting path: path consists of (y, x, y, x, y)
    - if augmenting path exists, we can match one more edge with fliping matched state (x, y, x, y, x)

    For maximaum matching A, B
    1. lv[0] = { v | v in A and v is not matched }
    2. starting from lv[0] vertices, get alternating path with bfs
    3. starting from lv[0] vertices, get augmenting path with dfs

    * min cover: selecting minimum vertices to cover all edges
    * max independent set: selecting maximum vertices not connected with edge
    * V - min cover = max independent set
*/
struct hofcroft {
	int n, m;
	vi dis, l, r, vis, chk;
	vvi g;
	hofcroft(int n, int m) : n(n), m(m), g(n, vi()) {  }
	void addedge(int u, int v) { g[u].pb(v); }
	bool bfs() { // build alternating path starts from lv[0] nodes
		queue<int> q;
		bool ok = 0;
		dis.assign(n, 0);
		FOR(u, 0, n) {
			if(l[u] == -1 && !dis[u]) {
				q.push(u);
				dis[u] = 1;
			}
		}
		while(q.size()) {
			int u = q.front(); q.pop();
			for(int v : g[u]) {
				if(r[v] == -1) ok = 1; // v is not matched
				else if(!dis[r[v]]) { // if v is matched, u>v>r[v] can be path
					dis[r[v]] = dis[u] + 1;
					q.push(r[v]);
				}
			}
		}
		return ok;
	}
	bool dfs(int u) { // find augmenting path and flip it!
		if(vis[u]) return 0; // augmenting path start/end with non-matched vertices
		vis[u] = 1;
		for(int v : g[u]) {
			if(r[v] == -1 || (dis[r[v]] == dis[u] + 1 && dfs(r[v]))) {
				l[u] = v; r[v] = u;
				return 1;
			}
		}
		return 0;
	}
	int match() { // bipartite match
		l.assign(n, -1);
		r.assign(m, -1);
		int ret = 0;
		while(bfs()) {
			vis.assign(n, 0);
			FOR(u, 0, n) if(l[u] == -1 && dfs(u)) ++ret;
		}
		return ret;
	}
	void rdfs(int u) { // dfs matched
		if(chk[u]) return;
		chk[u] = 1;
		for(int v : g[u]) {
			chk[v + n] = 1;
			rdfs(r[v]);
		}
	}
	vi getcover() { // get min cover vertices
		match();
		chk.assign(n+m, 0);
		FOR(u, 0, n) if(l[u] == -1) rdfs(u);
		vi ret;
		FOR(u, 0, n) if(!chk[u]) ret.pb(u);
		FOR(u, n, n+m) if(chk[u]) ret.pb(u);
		return ret;
	}
};

MCMF

const int WINF = 0x3fffffff, FINF = 0x3fffffff; // weight/flow inf
struct mcmf {
	struct edg { int v, c, r, w; };
	int n;
	vi dis, par, peg;
	vector<bool> inq;
	vector<vector<edg> > g;
	mcmf(int n) : n(n), g(n, vector<edg>()), par(n), peg(n) {  }
	void addedge(int u, int v, int c, int w) {
		g[u].pb({ v, c, sz(g[v]), w });
		g[v].pb({ u, 0, sz(g[u])-1, -w });
	}
	bool spfa(int s, int t) {
		dis.assign(n, WINF);
		inq.assign(n, 0);
		queue<int> q;
		dis[s] = 0;
		inq[s] = 1;
		q.push(s);
		bool ok = 0;
		while(q.size()) {
			int u = q.front(); q.pop();
			if(u == t) ok = 1;
			inq[u] = 0;
			FOR(eidx, 0, g[u].size()) {
				auto [v, c, r, w] = g[u][eidx];
				if(c > 0 && dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					par[v] = u;
					peg[v] = eidx;
					if(!inq[v]) {
						inq[v] = 1;
						q.push(v);
					}
				}
			}
		}
		return ok;
	}
	ii flow(int s, int t) { // return (max_flow, min_cost)
		int cost = 0, flow = 0;
		while(spfa(s, t)) {
			int cur = FINF;
			for(int u = t; u != s; u = par[u]) cur = min(cur, g[par[u]][peg[u]].c);
			for(int u = t; u != s; u = par[u]) {
				int r = g[par[u]][peg[u]].r;
				g[par[u]][peg[u]].c -= cur;
				g[u][r].c += cur;
			}
			flow += cur;
			cost += dis[t] * cur;
		}
		return { flow, cost };
	}
};

Ford-Fulkerson Algorithm

// Caution: All vertices' idx > 0 (par[S] = 0)
const int MAXND = 500, S = 1, T = 2, INF = 0x3fffffff;
struct nflow {
	struct edge {
		edge* rev; 
		int v, c, f; // need initialized
		edge(int v, int c) : v(v), c(c), f(0) { }
		int res() { return c-f; }
		int flow(int x) { f += x, rev->f -= x; }
	};
	vector<edge*> g[MAXND];
	int par[MAXND];
	edge* pedg[MAXND];
	nflow() {
		FOR(i, 0, MAXN) g[i] = vector<edge*>();
	}
	void addedge(int u, int v, int c) { 
		edge *uv = new edge(v, c), *vu = new edge(u, 0);
		uv->rev = vu, vu->rev = uv;
		g[u].pb(uv), g[v].pb(vu);
	}
	i64 maxflow() {
		i64 ret = 0;
		while(true) {
			memset(par, 0, sizeof(par));
			queue<int> q;
			q.push(S);
			par[S] = S;
			while(q.size()) {
				int u = q.front(); q.pop();
				for(auto e : g[u]) {
					if(e->res() && !par[e->v]) {
						q.push(e->v);
						par[e->v] = u;
						pedg[e->v] = e;
						if(e->v == T) break;
					}
				}
				if(par[T]) break;
			}
			if(!par[T]) break;
			int flow = INF;
			for(int u = T; u != S; u = par[u]) flow = min(flow, pedg[u]->res());
			for(int u = T; u != S; u = par[u]) pedg[u]->flow(flow);
			ret += flow;
		}
		return ret;
	}
};

Naive Bipartite Match

const int MAXN = 5e2+10;
int vis[MAXN], ato[MAXN], bto[MAXN];
bool dfs(int u) {
	if(vis[u]) return 0;
	vis[u] = 1;
	for(int v : g[u]) {
		if(bto[v] == -1 || dfs(bto[v])) {
			ato[u] = v;
			bto[v] = u;
			return 1;
		}
	}
	return 0;
}
int bimatch() {
	memset(ato, -1, sizeof(ato)), memset(bto, -1, sizeof(bto));
	int ret = 0;
	FOR(u, 0, n) {
		memset(vis, 0, sizeof(vis));
		if(dfs(u)) ++ret;
	}
	return ret;
}

Graph

2-SAT + SCC

/*
	2-SAT: (A || B) && (C || D) && (E || F) ...
	1. X || Y = !X -> Y, !Y -> X  (Proposition)
		False: T -> F, True: Others
	2. !X, X in same SCC: no solution
	3. For every SCC, each node in same SCC must have same flag (if both T, F exists in same SCC, T->F exists)
	4. Assign False to (Don't have in edge & Unassigned node) and erase node
		- sort nodes topologically, iterate nodes with assigning False to var if var is unassigned
			- !X node: X = True, X node: X = False
*/
struct sat2 {
	struct tarjan {
		int n, ncnt, scnt;
		vi scc, dis;
		vvi g;
		stack<int> sta;
		tarjan(int n) : n(n), g(n, vi()) { } // n: number of variables (NOT NODES!)
		void addedge(int u, int v) { g[u].pb(v); } // directed graph
		int f(int u) {
			int ret = dis[u] = ncnt++;
			sta.push(u);
			for(int v : g[u]) {
				if(dis[v] == -1) ret = min(ret, f(v));
				else if(scc[v] == -1) ret = min(ret, dis[v]);
			}
			if(ret == dis[u]) {
				while(1) {
					int t = sta.top(); sta.pop();
					scc[t] = scnt;
					if(t == u) break;
				}
				++scnt;
			}
			return ret;
		}
		vi& get_scc() {
			ncnt = scnt = 0;
			scc = dis = vi(n, -1);
			sta = stack<int>();
			FOR(i, 0, n) if(dis[i] == -1) f(i);
			dis.clear();
			return scc;
		}
	};
	int n;
	vi res;
	tarjan tj;
	sat2(int n) : n(n), tj(2*n) { }
	int nd(int u, int neg) { return u + neg*n; } // var u's node
	int neg(int u) { return (u+n)%(2*n); } // ~u
	void addedge(int u, int nu, int v, int nv) { // add (X || Y) clauses
		u = nd(u, nu), v = nd(v, nv);
		tj.addedge(neg(u), v);
		tj.addedge(neg(v), u); 
	} 
	vi& solve() { // return solved vars, if no solution return vi()
		vi& scc = tj.get_scc();
		FOR(u, 0, n) if(scc[u] == scc[u+n]) return res;
		res.assign(n, -1);
		vi ord(2*n);
		FOR(i, 0, 2*n) ord[i] = i;
		sort(ALL(ord), [&](int u, int v) { return scc[u] > scc[v]; });
		FOR(i, 0, 2*n) {
			int u = ord[i];
			if(res[u%n] == -1) res[u%n] = !(u<n);
		}
		return res;
	}
};

Cut-Vertex

// Find Bridge
const int MAXN = 3e5, INF = 0x7fffffff;
int ncnt, vid[MAXN], par[MAXN];
vii g[MAXN]; // (v, bridge flag)
int dfs(int u) {
	int ret = vid[u] = ncnt++;
	for(auto& e : g[u]) {
		int v = e.se, c = INF;
		if(par[u] == v) continue; // Tree edge
		if(vid[v] == -1) { // Tree Edge
			par[v] = u;
			c = min(c, dfs(v));
		} else c = min({ c, vid[v], vid[u] }); // Forward/Backward Edge
		if(c > vid[u]) e.fi = 1; // Bridge
		ret = min(ret, c);
	}
	return ret;
}

String

KMP Algorithm

string s, t;
vi getpi(const string& str) {
	int n = str.size(), len = 0;
	vi pi(n, 0);
	FOR(i, 1, n) {
		while(len && str[len] != str[i]) len = pi[len-1];
		if(str[len] == str[i]) pi[i] = ++len;
	}
	return pi;
}

vi kmp() {
	int n = s.size(), m = t.size(), len = 0;
	vi ret, pi = getpi(t);
	FOR(i, 0, n) {
		while(len && s[i] != t[len]) len = pi[len-1];
		if(s[i] == t[len] && ++len == m) ret.pb(i-len+1), len = pi[len-1];
	}
	return ret;
}

Rabin-Karp Algorithm

// f(p) = s[0] + s[1] * p + s[2] * p^2 + ... + s[n-1] * p^{n-1)
// h[i+1] = p * (h[i] - s[i] * s^(m-1)) + s[i+m]
// --> sub first character from hash > hash degree up > add last character to hash
const i64 MUL = 232153, MD = 1012924417; // be careful for MD not MOD
void mod(i64& x) { x %= MD; if(x < 0) x += MD; }
vi rabin(string& s, string& t) { // return start indexs
	vi ret;
	i64 ht = 0, hs = 0, mul = 1;
	RFOR(i, sz(t)-1, 0) { // get t's hash
		mod(ht += mul * t[i] % MD);
		mod(mul = mul * MUL);
	}
	mul = 1;
	RFOR(i, sz(t)-1, 0) { // get s's hash for first sz(t) string
		mod(hs += mul * s[i] % MD);
		if(i != 0) mod(mul = mul * MUL); // mul must be p^{m-1)
	}
	if(hs == ht) ret.pb(0);
	FOR(i, sz(t), sz(s)) {
		mod(hs -= mul*s[i-sz(t)]%MD);
		mod(hs *= MUL);
		mod(hs += s[i]);
		if(hs == ht) ret.pb(i-sz(t)+1);
	}
	return ret;
}

Trie (Array)

const int MAX_NODE = 1e6+10;
int cld[MAX_NODE][30];
i64 cnt[MAX_NODE];
int ncnt = 1;
void push(const string& x) {
	int u = 0;
	FOR(i, 0, x.size()) {
		if(!cld[u][x[i]-'a']) cld[u][x[i]-'a'] = ncnt++;
		u = cld[u][x[i]-'a'];
	}
	++cnt[u];
}
void calc_back(int u) {
	FOR(i, 0, 30) {
		if(cld[u][i]) {
			calc_back(cld[u][i]);
			cnt[u] += cnt[cld[u][i]];
		}
	}
	cnt[u] %= MOD;
}

Aho-Corasick Algorithm

const int MAXNODE = 1e5+10, MAXC = 26, INITCHAR = 'a';
struct ahocorasick {
	int ncnt, t[MAXNODE][MAXC], f[MAXNODE], chk[MAXNODE];
	ahocorasick() : ncnt(0) { memset(t, 0, sizeof(t)), memset(f, 0, sizeof(f)), memset(chk, 0, sizeof(chk)); }
	void insert(const string& s) {
		int u = 0;
		for(auto i : s) {
			i -= INITCHAR;
			if(!t[u][i]) t[u][i] = ++ncnt;
			u = t[u][i];
		}
		chk[u] = 1; // end of string
	}
	void precalc() {
		queue<int> q;
		FOR(i, 0, MAXC) if(t[0][i]) q.push(t[0][i]);
		// calculdate fail, chk with bfs
		while(q.size()) {
			int x = q.front(); q.pop();
			FOR(i, 0, MAXC) {
				if(t[x][i]) {
					int u = x, p = f[u];
					while(p && !t[p][i]) p = f[p]; // find fail link
					u = t[u][i], p = t[p][i]; // goto original target node
					f[u] = p;
					if(chk[p]) chk[u] = 1;
					q.push(u);
				}
			}
		}
	}
	bool query(const string& s) {
		int u = 0;
		for(auto i : s) {
			i -= INITCHAR;
			while(u && !t[u][i]) u = f[u];
			if(chk[u = t[u][i]]) return true;
		}
		return false;
	}
};

Suffix Array + LCP

/*
	sa[i] = ordered suffix (suffix's start position)
	ord[i] = [i:]'s index in sa  (ord[sa[i]] = i)
	lcp[i] = longest common prefix length of two suffix [i-1:], [i:]
	
	LCP's Lemma
	1.	Two adjacent in SA suffixes' LCP is always bigger than which of non-adjacents
	2.	lcp(sa[i-1], sa[i]) = h, h >= 1 then
		lcp(sa[i-1]+1, sa[i]+1) = h-1
		
	So that lcp[sa[i]+1] >= h-1 because it is always bigger than lcp(sa[i-1]+1, sa[i]+1) by Lemma 1
	and by Lemma 2, lcp(sa[i-1]+1, sa[i]+1) = h-1
*/
struct sfxarray {
	int n;
	string& str;
	vi sa, lcp, ord;
	sfxarray(string& str) : str(str), n(str.size()) { }
	void getsa() {
		sa = ord = vi(n+1);
		FOR(i, 0, n) sa[i] = i, ord[i] = str[i]; ord[n] = 0;
		for(int t = 1; t <= n; t *= 2) {
			int sz = max(257, n+1);
			vi cnt, tmp;
			cnt = tmp = vi(sz, 0);
			FOR(i, 0, n) ++cnt[ord[min(n, i+t)]];
			FOR(i, 1, sz) cnt[i] += cnt[i-1];
			FOR(i, 0, n) tmp[--cnt[ord[min(n, i+t)]]] = i;
			cnt = vi(sz, 0);
			FOR(i, 0, n) ++cnt[ord[i]];
			FOR(i, 1, sz) cnt[i] += cnt[i-1];
			RFOR(i, n-1, 0) sa[--cnt[ord[tmp[i]]]] = tmp[i];
			tmp[sa[0]] = 1;
			FOR(i, 1, n) {
				int u = sa[i-1], v = sa[i];
				tmp[v] = tmp[u] + (ord[u] < ord[v] || ord[u+t] < ord[v+t]);
			}
			ord = tmp;
			if(ord[sa[n-1]] == n) break;
		}
		FOR(i, 0, n) --ord[i];
	}
	void getlcp() {
		lcp = vi(n, 0);
		for(int i = 0, len = 0; i < n; ++i, len = max(0, len-1)) {
			if(ord[i]) {
				for(int j = sa[ord[i]-1]; str[i+len] == str[j+len]; ++len);
				lcp[ord[i]] = len;
			}
		}
	}
	tuple<vi, vi, vi> build() { getsa(), getlcp(); return { sa, lcp, ord }; }
};

Manacher’s Algorithm

const int MAXN = 1000005;
int aux[2 * MAXN - 1];
void solve(int n, int *str, int *ret){
	// *ret : number of nonobvious palindromic character pair
	for(int i=0; i<n; i++){
		aux[2*i] = str[i];
		if(i != n-1) aux[2*i+1] = -1;
	}
	int p = 0, c = 0;
	for(int i=0; i<2*n-1; i++){
		int cur = 0;
		if(i <= p) cur = min(ret[2 * c - i], p - i);
		while(i - cur - 1 >= 0 && i + cur + 1 < 2*n-1 && aux[i-cur-1] == aux[i+cur+1]){
			cur++;
		}
		ret[i] = cur;
		if(i + ret[i] > p){
			p = i + ret[i];
			c = i;
		}
	}
}

Math

Fraction

// dependency: GCD(i64 a, i64 b)
struct frac {
	i64 a, b;
	frac(i64 _a=0, i64 _b=1) : a(_a), b(_b) { if(a == 0 && b == 0) b = 1; assert(b != 0); relax(); }
	// Essential: Basic Operations
	void relax() { i64 g = GCD(abs(a), abs(b)); a /= g, b /= g; }
	frac operator + (const frac &ot) const { return { a * ot.b + ot.a * b, b * ot.b }; }
	frac operator - (const frac &ot) const { return { a * ot.b - ot.a * b, b * ot.b }; }
	frac operator * (const frac &ot) const { return { a * ot.a, b * ot.b }; }
	frac operator / (const frac &ot) const { return { a * ot.b, b * ot.a }; }
	frac operator - () { return { -a, b }; }
	// Essential: Basic Comparation
	bool operator == (const frac& ot) const { return a * ot.b == ot.a * b; }
	bool operator < (const frac& ot) const { return a * ot.b < ot.a * b; }
	bool operator <= (const frac& ot) const { return a * ot.b <= ot.a * b; }
	bool operator > (const frac& ot) const { return ot <= *this; }
	bool operator >= (const frac& ot) const { return ot < *this; }
	// Optional: Advanced Operations
	const frac& operator += (const frac &ot) { return *this = *this + ot; }
	const frac& operator -= (const frac &ot) { return *this = *this - ot; }
	const frac& operator *= (const frac &ot) { return *this = *this * ot; }
	const frac& operator /= (const frac &ot) { return *this = *this / ot; }
};
// fraction IO
ostream& operator<< (ostream& os, const frac& frac_x) { return os << frac_x.a << "/" << frac_x.b; }
istream& operator>> (istream& os, frac& frac_x) {
	os >> frac_x.a >> frac_x.b;
	frac_x.relax();
	return os;
}

Matrix

// Do not use this class as const
typedef i64 ELEM;
const ELEM MOD = 1e9+7; // If don't use MOD, set as 0x7fffffffffffffff
struct mat {
	int n, m;
	vector<vector<ELEM> > ar;
	// ----- constructor, assignment  ----- //
	mat(int n, int m, ELEM x = 0) : n(n), m(m), ar(n, vector<ELEM>(m, x)) {  }
	mat(int n = 0) : mat(n, n) {  }
	mat(const mat& o) { n = o.n, m = o.m, ar = o.ar; }
	mat(const vector<vector<ELEM>>& ar) : n(ar.size()), m(ar.size() ? ar[0].size() : 0), ar(ar) { }
	// ----- get field ----- //
	operator const vector<vector<ELEM> >& () const { return ar; }
	vector<ELEM>& operator[](int i) { return ar[i]; }
	const vector<ELEM>& operator[](int i) const { return ar[i]; }
	// ----- calculate ----- //
	mat pow(i64 x) const {
		assert(n == m && 0 <= x);
		mat a(*this), ret = eye(n);
		while(x) {
			if(x%2) ret = ret * a;
			a = a * a;
			x /= 2;
		}
		return ret;
	}
	mat operator * (const mat& o) const {
		assert(m == o.n);
		mat ret(n, o.m);
		FOR(i, 0, n) {
			FOR(j, 0, o.m) {
				FOR(k, 0, m) {
					ret[i][j] += ar[i][k] * o[k][j] % MOD;
					ret[i][j] %= MOD;
				}
			}
		}
		return ret;
	}
	mat operator + (const mat& o) const {
		assert(n == o.n && m == o.m);
		mat ret(n, m);
		FOR(i, 0, n) FOR(j, 0, n) ret[i][j] = (ar[i][j] + o[i][j]) % MOD;
		return ret;
	}
	mat operator - (const mat& o) const {
		assert(n == o.n && m == o.m);
		mat ret(n, m);
		FOR(i, 0, n) FOR(j, 0, n) ret[i][j] = (ar[i][j] - o[i][j]) % MOD;
		return ret;
	}
	mat operator * (const ELEM x) const {
		mat ret = ar;
		FOR(i, 0, n) FOR(j, 0, m) ret[i][j] = ret[i][j] * x % MOD;
		return ret;
	}
	mat operator / (const ELEM x) const {
		mat ret = ar;
		FOR(i, 0, n) FOR(j, 0, m) ret[i][j] = ret[i][j] / x % MOD;
		return ret;
	}
	const mat& operator - () {
		FOR(i, 0, n) FOR(j, 0, m) ar[i][j] = -ar[i][j];
		return *this;
	}
    // If use dp matrix as: state = state * dpmat
    // use rotated dpmat and horizontal state mat
	mat rotate() const {
		mat ret(m, n);
		FOR(i, 0, n) FOR(j, 0, m) ret[j][i] = ar[i][j];
		return ret;
	}
	static mat eye(const int size) {
		mat ret(size);
		FOR(i, 0, size) ret[i][i] = 1;
		return ret;
	}
	// return matrix dp
    // dp[i] = ar[0] * dp[i-n] + ar[1] * dp[i-n+1] + ... + ar[n-1] * dp[i-1]
	// data matrix br: br[0] = dp[i], br[1] = dp[i-1] ...
	// If DP equation contains constant, fix one element for constant
	static mat dpmat(const vector<ELEM>& ar) {
		int n = ar.size();
		mat ret(n, n);
		FOR(i, 0, n-1) ret[i][i+1] = 1; // transition prev dp values
		FOR(i, 0, n) ret[n-1][i] = ar[i]; // DP equation
		return ret;
	}
};
ostream& operator<<(ostream& os, const mat& v) { for(auto vv : (vector<vector<ELEM> >)v) os << vv << ENDL; return os; }

Miller-Rabin Test

namespace miller_rabin{ // O(logP)
	i64 mul(i64 x, i64 y, i64 mod){ return (__int128) x * y % mod; }
	i64 ipow(i64 x, i64 y, i64 p){
		i64 ret = 1, piv = x % p;
		while(y){
			if(y&1) ret = mul(ret, piv, p);
			piv = mul(piv, piv, p);
			y >>= 1;
		}
		return ret;
	}
	bool miller_rabin(i64 x, i64 a){
		if(x % a == 0) return 0;
		i64 d = x - 1;
		while(1){
			i64 tmp = ipow(a, d, x);
			if(d&1) return (tmp != 1 && tmp != x-1);
			else if(tmp == x-1) return 0;
			d >>= 1;
		}
	}
	bool isprime(i64 x){
		for(auto &i : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}){
			if(x == i) return 1;
			if(x > 40 && miller_rabin(x, i)) return 0;
		}
		if(x <= 40) return 0;
		return 1;
	}
}

Euler’s Sieve

const int RANGE = 2e7;
int pn, spf[RANGE], pr[RANGE]; // spf[x] = min prime factor of x
void eulerSieve() {
	FOR(x, 2, RANGE) {
		if(!spf[x]) spf[x] = pr[pn++] = x; // if x is prime, spf[x] = x
		for(int j = 0; x*pr[j] < RANGE; ++j) {
			spf[x*pr[j]] = pr[j];
			if(x % pr[j] == 0) break;
		}
	}
}

Binomial Coefficient

// 1. c[n][r] = c[n-1][r-1] + c[n-1][r]
// 2. nCr = n! / ((n-r)! * r!)
const int RANGE = 1e6;
// precalc: n!, n!^(-1) --> O(NlogP)
void precalc_1() {
	i64 ftr[RANGE], iftr[RANGE];
	ftr[0] = iftr[0] = 1;
	FOR(i, 1, RANGE) {
		ft[i] = (ft[i-1] * (i64)i) % MOD;
		ift[i] = (ift[i-1] * POW((i64)i, MOD-2)) % MOD;
	}
}
// (n-1)!^(-1) =  n*n!^(-1) --> O(n+logP)
void precalc_2() {
	i64 ftr[RANGE], iftr[RANGE];
	ftr[0] = iftr[0] = 1;
	FOR(i, 1, RANGE) ftr[i] = ftr[i-1] * i;
	iftr[RANGE-1] = POW(ftr[RANGE-1], MOD-2);
	RFOR(i, RANGE-2, 0) iftr[i] = (i * iftr[i+1]) % MOD;
}
// inv(1) = 1, inv(1) = -floor(p/i) + inv(p%i) --> O(n)
void precalc_3() {
	i64 inv[RANGE+1], ftr[RANGE], iftr[RANGE];
	inv[1] = 1;
	FOR(i, 2, RANGE+1) {
		inv[i] = inv[MOD % i] - (MOD / i);
		if(inv[i] < 0) inv[i] += MOD;
		inv[i] %= MOD;
	}
}

Inclusion–Exclusion Principle

FOR(i, 1, (1 << n)) { // get Union(A, B, C, D ...)
    int bits = __builtin_popcount(i);
    if(bits % 2); // add to ans
    else; // sub to ans
}

Josephus problem

/*	O(n)
	f(n, k) = last survived person for n-people, k-cycle
	
	< basic idea >
	except 1 element from f(n, k), then answer is f(n-1, k)
	but f(n-1, k) need to be repositioned to starting from kth's next person
	
	< 1-indexed >
	f(1, k) = 1
	f(n, k) = ((f(n-1, k) + k-1) % n) + 1
	< 0-indexed >
	f(1, k) = 0;
	f(n, k) = ((f(n-1, k) + k) % n)
*/
// O(KlogN) algorithm 
long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

Segment Tree

Fenwick Tree Tricks

struct fenwick {
	int n;
	vector<i64> t;
	void init(int _n) { n = _n, t = vector<i64>(n+1, 0); }
	void add(int u, i64 x) { for(++u; u < t.size(); u += (u&-u)) t[u] += x; }
	i64 sum(int u) {
        i64 ret = 0;
		for(++u; u > 0; u -= (u&-u)) ret += t[u];
		return ret;
	}
	i64 operator[](int u) {
		++u;
		int ret = t[u], p = u - (u&-u);
		--u;
		while(u != p) {
			ret -= t[u];
			u -= (u&-u);
		}
		return ret;
	}
	// Can use all elements are positive.
	// k >= 0
	// find x which ( sum[a[0]..a[x-1]] < k <= sum[a[0]..a[x]] )
	int lower(i64 k) {
		if(k < 0) return 0;
		int l = (1 << (8*sizeof(int) - __builtin_clz(n)) - 1);
		int u = 0;
		while(l > 0 && u <= n) {
			int tu = u + l;
			if(k > t[tu]) u = tu, k -= t[tu];
			do l >>= 1;
			while(l > 0 && u + l > n);
		}
		return u;
	}
	// find x which ( sum[a[0]..a[x-1]] <= k < sum[a[0]..a[x]] )
	int upper(i64 k) {
		if(k < 0) return 0;
		int l = (1 << (8*sizeof(int) - __builtin_clz(n)) - 1);
		int u = 0;
		while(l > 0 && u <= n) {
			int tu = u + l;
			if(k >= t[tu]) u = tu, k -= t[tu];
			do l >>= 1;
			while(l > 0 && u + l > n);
		}
		return u;
	}
};

Fenwick Tree 2D (Sparse)

struct segtree {
	vi ys[RANGE], t[RANGE];
	// Notify segtree update access on (x, y)
	void initpos(int x, int y) {
		for(++x; x < RANGE; x += (x&-x)) {
			ys[x].pb(y);
		}
	}
	// Execute after notifying (x, y)
	void init() {
		FOR(i, 0, RANGE) sort(ALL(ys[i])), UNIQUE(ys[i]), t[i].assign(ys[i].size()+1, 0);
	}
	// add (x, y) to c
	void add(int x, int y, int c) {
		for(++x; x < RANGE; x += (x&-x)) {
			for(int j = getidx(ys[x], y)+1; j < sz(t[x]); j += (j&-j)) {
				t[x][j] += c;
			}
		}
	}
	// partial sum of ([..x], [..y])
	int sum(int x, int y) {
		int ret = 0;
		for(++x; x > 0; x -= (x&-x)) {
			int j = getidx(ys[x], y);
			if(j == ys[x].size() || ys[x][j] > y) --j;
			for(++j; j > 0; j -= (j&-j)) {
				ret += t[x][j];
			}
		}
		return ret;
	}
} seg;

Fenwick Tree Range Update/Query

struct rfenwick { // using 2 basic fenwick tree
	fenwick ax, b;
	void init(int n) { ax.init(n), b.init(n); }
	void add(int u, i64 x) { b.add(u, x); }
	void add(int s, int e, i64 x) {
		ax.add(s, x);
		ax.add(e+1, -x);
		b.add(s, -x * (s-1));
		b.add(e+1, x * e);
	}
	i64 sum(int u) {
		return u * ax.sum(u) + b.sum(u);
	}
};

Segment Tree (Loop)

template<class T, class C>
struct segtree {
	int n;
	vector<T> t;
	void build(const vector<T>& ar) {
		n = ar.size();
		t.assign(n*2, 0);
		FOR(i, 0, n) t[n+i] = ar[i];
		RFOR(i, n-1, 1) t[i] = C()(t[i*2], t[i*2+1]);
	}
	void mod(int u, T k) {
		for(t[u += n] = k; u > 1; u /= 2) t[u/2] = C()(t[u], t[u^1]);
	}
	T query(int s, int e) {
		T ret = 0;
		for(s += n, e += n; s < e; s /= 2, e /= 2) {
			if(s & 1) ret = C()(ret, t[s++]);
			if(e & 1) ret = C()(ret, t[--e]);
		}
		return ret;
	}
};

Segment Tree 2D (Dense)

struct segtree {
	int n, m;
	vvi t;
	void init(const vvi& ar) {
		n = ar.size(), m = ar[0].size();
		t.assign(2*n, vi(2*m, 0));
		FOR(y, 0, n) { // push in leaf
			FOR(x, 0, m) {
				t[n+y][m+x] = ar[y][x];
			}
		}
		RFOR(y, 2*n-1, 1) { // construct
			RFOR(x, 2*m-1, 1) {
				if(y < n) t[y][x] = t[y*2][x] + t[y*2+1][x];
				if(x < m) t[y][x] = t[y][x*2] + t[y][x*2+1];
			}
		}
	}
	void modify(int y, int x, int c) {
		t[y + n][x + m] = c; // leaf update
		for(y += n; y > 0; y /= 2) {
			for(int x2 = x + m; x2 > 0; x2 /= 2) {
				if(y < n) t[y][x2] = t[y*2][x2] + t[y*2+1][x2];
				if(x2 < m) t[y][x2] = t[y][x2*2] + t[y][x2*2+1];
			}
		}
	}
	int query(int sy, int sx, int ey, int ex) {
		int ret = 0;
		for(sy += n, ey += n; sy < ey; sy /= 2, ey /= 2) {
			for(int x1 = sx + m, x2 = ex + m; x1 < x2; x1 /= 2, x2 /= 2) {
				if(sy&1) {
					if(x1&1) ret += t[sy][x1];
					if(x2&1) ret += t[sy][x2-1];
				}
				if(ey&1) {
					if(x1&1) ret += t[ey-1][x1];
					if(x2&1) ret += t[ey-1][x2-1];
				}
				if(x1&1) ++x1;
				if(x2&1) --x2;
			}
			if(sy&1) ++sy;
			if(ey&1) --ey;
		}
		return ret;
	}
};

Lazy Propagation

const int ST_MAX = 1<<21, lf = ST_MAX/2; 
struct segtree{
	i64 t[ST_MAX], d[ST_MAX];
	segtree(){ memset(t, 0, sizeof(t)), memset(d, 0, sizeof(d)); }
	void build(){ RFOR(i, lf-1, 1) t[i] = t[i*2]+ t[i*2+1]; } // !! BUILD !!
	void propagate(int u, int ns, int ne){
		if(!d[u]) return;
		if(u < lf){ // propagate to childs
			d[u*2] += d[u];
			d[u*2+1] += d[u];
		}
		t[u] += d[u] * (ne-ns); // update node
		d[u] = 0;
	}
	void add(int s, int e, int x){ add(s, e, x, 1, 0, lf); } // [s, e)
	void add(int s, int e, int x, int u, int ns, int ne){
		propagate(u, ns, ne);
		if(e <= ns || ne <= s) return;
		if(s <= ns && ne <= e){
			d[u] += x;
			propagate(u, ns, ne);
			return;
		}
		int mid = (ns+ne)/2;
		add(s, e, x, u*2, ns, mid), add(s, e, x, u*2+1, mid, ne);
		t[u] = t[u*2] + t[u*2+1];
	}
	i64 sum(int s, int e){ return sum(s, e, 1, 0, lf); } // [s, e)
	i64 sum(int s, int e, int u, int ns, int ne){
		propagate(u, ns, ne);
		if(e <= ns || ne <= s) return 0;
		if(s <= ns && ne <= e) return t[u];
		int mid = (ns+ne)/2;
		return sum(s, e, u*2, ns, mid) + sum(s, e, u*2+1, mid, ne);
	}
};

Persistent Segment Tree

struct node {
	int x;
	node *l, *r;
	node(int _x = 0, node* l = 0, node* r = 0) : x(_x), l(l), r(r) {  }
	node* addtree(int u, int c, int ns = 0, int ne = MAXN-1) {
		if(ns <= u && u <= ne) {
			if(ns == ne) return new node(x + c, 0, 0);
			int mid = (ns+ne)/2;
			return new node(x + c, l->addtree(u, c, ns, mid), r->addtree(u, c, mid+1, ne));
		}
		return this;
	}
	int query(int s, int e, int ns = 0, int ne = MAXN-1) {
		if(s <= ns && ne <= e) return x;
		if(ne < s || e < ns) return 0;
		int mid = (ns+ne)/2;
		return l->query(s, e, ns, mid) + r->query(s, e, mid+1, ne);
	}
} *root[MAXN+1];

Persistent Segment Tree (Array)

struct pst {
	i64 x[MAXN*LOGN];
	int l[MAXN*LOGN], r[MAXN*LOGN], tcnt;
	int base(int ns = 0, int ne = MAXN-1) { // make 0th tree
		int u = tcnt++;
		l[u] = u, r[u] = u;
	}
	int make(int idx, int c, int u, int ns = 0, int ne = MAXN-1) { // update from u-rooted
		if(idx < ns || ne < idx) return u;
		int v = tcnt++;
		if(ns == ne) x[v] = (x[u] + c) % MOD;
		else {
			int m = (ns+ne)/2;
			l[v] = make(idx, c, l[u], ns, m);
			r[v] = make(idx, c, r[u], m+1, ne);
			x[v] = (x[l[v]] + x[r[v]]) % MOD;
		}
		return v;
	}
	i64 query(int s, int e, int u, int ns = 0, int ne = MAXN-1) { // query from u-rooted
		if(s <= ns && ne <= e) return x[u];
		if(ne < s || e < ns) return 0;
		int m = (ns+ne)/2;
		return (query(s, e, l[u], ns, m) + query(s, e, r[u], m+1, ne)) % MOD; 
	}
};

HLD (Vertex)

/*
	HLD with costed vertex.

	usually (dfs_init, lca, decomposite, eidx, query) don't need to be changed.
	just modify (segtree, init_segs), and if segtree function changed modify (update, query_to)
*/
const int MAXN = 1e5+10, LOGN = 18, INF = 0x7fffffff;
struct hld_vtx {
	struct segtree {
		int n;
		vi t;
		void init(int _n) { n = _n; t.assign(2*n, INF); }
		void update(int u, int x) {
			for(t[u += n] = x; u > 1; u /= 2) t[u/2] = min(t[u], t[u^1]);
		}
		int query(int s, int e) {
			int ret = INF;
			for(s += n, e += n; s < e; s /= 2, e /= 2) {
				if(s&1) ret = min(ret, t[s++]);
				if(e&1) ret = min(ret, t[--e]);
			}
			return ret;
		}
	};	
	int n, rt;
	vi ssz, dep, hidx;
	vvi g, par, hvy;
	vector<segtree> segs;
	hld_vtx(vvi& g, int rt) : g(g), rt(rt), n(g.size()), ssz(n, 0), dep(n, 0), hidx(n, -1), par(n, vi(LOGN, 0)) { 
		par[rt][0] = rt;
		dfs_init(rt);
		decomposite(rt);
		init_segs();
	}
	void dfs_init(int u) { // initialize dfs info
		ssz[u] = 1;
		FOR(j, 1, LOGN) par[u][j] = par[par[u][j-1]][j-1];
		for(int v : g[u]) {
			if(par[u][0] == v) continue;
			par[v][0] = u;
			dep[v] = dep[u] + 1;
			dfs_init(v);
			ssz[u] += ssz[v];
		}
	}
	int lca(int u, int v) { // consider par[root] = root
		if(dep[u] < dep[v]) swap(u, v);
		int dif = dep[u] - dep[v];
		FOR(j, 0, LOGN) if(dif & (1<<j)) u = par[u][j];
		if(u != v) {
			RFOR(j, LOGN-1, 0) if(par[u][j] != par[v][j]) u = par[u][j], v = par[v][j];
			u = par[u][0];
		}
		return u;
	}
	void decomposite(int rt) { // decomposite tree
		queue<int> q;
		q.push(rt);
		while(q.size()) {
			int u = q.front(); q.pop();
			for(int v : g[u]) if(par[v][0] == u) q.push(v);
			int p = par[u][0];
			if(u != rt && ssz[u]*2 >= ssz[p]) { // extend h-path
				hidx[u] = hidx[p];
				hvy[hidx[u]].pb(u);
			} else { // create h-path
				hidx[u] = hvy.size();
				hvy.pb(vi());
				hvy[hidx[u]].pb(u);
			}
		}
	}
	void init_segs() { // initialize segtrees
		segs.assign(hvy.size(), segtree());
		FOR(i, 0, hvy.size()) segs[i].init(hvy[i].size()); // m nodes
	}
	int vidx(int u) { // get v's index in h-path
		return dep[u] - dep[hvy[hidx[u]][0]];
	}
	void update(int u, int x) { // update v's cost
		if(x == 0) segs[hidx[u]].update(vidx(u), INF);
		else segs[hidx[u]].update(vidx(u), vidx(u));
	}	
	int query(int v) { // root->v query
		return query_to(0, v);
	}	
	int query_to(int u, int v) { // return u->v path's query
		if(hidx[u] == hidx[v]) {
			int res = segs[hidx[u]].query(vidx(u), vidx(v)+1);
			if(res == INF) return INF;
			return hvy[hidx[u]][res];
		}
		int res = query_to(u, par[hvy[hidx[v]][0]][0]);
		if(res != INF) return res;
		res = segs[hidx[v]].query(0, vidx(v)+1);
		if(res == INF) return INF;
		return hvy[hidx[v]][res];
	}
};

HLD (Edge)

/*
	HLD with costed edge.
	Unlike the normal HLD, top edge of each chains are also belongs to chain.

	usually (dfs_init, lca, decomposite, eidx, query) don't need to be changed.
	just modify (segtree, init_segs), and if segtree function changed modify (update, query_to)
*/
const int LOGN = 18;
struct hld_edge {
	struct segtree { // just edit segtree ( currently half-open interval [s, e) )
		int n;
		vi t;
		void init(int _n) { n = _n; t.assign(2*n, 0); }
		void update(int u, int x) {
			for(t[u += n] = x; u > 1; u /= 2) t[u/2] = max(t[u], t[u^1]);
		}
		int query(int s, int e) {
			int ret = 0;
			for(s += n, e += n; s < e; s /= 2, e /= 2) {
				if(s&1) ret = max(ret, t[s++]);
				if(e&1) ret = max(ret, t[--e]);
			}
			return ret;
		}
	};
	int n, rt;
	vi ssz, dep, hidx;
	vvi g, par, hvy;
	vector<segtree> segs;
	hld_edge(vvi& g, int rt) : g(g), rt(rt), n(g.size()), ssz(n, 0), dep(n, 0), hidx(n, -1), par(n, vi(LOGN, 0)) { 
		par[rt][0] = rt;
		dfs_init(rt);
		decomposite(rt);
		init_segs();
	}
	void dfs_init(int u) { // initialize dfs info
		ssz[u] = 1;
		FOR(j, 1, LOGN) par[u][j] = par[par[u][j-1]][j-1];
		for(int v : g[u]) {
			if(par[u][0] == v) continue;
			par[v][0] = u;
			dep[v] = dep[u] + 1;
			dfs_init(v);
			ssz[u] += ssz[v];
		}
	}
	int lca(int u, int v) { // consider par[root] = root
		if(dep[u] < dep[v]) swap(u, v);
		int dif = dep[u] - dep[v];
		FOR(j, 0, LOGN) if(dif & (1<<j)) u = par[u][j];
		if(u != v) {
			RFOR(j, LOGN-1, 0) if(par[u][j] != par[v][j]) u = par[u][j], v = par[v][j];
			u = par[u][0];
		}
		return u;
	}
	void decomposite(int rt) { // decomposite tree
		hidx[rt] = -1;
		queue<int> q;
		q.push(rt);
		while(q.size()) {
			int u = q.front(); q.pop();
			for(int v : g[u]) if(par[v][0] == u) q.push(v);
			if(u != rt) {
				int p = par[u][0];
				if(p != rt && ssz[u]*2 >= ssz[p]) { // extend h-path (only if h-path)
					hidx[u] = hidx[p];
					hvy[hidx[u]].pb(u);
				} else { // create h-path (l-path or root-h-path)
					hidx[u] = hvy.size();
					hvy.pb(vi());
					hvy[hidx[u]].pb(p);
					hvy[hidx[u]].pb(u);
				}
			}
		}
	}
	void init_segs() { // initialize segtrees
		segs.assign(hvy.size(), segtree());
		FOR(i, 0, hvy.size()) segs[i].init(hvy[i].size()-1); // m vertices: m-1 edges
	}
	int eidx(int v) { // get u->v edge index in h-path
		return dep[par[v][0]] - dep[hvy[hidx[v]][0]];
	}
	void update(int u, int v, int x) { // u->v edge update
		if(par[u][0] == v) swap(u, v);
		assert(par[v][0] == u);
		segs[hidx[v]].update(eidx(v), x);
	}
	int query_to(int u, int v) { // return u->v path's query
		if(u == v) return 0;
		// modify range if segtree use closed interval [s, e]
		if(hidx[u] == hidx[v]) return segs[hidx[u]].query(eidx(u)+1, eidx(v)+1); // e(u)+1 because target is edge
		return max(query_to(u, hvy[hidx[v]][0]), segs[hidx[v]].query(0, eidx(v)+1)); // query tail path + recur
	}
	int query(int u, int v) {
		int t = lca(u, v);
		return max(query_to(t, u), query_to(t, v));
	}
};

Miscellaneous

Preset

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class key, class value, class cmp = less<key>>
using treemap = tree<key, value, less<int>, rb_tree_tag, tree_order_statistics_node_update>; // key, val, comp, implements, 노드 불변 규칙
template<class key, class cmp = less<key>>
using treeset = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); }
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // for positive numbers
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ........................... MAIN ........................... //   
void input() { }
int solve() { return 0; }
void execute() { input(), solve(); }
int main(void) {
#ifdef LOCAL_BOOKNU
	freopen("__IO/input.txt", "r", stdin);
	// freopen("__IO/out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}

3D-Partial Sum

const int RANGE = 256;
int n, k, ps[RANGE][RANGE][RANGE], ar[RANGE][RANGE][RANGE];
int f(int x, int y, int z) {
	return (x < 0 || y < 0 || z < 0 || x >= RANGE || y >= RANGE || z >= RANGE ? 0 : ps[x][y][z]);
}
int sum(int x1, int y1, int z1, int l) {
	int x2 = min(RANGE - 1, x1 + l), y2 = min(RANGE - 1, y1 + l), z2 = min(RANGE - 1, z1 + l);
	--x1, --y1, --z1;
	return
		f(x2, y2, z2)
		- f(x1, y2, z2) - f(x2, y1, z2) - f(x2, y2, z1)
		+ f(x1, y1, z2) + f(x1, y2, z1) + f(x2, y1, z1)
		- f(x1, y1, z1);
}
void init() {
	FOR(x, 0, RANGE) {
		FOR(y, 0, RANGE) {
			FOR(z, 0, RANGE) {
				ps[x][y][z] +=
					f(x - 1, y, z) + f(x, y - 1, z) + f(x, y, z - 1)
					- f(x - 1, y - 1, z) - f(x - 1, y, z - 1) - f(x, y - 1, z - 1)
					+ f(x - 1, y - 1, z - 1);
			}
		}
	}
}

Knuth’s Optimization

DP Equation Form
- $D[i][j] = \min_{i < k < j}(D[i][k] + D[k][j]) + C[i][j]$
Quadrangle Inequality
- $C[a][c] + C[b][d] \leq C[a][d] + C[b][c], a \leq b \leq c \leq d$
Monotonicity
- $C[b][c] \leq C[a][d], a \leq b \leq c \leq d$

Define $A[i][j] = k \text{ for } D[i][j] \text{ becomes minimum}$

If condition $2$, $3$ is satisfied, then

$A[i][j-1] \leq A[i][j] \leq A[i+1][j]$

Bit Tricks

__builtin_clz(int x); // count leading-zero
__builtin_ctz(int x); // count tailing-zero
__builtin_clzll(i64 x);
__builtin_ctzll(i64 x);
__builtin_popcount(int x); // number of 1-bits
__builtin__ffs(int x); // lsb index (1-based, x = 0 -> 0)

floor(log2(n)): 31 - __builtin_clz(n|1);
// 00111, 01011, 01101, 01110, 10011, 10101...
i64 next_perm(i64 x) {
    i64 t = x|(x-1);
    return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(x) + 1))
}

Fast IO

class FastIO {
	int fd, bufsz;
	char *buf, *cur, *end;
public:
	FastIO(int _fd = 0, int _bufsz = 1 << 20) : fd(_fd), bufsz(_bufsz) {
		buf = cur = end = new char[bufsz];
	}
	~FastIO() { delete[] buf; }
	bool readbuf() {
		cur = buf;
		end = buf + bufsz;
		while(true) {
			size_t res = fread(cur, sizeof(char), end - cur, stdin);
			if(res == 0) break;
			cur += res;
		}
		end = cur;
		cur = buf;
		return buf != end;
	}
	bool hasNext() {
		while(true) {
			if(cur == end && !readbuf()) return false;
			if(isdigit(*cur) || *cur == '-') break;
			++cur;
		}
		return true;
	}
	int r() {
		while(true) {
			if(cur == end) readbuf();
			if(isdigit(*cur) || *cur == '-') break;
			++cur;
		}
		bool sign = true;
		if(*cur == '-') {
			sign = false;
			++cur;
		}
		int ret = 0;
		while(true) {
			if(cur == end && !readbuf()) break;
			if(!isdigit(*cur)) break;
			ret = ret * 10 + (*cur - '0');
			++cur;
		}
		return sign ? ret : -ret;
	}
} sc;

Input Format

while(scanf("%d", &n) > 0) { // until input ends
    scanf("%d: (%d)", &x, &y); // formatted input
    for(int i = 0; i < x; ++i) scanf("%d", &z);
}
getline(cin, line);

String Parsing

vector<string> split(string& target, string regex) { // using regex
	vector<string> ret;
	std::regex rgx(regex);
	std::sregex_token_iterator iter(target.begin(),
		target.end(),
		rgx,
		-1);
	std::sregex_token_iterator end;
	for( ; iter != end; ++iter) ret.pb(*iter);
	return ret;
}
vector<string> space_split(string& s) { // split by whitespace 
	istringstream iss(s);
	vector<string> ret(istream_iterator<string>{iss}, istream_iterator<string>());
	return ret;
}
std::to_string(42);
std::atoi("42");

Ordered Statistic Tree in g++

s.find_by_order(x); // 0-indexed
s.order_of_key(x) // 0-indexed, find first element x <= ar[idx]

Prime Numbers

165349, 232153, 1012924417

< 10^k    prime   # of prime          < 10^k            prime
	-------------------------------------------------------------
           7            4          10           9999999967
          97           25          11          99999999977
         997          168          12         999999999989
        9973         1229          13        9999999999971
       99991         9592          14       99999999999973
      999983        78498          15      999999999999989
     9999991       664579          16     9999999999999937
    99999989      5761455          17    99999999999999997
   999999937     50847534          18   999999999999999989

Random

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(0x14004); // 0x94949
int randint(int s, int e) { return uniform_int_distribution<int>(s, e)(rng); }

Hashing

struct chash {
	const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
	static unsigned long long hash_f(unsigned long long x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
	int operator()(int x) const { return hash_f(x)^RANDOM; }
};

gp_hash_table<key, int, chash> mp;
int main() {
	mp[1] = 1;
}

Read All

CCW

2019-08-30

booknu

알고리즘_Geometry

기하 CCW
- 개요
- 아이디어
개요
- 세 점 $A, B, C$가 있을 때 점의 방향 관계를 판별한다.
아이디어
- $\vec{a}\times\vec{b}$의 방향을 통해 판단할 수 있다.
Read All
벡터의 외적 기초

2019-08-30

booknu

기초수학

기하
- 외적의 정의
- 외적의 성질
외적의 정의

$\vec{a}\times\vec{b} = (a_2b_3-a_3b_2,\ a_3b_1-a_1b_3,\ a_1b_2-a_2b_1)$

$\vec{a}\times\vec{b}\\=\begin{vmatrix}a_2 & a_3 \\ b_2 & b_3\end{vmatrix}\vec{i}-\begin{vmatrix}a_1 & a_3 \\ b_1 & b_3\end{vmatrix}\vec{j}+\begin{vmatrix}a_1 & a_2 \\ b_1 & b_2\end{vmatrix}\vec{k}\\=\begin{vmatrix} \vec{i} & \vec{j} & \vec{k} \\ a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \end{vmatrix}$ $(\vec{i}, \vec{j}, \vec{k}$ 는 각 축의 단위 벡터$)$
- 방향: 두 벡터와 동시에 수직
- 크기: 두 벡터를 변으로 하는 평행사변형의 넓이
  - $\lvert\vec{a}\times\vec{b}\rvert = \lvert\vec{a}\rvert\lvert\vec{b}\rvert\sin\theta$
외적의 성질
- 분배 법칙
  - $\vec{a}\times(\vec{b}+\vec{c}) = (\vec{a}\times\vec{b})+(\vec{a}\times\vec{c})$
- 교환 법칙 성립 안 함
  - $\vec{a}\times\vec{b} = -\vec{b}\times\vec{c}$
- 스칼라배는 자유롭게 이동 가능
- $\vec{a} \times \vec{a} = \vec{0}$
Read All
벡터의 내적 기초

2019-08-30

booknu

기초수학

기하
내적의 정의

$\vec{a} \cdot \vec{b} = \lvert\vec{a}\rvert\lvert\vec{b}\rvert\cos\theta = a_1b_1+a_2b_2$
- 벡터를 다른 벡터에 정사영시킨 크기의 곱
내적의 특징
- 내적의 결과로 스칼라 값이 나옴
- 두 벡터 중 하나라도 $\vec{0}$이면 내적의 결과는 $0$
- $\vec{a} \cdot \vec{a} = \lvert\vec{a}\rvert\lvert\vec{a}\rvert\cos0 = \lvert\vec{a}\rvert^2$
- $\vec{a}//\vec{b}\ 이면\ \vec{a}\cdot \vec{b} = \pm\lvert\vec{a}\rvert\lvert\vec{b}\rvert $
  - 벡터가 평행하다는 뜻은, $\theta=$ $0$ or $\pi$
- $\vec{a} \perp \vec{b}\ 이면\ \vec{a} \cdot \vec{b} = 0$
- $\vec{a} \cdot \vec{b} = \lvert\vec{a}\rvert\lvert\vec{b}\rvert\cos\theta=\lvert\vec{a}\rvert\times\lvert\vec{b}\rvert의\ 정사영$
내적의 성질
- 교환 법칙
- 스칼라배는 자유롭게 이동 가능
- 분배법칙 성립
내적의 응용
- 수직 판별 (내적이 $0$)
- 두 벡터의 각
  - $\cos\theta = \frac{\vec{a}\cdot\vec{b}}{\lvert\vec{a}\rvert\lvert\vec{b}\rvert} = \frac{a_1b_1+a_2b_2}{\sqrt{ {a_1}^2+{a_2}^2} \times \sqrt{ {b_1}^2+{b_2}^2} }$
Read All

SCPC 2019 2차 예선 리뷰

2019-07-06

booknu

PS_대회

PS SCPC DP 완전탐색 부분합 기하 휴리스틱 SegTree

1번
2번
3번
4번

1번

DP 완전탐색

현재 숫자에서 각 자리수를 지워나갈 때, 숫자가 소수를 유지하며 지워지는 최대 횟수를 점수로 볼 때, 두 숫자의 점수를 비교하는 문제이다.

풀이 보기

문제 자체가 겉으로 보기에는 상당히 복잡해보인다.

단순하게 생각하면 각 자리를 지워보며 소수가 유지되는 최대값을 찾아가는 완전 탐색으로 풀 수 있다.

다섯 자리밖에 안 되는 숫자이기 때문에 완전 탐색으로도 시간초과가 나지 않겠지만, DP를 쓰면 더 안정적인 시간복잡도로 답을 구할 수 있을 것이다.

각 숫자를 상태공간으로 보고 해당 숫자에서 각 자리수를 지워나가며 재귀를 돌면 답을 구할 수 있다.

숫자의 각 자리를 지우는게 좀 귀찮긴 하지만, 이것은 다양한 방법으로 구현할 수 있다.

소스코드 보기

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

const int MAXN = 3e4+10;
int a, b, dp[MAXN];

// --> x*pr[j]에서 overflow 발생할 수 있음! 그러나 적당히 작은 RANGE에서는 소수 분포가 촘촘하기 때문에 발생하지 않음.
// --> RANGE 내의 소수 개수 = RANGE/ln(RANGE) --> 2e7에서 인접 소수 최대 차이 = 180, 4e6 = 140
const int RANGE = MAXN;
int pn, spf[RANGE], pr[RANGE]; // pr은 vi로 구현해도 됨. --> but 실행 시간 많이 늘어남.
void eulerSieve() {
	FOR(x, 2, RANGE) {
		if(!spf[x]) spf[x] = pr[pn++] = x; // x 자체가 소수이면 spf[x] = x이다.
		for(int j = 0; x*pr[j] < RANGE; ++j) { // x의 소수배들에 spf[x*pr] = pr로 칠해준다. (단, pr <= spf[x])
			spf[x*pr[j]] = pr[j];
			if(x % pr[j] == 0) break; // 좀 더 직관적으로 if(spf[x] == pr[j])로 구현해도 되지만, 똑같은 효과를 가진 코드이다.
		}
	}
}

void input() {
	// ---- !!! INIT GLOBAL VARIABLES !!! ---- //
	// ---- Interactive Cautions : cin.tie(0), freopen(...), Case #x: ---- //
	cin >> a >> b;
}

int f(int x) {
	int& ret = dp[x];
	if(ret != -1) return ret;
	if(spf[x] != x) return ret = 0; // 소수가 아님
	int cur = x, w = 1;
	ret = 0;
	while(cur) { // 각 자리를 지워보며 재귀
		ret = max(ret, f((cur/10) * w + x % w));
		cur /= 10;
		w *= 10;
	}
	return ++ret;
}

int solve() {
	if(f(a) > f(b)) cout << 1 << ENDL;
	else if(f(a) < f(b)) cout << 2 << ENDL;
	else cout << 3 << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	memset(dp, -1, sizeof(dp));
	eulerSieve();
	spf[0] = -1;
	int TTTT; cin >> TTTT;
	FOR(tttt, 0, TTTT) {
		cout << "Case #" << tttt+1 << ENDL;
		input(), solve();
	}
}

int main(void) {
#ifdef LOCAL_BOOKNU
// 	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

2번

DP 팰린드롬 부분 합

길이가 같은 $A, B$ 수열이 있을 때, 같은 인덱스에 같은 수가 있는 수를 유사도라고 한다.

$B$수열의 일부를 한 번만 뒤집을 수 있을 때, $A, B$ 수열의 유사도의 최대값을 구해야한다.

풀이 보기

구현이 은근히 까다로운 문제이다. 우선, 가장 쉬운 아이디어로 $B$의 모든 구간을 뒤집어보고 유사도를 판단하는 방법이 있다.

하지만 이 방법은 모든 구간을 선택하는데 $n^2$, 유사도를 비교하는데 $n$번의 연산이 필요하기 때문에 $O(n^3)$의 시간복잡도를 갖고, 시간초과가 발생한다.

$B$의 $[s, e]$ 구간을 뒤집었을 때를 생각해보면, 구간의 길이가 홀수인 경우 어떤 중점을 기준으로 A와 뒤집어진 상태로 매핑된다는 것을 알 수 있다.

즉, 아래 그림과 같이 매핑된다.

이것을 이용하면 팰린드롬의 문제처럼 구간의 길이를 점차 늘려가는 방식을 사용해 뒤집힌 구간에 대한 유사도 비교를 O(1)에 할 수 있다.

(이 때, 구현을 더 쉽게 하기 위해서 문자열 문제에서 많이 사용하는 숫자 사이에 #을 넣는 트릭을 사용할 수 있다.)

또한 뒤집히지 않은 구간에 대해서는 partial sum 아이디어를 이용하여 $[0, i]$의 유사도를 배열 형태로 저장해두면 임의의 구간에 대한 유사도 역시 $O(1)$에 구할 수 있으며, 결과적으로 모든 구간에 대해서 유사도 비교를 $O(1)$에 할 수 있으므로 시간 복잡도는 $O(n^2)$이 된다.

소스코드 보기

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

const int MAXN = 5e3+1;
int n, ar[MAXN], br[MAXN], ps[MAXN], ev[MAXN], od[MAXN];
void input() {
	// ---- !!! INIT GLOBAL VARIABLES !!! ---- //
	cin >> n;
	FOR(i, 0, n) cin >> ar[i];
	FOR(i, 0, n) cin >> br[i];
	memset(ps, 0, sizeof(ps));
	memset(ev, 0, sizeof(ev));
}

int rs(int s, int e) {
	if(s > e) return 0;
	return (e < n ? ps[e] : ps[n-1]) - (s > 0 ? ps[s-1] : 0);
}

int solve() {
	FOR(i, 0, n) ps[i] = (i ? ps[i-1] : 0) + (ar[i] == br[i]);
	int ans = ps[n-1];
	// 홀수
	FOR(i, 0, n) od[i] = ar[i] == br[i];
	FOR(len, 1, n) {
		FOR(i, len, n-len) {
			if(ar[i-len] == br[i+len]) ++od[i];
			if(ar[i+len] == br[i-len]) ++od[i];
			ans = max(ans, od[i] + rs(0, i-len-1) + rs(i+len+1, n-1));
		}
		FOR(i, len-1, n-len) {
			if(ar[i+len] == br[i-len+1]) ++ev[i];
			if(ar[i-len+1] == br[i+len]) ++ev[i];
			ans = max(ans, ev[i] + rs(0, i-len) + rs(i+len+1, n-1));
		}
	}
	cout << ans << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
#ifdef LOCAL_BOOKNU
	auto START_TIME = clock();
#endif
	int TTT; cin >> TTT;
	FOR(ttt, 0, TTT) cout << "Case #" << ttt+1 << ENDL,
		input(), solve();
#ifdef LOCAL_BOOKNU
	auto END_TIME = clock();
	cout << ENDL << END_TIME - START_TIME << "ms" << ENDL;
#endif
}

int main(void) {
#ifdef LOCAL_BOOKNU
// 	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

3번

그리디 기하

천장과 바닥으로 이루어진 구불구불한 도형이 주어질 때, 좌측 끝 $h_s$ 높이에서 출발하여 우측 끝 $h_e$ 높이로 최단거리로 이동할 때, 여러 최단 경로들이 나올 것이다.

(도형의 변은 $x$축 혹은 $y$축과 평행하며, 이동 역시 수평으로만 한다.)

이 때 가능한 최단 경로들을 한꺼번에 그리면 어떤 면적이 나올텐데 그 면적의 너비를 구하면 된다.

풀이 보기

도형의 전처리

우선, 이상하게 생긴 도형을 익숙하게 처리할 수 있도록 전처리를 해보자.

도형을 수직 단위로 끊으면 여러 직사각형들이 수평으로 나열된 형태가 된다.

(즉, 아래 그림과 같이 된다.)

훨씬 처리하기가 편하게 변했다.

최단경로의 면적

도형이 있을 때, 다음과 같은 면적을 구하는 것이 문제의 요구사항이다.

이 때 관찰할 수 있는 것은, 이 면적이 어떠한 위 껍질과, 아래 껍질로 이루어진 도형이라는 것이다.

그 껍질이 가지는 특성을 알아내면, 쉽게 면적도 알아낼 수 있을 것이다.

위 껍질의 성질

우선 아래 껍질은 제쳐두고, 위 껍질의 특성부터 알아보자.

직관적으로는 위 껍질의 특성이 도형을 위아래로 뒤집은 도형의 특성에 적용되면 아래 껍질을 구할 수 있을 것 같다는 추측을 할 수 있으므로, 위 껍질부터 알아보자.

또한, 다음 그림과 같이 일관성을 위해 시작/끝 높이에 상관 없이, 가장 왼쪽 도형의 맨 위쪽에서 시작해 가장 오른쪽 도형의 맨 위쪽으로 가는 경로들에 대해서 생각하자.

위 껍질은 가능한 최단 경로 중 최대한 위쪽을 타고 가려는 특성을 가지고 있다.

하지만, 끝 높이가 낮은 경우는 마냥 위쪽을 타고 갈 수는 없다.

그렇다고 항상 끝 높이보다 낮은 높이를 유지해야 하는 것도 아니다.

따라서 이들 사이에 관계를 찾기 위해 현재 어떤 직사각형 $i$까지 왔고, 현재 높이가 $h$이며, 현재 직사각형의 다음 직사각형 중 임의의 직사각형을 $j$라고 할 때, 이 직사각형에서는 어떤 높이를 유지해야 하는지를 알아보자.

단순히 바로 다음 직사각형만을 보고 결정할 수 없다는 것은 간단한 예제들로 알 수 있다.

그러므로 뒤의 모든 직사각형을 고려해야 하는데, 여러가지 시도를 해보면 다음과 같은 두 가지 경우가 높이를 제한한다는 것을 알 수 있다.

(설명의 편의를 위해 직사각형의 아래 높이를 $h_s$, 위 높이를 $h_e$라고 한다.)

높이를 높일 수 없는 경우 (상한)

$h[i]_e > h[j]_e$ 인 $j$가 존재할 경우, 현재 직사각형에서는 최대 $h[j]_e$까지 밖에 못올라간다.
높이를 줄일 수 없는 경우 (하한)

1번과 반대로 높이를 $x$로 줄이려고 할 때, $x < h[j]_s$ 인 $j$가 존재할 경우, 높이는 $h[j]_s$까지 밖에 줄이지 못한다.

아래 껍질의 경우

위 껍질이 최대한 위를 타고 가려는 특성이 있다면, 아래 껍질 역시 최대한 아래를 다고 가려는 특성이 있다.

따라서 위 껍질을 구하는 알고리즘을 그대로 이용하면 아래 껍질 역시 쉽게 구할 수 있다.

소스코드 보기

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

struct rect {
	int s, e, w;
	rect(int s = 0, int e = 0, int w = 0) : s(s), e(e), w(w) { }
};

const int MAXN = 1e5+10;
int n, m, tlen, begh, finh, ah[MAXN], aw[MAXN], bh[MAXN], bw[MAXN];
vector<rect> ar;
void input() {
	// ---- !!! INIT GLOBAL VARIABLES !!! ---- //
	cin >> tlen >> begh >> finh;
	cin >> n;
	FOR(i, 0, n) cin >> aw[i] >> ah[i]; ah[n] = ah[n-1];
	cin >> m;
	FOR(i, 0, m) cin >> bw[i] >> bh[i]; bh[m] = bh[m-1];
}

// 직사각형 형태로 만든다.
void generateRec() {
	ar.clear();
	int ap = 0, bp = 0, x = 0, ax = 0, bx = 0;
	while(ap < n || bp < m) {
		rect cur;
		if(bp == m || (ap < n && ax + aw[ap] < bx + bw[bp])) {
			cur = { bh[bp], ah[ap], ax + aw[ap] - x };
			x = ax = ax + aw[ap];
			++ap;
		} else {
			cur = { bh[bp], ah[ap], bx + bw[bp] - x };
			x = bx = bx + bw[bp];
			++bp;
		}
		if(cur.w != 0) ar.pb(cur);
	}
}

// 조건에 맞는 껍질을 { height }로 반환
vector<int> getConvex(vector<rect>& ar, int beg) {
	vector<int> ret(ar.size(), 0);
	vector<int> minu(ar.size()), maxd(ar.size());
	// i에서부터의 상한, 하한을 구한다.
	RFOR(i, sz(ar)-1, 0) {
		minu[i] = min(i+1 == ar.size() ? 0x7fffffff : minu[i+1], ar[i].e);
		maxd[i] = max(i+1 == ar.size() ? -0x7fffffff : maxd[i+1], ar[i].s);
		// 현재에서 상한, 하한이 서로를 뛰어 넘는 경우
		// 상한이 하한보다 낮아진다면? 하한을 이걸로 조정!
		if(ar[i].e < maxd[i]) maxd[i] = ar[i].e;
		// 하한이 상한보다 높아진다면? 상한을 이걸로 조정!
		if(ar[i].s > minu[i]) minu[i] = ar[i].s;
	}
	int cur = beg;
	FOR(i, 0, ar.size()) {
		// 현재 높이보다 낮아질 필요는 없다.
		ret[i] = min(cur, ar[i].e);
		// 하한보다 낮아질 필요는 없다.
		ret[i] = max(ret[i], min(ar[i].e, maxd[i]));
		// 상한보다는 낮아야 한다.
		ret[i] = max(ret[i], max(ar[i].s, minu[i]));
		cur = ret[i];
	}
	return ret;
}

int solve() {
	generateRec();
	// 귀찮은거 따로 처리
	if(ar.size() == 1) {
		cout << (i64)ar[0].w * abs(begh - finh) << ENDL;
		return 0;
	}
	// 위 껍질 찾기
	vector<rect> tmp = ar;
	tmp.pb({ finh, finh, 0 });
	vector<int> up = getConvex(tmp, begh);
	debug(up);
	// 아래 껍질 찾기
	FOR(i, 0, ar.size()) {
		ar[i].s = -ar[i].s;
		ar[i].e = -ar[i].e;
		swap(ar[i].s, ar[i].e);
	}
	ar.pb({ -finh, -finh, 0 });
	vector<int> dw = getConvex(ar, -begh);
	debug(dw);
	// 계산
	i64 ans = 0;
	FOR(i, 0, ar.size()-1) {
		ans += (i64)ar[i].w * (up[i] + dw[i]);
	}
	cout << ans << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
#ifdef LOCAL_BOOKNU
	auto START_TIME = clock();
#endif
	int TTT; cin >> TTT;
	FOR(ttt, 0, TTT) cout << "Case #" << ttt+1 << ENDL,
		input(), solve();
#ifdef LOCAL_BOOKNU
	auto END_TIME = clock();
	cout << ENDL << END_TIME - START_TIME << "ms" << ENDL;
#endif
}

int main(void) {
#ifdef LOCAL_BOOKNU
// 	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

후기

삽질하면서 푸느라 설명도 좀 이상해지고 코드에도 쓸모 없는 부분이 있을 것 같은데, 나중에 더 깔끔한 풀이를 보고 다시 풀어봐야겠다.

4번

휴리스틱 그리디

$50 \times 500$의 맵이 주어지고, 부숴야 할 집들이 주어진다.

하나의 폭탄은 $3 \times 3$범위만을 폭파시킬 수 있을 때, 폭탄을 최소로 사용해 모든 집을 부숴야 한다.

풀이 보기

우선 위의 식을 개념적으로 풀어서 이해하면, 일단 세그먼트 단위로 쪼갠 후, 각 세그먼트에 들어있는 원소들의 합에 세그먼트 idx를 곱한것들의 합을 구하는 것으로 바뀐다. 즉, 현재 맵에서 $3 \times 3$ 범위 중 집이 가장 많이 포함되는 곳을 선택해 폭탄을 사용하는 방식으로 구현했다.

모든 경우에서 최적의 결과가 나오지는 않지만, 그럭저럭 좋은 결과는 나온다.

단, 현재 맵 상태에서 모든 곳에 폭탄을 터뜨려보는 것은 시간초과가 발생할 수 있으므로, 약간 트리키하게 구현했다.

소스코드 보기

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

const int MAXN = 510;
int n, m, dp[51][MAXN];
string g[51];
set<iii> lis;
void input() {
	// ---- !!! INIT GLOBAL VARIABLES !!! ---- //
	cin >> n >> m;
	FOR(i, 0, n) cin >> g[i];
}

void eraseBomb(int y, int x) {
	for(int dy : {-1, 0, 1}) {
		for(int dx : {-1, 0, 1}) {
			int ny = y+dy, nx = x+dx;
			if(0 < ny && ny < n-1 && 0 < nx && nx < m-1) {
				auto it = lis.find({ dp[ny][nx],{ ny, nx } });
				if(it != lis.end()) {
					dp[ny][nx] = it->first + 1;
					lis.erase(it);
					lis.insert({ dp[ny][nx], {ny, nx} });
				}
			}
		}
	}
}

int solve() {
	lis.clear();
	memset(dp, 0, sizeof(dp));
	FOR(i, 1, n-1) {
		FOR(j, 1, m-1) {
			int cc = 0;
			for(int dy : { -1, 0, 1 }) {
				for(int dx : { -1, 0, 1 }) {
					int ny = i + dy, nx = j + dx;
					if(g[ny][nx] == '1') {
						++cc;
					}
				}
			}
			lis.insert({ -cc, { i, j } });
			dp[i][j] = -cc;
		}
	}
	int rem = 0;
	FOR(i, 0, n) FOR(j, 0, m) if(g[i][j] == '1') ++rem;
	vii ans;
	while(rem) {
		iii cur = *lis.begin();
		lis.erase(lis.begin());
		int cc = -cur.fi, cy = cur.se.fi, cx = cur.se.se;
		rem -= cc;
		ans.pb({ cy, cx });
		for(int dy : {-1, 0, 1}) {
			for(int dx : { -1, 0, 1}) {
				int y = cy+dy, x = cx+dx;
				if(g[y][x] == '1') {
					eraseBomb(y, x);
					g[y][x] = '0';
				}
			}
		}
	}
	cout << ans.size() << ENDL;
	FOR(i, 0, ans.size()) cout << ans[i].fi << ' ' << ans[i].se << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
#ifdef LOCAL_BOOKNU
	auto START_TIME = clock();
#endif
	int TTT; cin >> TTT;
	FOR(ttt, 0, TTT) cout << "Case #" << ttt+1 << ENDL,
		input(), solve();
#ifdef LOCAL_BOOKNU
	auto END_TIME = clock();
	cout << ENDL << END_TIME - START_TIME << "ms" << ENDL;
#endif
}

int main(void) {
#ifdef LOCAL_BOOKNU
// 	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

Read All

1/4