청정알고리즘

어떤 클래스의 인스턴스를 생성하는 데 사용하는 데이터와 코드가 여러 클래스에 퍼져 있다면, 그 생성 지식을 하나의 팩터리 클래스로 옮긴다.

동기

객체 생성을 위한 지식이 여러 클래스에 퍼져 있다면, 이를 '문어발 생성'이라고 이야기 한다. 하나의 클래스는 자신의 기능이 명확해야 하므로 문어발 생성이 존재한다는 것은 객체 생성과 상관없는 클래스가 객체 생성에 대한 책임을 지고 있다는 이야기가 된다. 특히 외부 설정값을 클래스별로 이리저리 전달하다가 생성 코드까지 전달할 경우 자주 일어나는데, 이런 경우에 Factory 패턴을 통해 객체 생성 로직과 외부 설정값 처리에 대한 로직을 캡슐화할수 있다. 이 방법으로 생성 로직이 변경되더라도 이리저리 쫓아다니며 코드를 고칠 필요없이 Factory 클래스만 수정하면 되기 때문에 편리하다.

Factory 패턴을 이용하면 하나의 Factory 인스턴스에 지속적으로 상태를 조정할 수 있으며, 하나의 인스턴스가 프로그램 내에서 계속 재사용될 수 있다. 경우에 따라서는 abstract class로 구현하여, 생성 옵션에 따라서 별개의 생성 클래스를 만들어 생성 로직의 복잡함을 줄일 수 있다.

절차

1. 주어진 클래스의 인스턴스를 생성하기 위해 다른 클래스에서 knowledge를 사용하는 부분을 찾는다. creation method를 사용하지 않는다면, 사용하도록 수정한다.
2. 팩터리로 사용할 클래스를 만든다. 이 때 팩터리 클래스의 이름은 생성할 클래스의 이름을 고려하여 정한다.
   ex) Pizza class의 인스턴스를 만드는 팩터리 -> PizzaFactory
3. Move Method 리팩터링을 이용해, 생성 메서드를 Factory 클래스로 옮긴다.
4. Factory의 인스턴스를 생성한 후, 생성할 클래스에서 Factory를 통해 인스턴스를 생성하도록 수정한다.
5. 주변 코드를 보면서, 무엇이든 Factory에 있는것이 나아보이는 것을 Factory로 전부 옮긴다. 아이디어의 기본은 Factory가 생성에 관한 가능한한 가장 많은 일을 하게 하는 것이다.
   
   
   

추가

다음과 같은 class를 보자.

public class Query...
    public void createQuery() throws QueryException...
        if (usingSDVersion52()){
            query = new QuerySD52();
        else
            query = new QuerySD51();

여기서 조건문 부분을 팩터리로 변경한다면 다음과 같이 변경할 것이다.

public class Query...
    public void createQuery() throws QueryException...
        query = queryFactory.createQuery();

QueryFactory가 코드를 깔끔하게 만든것으로 보인다. 하지만 이 경우에는 그냥 내부 구현을 다른 곳으로 옮긴 것이 불가하다. Factory의 도입으로 코드의 설계가 개선되거나 이곳저곳에서 사용되는 생성 로직을 한곳으로 모으거나, 직접 객체를 생성할 때는 불가능한 방법으로 Factory의 상태를 조정하는것이 아니라면 Factory를 사용하는 것은 괜히 설계만 복잡하게 만들게 될 뿐이다. 이런 경우에는 Factory를 사용하지 않은 편이 나으며, 원래 코드도 충분히 좋은 코드라고 할 수 있다.

만약 다른 곳에서도 비슷한 일이 발생하며 여러가지 문어발식 생성이 발생하게 된다면, 그 때 리팩터링해도 늦지 않다. 항상 리팩터링은 민첩하고 꾸준하지만 게으르게 해라.

어떤 클래스의 인스턴스를 생성할 때 그것이 제공하는 여러 생성자 중 어떤 것을 호출해야 할지 결정하기가 어렵다면, 인스턴스를 생성해 리턴하는 생성 메서드로 각 생성자를 대체하여 그 용도가 명확히 드러나도록 한다.

동기

C++이나 Java 계열의 언어에서는 생성자의 이름이 항상 클래스의 이름으로 고정이다. Python의n의 경우에는 __init__이 생성자의 역할을 대신한다. 특히 C++이나 Java 계열의 언어에서 프로그래머는 생성자가 여러종류일 경우 생성자 코드를 살펴본 후 어떤 생성자를 호출할 지를 정해야한다. 이는 코딩을 할 때 생산성의 저하로 이어지게 된다.

생성자의 시그니처만 보고 용도를 명확히 알기는 어렵다. 생성자가 많을수록 프로그래밍 시 잘못된 생성자를 호출하는 경우도 있다. 극단적인 경우 새로 만들 생성자의 시그니처가 기존 생성자와 같은 경우도 있을 수 있다. 불가능한 선언이 되는것이다.

Creation Method를 이용하여 Constructor를 대체한다면 이러한 문제를 해결할 수 있으며, Creation Method의 이름을 통해 그 역할 또한 명시적으로 전달할 수 있다. Python의 경우에는 class method를 이용하여 구현하면 좋을 것 같다.

절차

1. 리팩터링할 생성자를 하나 선택하여 이를 호출하는 코드를 확인한다. 이 부분에서 해당 호출부를 Extract Method 리팩터링을 진행한 후 이 메서드를 선언한 클래스로 Move Method 리팩터링을 진행한다.
2. 선택한 생성자를 사용하는 모든 곳에서 생성자 대신 새로 만든 메서드를 호출하도록 변경한다.
3. 만약 선택한 생성자가 다른 생성자를 호출하고 있다면, 해당 생성자 대신 호출되는 생성자를 사용하도록 변경한다.
4. 위의 과정을 반복하여 필요한 모든 생성자를 리팩터링한다.
5. 마지막으로 클래스의 생성자가 밖에서 사용되지 않는다면 이를 private으로 변경한다.
   
   
   

추가

추상 메서드가 많을 경우 Factory 클래스를 생성하여 생성하는 부분을 위임해도 괜찮다. 취향의 문제이다.

리팩터링이란?

리팩토링은 겉으로 보이는 동작을 바꾸지 않고, 이해하거나 수정하기 쉽게 소프트웨어의 구조를 변경하는 행위이다.
리팩터링을 할땐 반복을 없애거나, 복잡한 로직을 단순화하고, 큰 함수를 나누고, 변수명을 수정하는 등 다양한 행위를 포함한다.
안전한 리팩터링을 위해서는 테스트가 필수이다. 만약 내 코드가 겉으로 보이는 동작이 달라졌다면 이는 테스트를 통해 확인할 수 있다.
따라서 테스트를 하지 않는다면 리팩터링을 하는데에 매우 소극적으로 변하게 되고 큰 구조의 변경이나 로직을 단순화하는 등 실제 결과를 다르게 할 수도 있는 거대한 리팩터링을 하는데에 무리가 있다.

리팩터링은 다음과 같은 이유들로 진행한다고 저자는 설명한다.

• 새로운 코드를 더 쉽게 추가할 수 있도록 하기 위해
  코드를 새로 추가할 땐 두가지 방법중 하나를 택하게 된다. 기존 코드를 생각하지 않고, 무작정 프로그램을 작성하는 방법과, 새로운 기능이 예쁘게 들어맞도록 기존의 설계를 약간 수정하는 것이다. 전자의 방법은 '설계 부채'를 만들고, 이는 나중에 언젠간 리팩터링으로 갚아야 한다.
• 기존 코드를 잘 이해하고 발전적인 설계로 개선하기 위해
  가끔 스스로 짠 코드도 이해하기 힘든 경우가 있다. 이런 코드에 무작정 주석을 다는 것보단, 코드가 명확하지 않은 부분이 있다면 리팩터링으로 해결하는 것이 옳을 것이다. '냄새'를 덮는게 아니라, 냄새의 근원을 찾아 없애는 것이다. 이 과정을 통해 코드의 유지보수와 확장이 매우 쉬워지게 된다.
• 덜 짜증나는 코드를 만들기 위해
  일단 리팩터링을 하지 않은 코드들을 보면 짜증이 나기때문에 이를 덜 짜증나게 바꾸는 것으로 프로그래밍을 좀 더 즐겁게 만들수 있다.
  
  
  

사람이 읽기 쉬운 코드

다음과 같은 말이 있다.

컴퓨터가 이해하는 코드는 어느 바보나 다 짤 수 있다. 훌륭한 프로그래머는 사람이 이해할 수 있는 코드를 짠다.

작은 단계

항상 리팩터링을 할때 작은 단계로 점차 나아가는 것이 중요하다. 지나치게 큰 단계를 취하고 테스트를 통과시키기 위해 많은 고생을 하는 경우가 많다. 테스트는 나침반이다. 올바른 길에서 벗어나지 않도록 도와준다. 조금씩 조금씩 한걸음 한걸음 떼는 습관을 들이자.

설계 부채

인간은 완벽하지 않다. 언제나 완벽한 설계를 한다는 것은 사실상 불가능하고, 우리는 그렇기 때문에 '설계 부채'라는 것을 지게 된다. 제대로 되지 못한 설계를 리팩터링을 통해 갚지 않는다면, 이는 눈덩이처럼 불어나게 되고, 손쓸수 없는 지경에 까지 이르게 된다.

소프트웨어 패턴이 왜 중요할까?

모든 프로그래머들은 처음에는 시행착오에 빠진다.
어떤 문제든 처음 보고 척척해결하는 프로그래머는 거의 없다.
다만, 프로그래머계의 격언이 있듯이 'Google은 항상 답을 알고 있다.'
대부분의 신입 프로그래머들이 겪는 문제점들은 이미 선배 프로그래머들이 경험해본 경우가 대부분이고, 많은 경우 그 해결방안 또한 stackoverflow와 같은 기타 커뮤니티에 정리되어 있는 경우가 많다.

소프트웨어 패턴 또한 이런 부분에서 시작되었다고 할 수 있다.
코드의 동작 여부와 별개로 어떤 문제점이 존재할 때,(책에서는 이러한 코드를 '냄새나는 코드'로 이야기하였다.) 이를 해결하기 위한 좋은 방법을 선배프로그래머나 연구자들이 '패턴'이라는 형태로 그 답을 정해놓은 것이다.
그렇기 때문에, 소프트웨어 패턴이 대단한 점은 그로부터 설계에 대한 여러 유용한 아이디어를 얻을 수 있다는 데에 있는 것이다.

이런 생각으로 처음으로 여러 종류의 패턴을 배우면 훌륭한 프로그래머가 될 수 있다는 착각에 빠진다고 저자는 언급했다. 물론 패턴을 사용하면 견고하고 확장성 있는 시스템을 만드는 데에 큰 도움이 되지만, 때로는 '패턴 만능주의'에 빠져 일을 지나치게 복잡하게 만들기 때문이다. 따라서 저자는 패턴을 너무 일찍 코드에 도입하는 대신 꼭 필요한 시기에 리팩터링을 통해 도입하는 방법을 추천한다.

과도한 설계

항상 일을 할때도 계획만 번지르르하게 세우는 종류의 사람들이 있는데, 프로그래머 중에도 그런 프로그래머들이 있다.
물론 계획을 세우는 것은 중요한 일이지만, 일부 프로그래머들은 현재 시스템에 대한 미래의 요구사항을 모두 알고 있다고 착각한다.
그런 이유로 미래에 닥칠 설계의 변화에 대비하여 현재 설계를 융통성 있고 정교하게 해두는 것이다.
그럴싸하게 들리지만 저자는 이러한 설계를 비판한다.
결국 설계의 변화가 없다면 필요 이상의 귀중한 시간과 비용을 낭비한 꼴이 되기 때문이다.
과도한 설계에 시간을 쏟는 대신, 새로 필요한 기능을 추가하거나 결함을 고치는데에 시간을 쏟는 쪽이 훨씬 합리적인 것이다.

더 심각한 문제는 저런 코드들은 없어지지도 않는다는 것이다.
혹시 나중에 사용할 것을 대비하여, 혹은 귀찮아서 등, 여러가지 이유로 이러한 과도한 설계에 해당하는 코드들이 쌓이게 된다.
그렇게 되면 작업하는 사람들은 단순한 코드를 보는 대신 훨씬 복잡한 코드를 기반으로 작업해야하므로 불편해 지는 것이다.
생산력의 감소로 이어지지만, 이것이 과도한 설계 때문이라는 것은 알아채기 힘들다.
그렇기 때문에 저자는 모든 것을 패턴으로 해결하려는 생각을 버리고, 작고 단순하고 이해하기 쉬운 코드를 작성하는데 주의를 기울여야 한다고 주장한다.

미진한 설계

미진한 설계가 과도한 설계에 비해 자주 발생하게 된다. 저자는 다음과 같은 이유들로 발생한다고 설명한다.

• 시간이 없을때
  • 절대적인 시간이 주어지지 않을 때
  • 기존 시스템에 새 기능을 추가할 때
  • 참여 중인 프로젝트가 많을 때
• 훌륭한 설계를 모를때
  

지속적으로 미진한 설계가 쌓이면 처음엔 빠르게 진행되다가 점차 느려지는 양상이 된다.
엉망인 코드로 초기 버전을 일단 작성한후, 이 엉망인 코드 때문에 생산성도 떨어지고, 결국엔 완전히 재작성하게 되는 경우가 허다하다.

TDD와 리팩터링

TDD와 리팩터링은 XP(extreme programming)의 핵심 실행지침중 하나라고 한다. 프로그래밍 과정을 다음과 같은 interactive 과정으로 변경하여, 코드를 효율적으로 작성하고 외부 변화에 민감할 수 있도록 만든 것이다.

• 질문. 테스트를 작성함으로써 시스템에 질문한다.
  바로 다음 작성할 코드가 해야 할 일을 예상하고 이것을 나타내는 테스트를 작성한다. 아직 코드를 작성하기 전이기 때문에 테스트는 당연히 실패한다.
• 대답. 테스트를 통과하는 코드를 작성해 질문에 대답한다.
  테스트를 통과하도록 임시방편으로라도 프로그램을 작성한다. 이 때는 코드 반복, 설계같은것을 고민할 필요 없이 일단 돌아가게 작성한다.
• 정제. 아이디어를 통합하고, 불필요한 것은 제거하고, 모호한 것은 명확히 해서 대답을 정제한다.
  테스트가 통과한다면, 더 좋은 설계를 맘편하게 테스트 할수 있다. 코드의 반복제거, 명확하고 단순한 코드, 좋은 설계는 이 단계에서 고려한다.
• 반복. 다음 질문을 물어 대화를 반복한다.
  완성될때까지 계속 반복한다. XP와 같은 환경에서는 사용자가 계속 피드백을 주는 경우가 많기 때문에, 이 피드백을 지속적으로 반영한다고 생각해도 좋을 것이다.
  

TDD는 얼핏 보기에는 비효율적이고 무계획한 소프트웨어 개발 방법으로 보일 수 있지만, 실제로는 이와 정 반대로, 이는 생산성을 극대화하는 간결하고도 반복적이며 통제된 개발방식이다. 이러한 방식은 두려움 없이 리팩터링을 할수 있게 해주고, 이를 통해 더 단순하고 훌륭한 코드를 생산하는 데 도움을 준다. 또한, 단순한 과정의 반복으로 스트레스 없이 프로그램을 작성할 수 있게 된다.

발전적 설계

저자는 더 나은 소프트웨어 엔지니어가 되기 위해서, 훌륭한 소프트웨어 설계를 공부하는 것보다 그것이 발전해온 과정을 공부하는 것이 더 가치있다고 말한다. 그 발전 과정속에 선배 프로그래머들의 지혜가 담겨있다고 얘기한다. 왜 그런식으로 발전했는지를 이해하지 못한다면, 다른 프로젝트에서 선배 프로그래머들이 겪었던 과오를 반복해서 경험할 가능성이 커진다. 설계를 발전시켜 나가면, 과도하거나 미진한 설계를 줄일 수 있고, 그 핵심에 있는게 바로 TDD와 리팩터링이다. 패턴을 이용한 리팩터링을 습득하게 된다면 훌륭한 설계를 발전시킬수 있는 장비를 가진 것과 다름이 없는 것이다.

본 게시판은 Joshua Kerievsky의 'Refactoring to Patterns'의 번역서인 '패턴을 위한 리팩토링'을 공부하며 스스로 배운점들을 요약 정리하는 게시판입니다.

#define MAX 30000
#define QSIZE 10
using namespace std;

class Status
{
private:
	int num[4], ind, mod[4][4], high;
	int f(int x)
	{
		return 81*81*81*num[x] + 81*81*num[(x+1)&3] + 81*num[(x+2)&3] + num[(x+3)&3];
	}
public:
	Status(){}
	Status(int m[4][4])
	{	
		high = -1;
		for(int i=0;i<4;i++) for(int j=0;j<4;j++)
		{
			mod[i][j]=m[i][j];
			if(mod[i][j]>high) high=mod[i][j];
		}
		num[0] = 27*m[0][0]+9*m[0][1]+3*m[1][0]+m[1][1];
		num[1] = 27*m[0][3]+9*m[1][3]+3*m[0][2]+m[1][2];
		num[2] = 27*m[3][3]+9*m[3][2]+3*m[2][3]+m[2][2];
		num[3] = 27*m[3][0]+9*m[2][0]+3*m[3][1]+m[2][1];
		
		ind=0;
		for(int i=1;i<4;i++)
		{
			int find = f(ind), fi = f(i);
			if(find>fi) ind=i;
		}
	}
	int get(int x){ return num[(ind+x)&3]; }
	bool operator==(Status& x)
	{
		for(int i=0;i<4;i++)
		{
			if(get(i)!=x.get(i)) return false;
		}
		return true;
	}
	bool operator<(Status& x)
	{
		for(int i=0;i<4;i++)
		{
			if(get(i)!=x.get(i)) return get(i)<x.get(i);
		}
		return false;
	}

	int getHigh(){return high;}
	Status flipComplement()
	{
		int t[4][4];
		for(int i=0;i<4;i++) for(int j=0;j<4;j++) t[i][j] = high - mod[i][3-j];
		return Status(t);
	}
};
struct Block
{
	Status st;
	int base;
	Block(){}
	Block(int _d[4][4], int _b)
	{
		st = Status(_d);
		base = _b;
	}
	bool operator<(Block& x)
	{
		if(st==x.st)return base>x.base;
		return st<x.st;
	}
};
class Queue{
private:
	int data[QSIZE];
	int f,b,s;
public:
	Queue()
	{
		f=b=s=0;
	}
	void push(int x)
	{
		data[b]=x;
		++b;
		++s;
		if(b==QSIZE) b=0;
	}	
	void pop()
	{
		++f;
		--s;
		if(f==QSIZE) f=0;
	}
	int front(){return data[f];}
	int size(){return s;}
};

class Data
{
public:
	Status status;
	Queue q;
	Data(){}
	Data(Status& _st)
	{
		status=_st;
		q=Queue();
	}
};
void swap(Block& x,Block& y)
{
	Block t=x;
	x=y;
	y=t;
}

void quickSort(int l,int r, Block* b)
{
	if(l+1>=r)return;
	
	int pivot = l;
	int j=pivot;
	
	for(int i=l+1;i<r;i++)
	{
		if(!(b[i]<b[pivot])) continue;
		j++;
		swap(b[i], b[j]);
	}

	swap(b[l], b[j]);

	pivot=j;
	quickSort(l, pivot, b);
	quickSort(pivot+1,r, b);
}

int binary_search(int l, int r, Status& v, Data* d)
{
	while(l<r)
	{
		int mid = (l+r)>>1;
		if(d[mid].status==v)return mid;
		
		if(d[mid].status<v) l=mid+1;
		else r=mid;
	}
	return -1;
}

Block b[MAX];
Data d[MAX];

int normalize(int module[4][4])
{
    int base=module[0][0];
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(base>module[i][j])
                base = module[i][j];
    
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            module[i][j] -= base;
    
    return base;
}

int makeBlock(int module[][4][4]) {
	for(int i=0;i<MAX;i++)
	{
		int base = normalize(module[i]);
		b[i] = Block(module[i], base);
	}
	quickSort(0, MAX, b);

	int dnum=0;
	for(int i=0;i<MAX;i++)
	{
		d[dnum]=Data(b[i].st);
		d[dnum].q.push(b[i].base);
		while(b[i].st == b[i+1].st)
		{
			d[dnum].q.push(b[i+1].base);
			++i;
		}
		++dnum;
	}

	int ans=0;
	for(int i=0;i<dnum;i++)
	{	
		if(d[i].q.size()==0)continue;
		Status target = d[i].status.flipComplement();
		int ind = binary_search(0, dnum, target, d);
		if(ind==-1) continue;

		if(i==ind)
		{
			while(d[i].q.size()>1)
			{
				ans += d[i].q.front();
				d[i].q.pop();
				ans += d[i].q.front();
				d[i].q.pop();
				ans += d[i].status.getHigh();
			}
			continue;
		}
		while(d[i].q.size()>0 && d[ind].q.size()>0)
		{
			ans += d[i].q.front() + d[ind].q.front() + d[i].status.getHigh();
			d[i].q.pop();
			d[ind].q.pop();
		}
	}
	return ans;
}

문제

https://www.acmicpc.net/problem/9240

풀이

전형적인 Convex Hull 문제이다.

아래 풀이에서는 Graham Scan이라고 하는 $O(nlogn)$의 알고리즘을 사용한다.

Convex Hull을 구한 후, Convex Hull 상에서 가장 먼 두 점을 찾는데, 원래는 Rotating Calipers 라는 알고리즘을 사용하여 $O(n)$에 구해야 한다.

하지만 필자는 한 번도 구현해본 적이 없고, 실제 이 문제에서는 좌표의 범위가 작고, 정수점만 입력으로 들어오기때문에 Convex Hull의 점의 수가 매우 작고, 실제로 1000*4=4000개보다 작음은 약간의 논증을 통해 보일 수 있다.

따라서 Convex Hull 내부의 모든 점을 비교해도 시간안에 구할 수 있다.

정해는 rotating calipers라는 알고리즘을 이용해서 가장 먼 두 점을 구하는데 $O(|convex hull|)$이면 충분하다.

Time Complexity : $O(nlogn + |convex hull|^2)$

코드

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 100002
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pos;
 
double dist(pos p1, pos p2)
{
	double dissq = (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second);
	return sqrt(dissq);
}

int n;

vector<pos> p;

ll ccw(pos p1, pos p2, pos p3)
{
	return (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
}

bool cmp(pos p1, pos p2)
{
	ll c = ccw(p[0], p1, p2);
	if (c > 0) return 1;
	if (c < 0) return 0;
	else
    {
		if (dist(p[0], p1) < dist(p[0], p2)) return 1;
		else return 0;
	}
}

int main()
{
	cin>>n;

	p.resize(n);
	for (int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
	
	sort(p.begin(),p.end());
	sort(p.begin()+1,p.end(),cmp);
    
	vector<pos> cvxh;
	cvxh.push_back(p[0]);
	cvxh.push_back(p[1]);

	for (int i=2;i<n;i++)
	{
		while (cvxh.size() >= 2 && ccw(cvxh[cvxh.size()-2],cvxh.back(),p[i])<=0)
			cvxh.pop_back();
		cvxh.push_back(p[i]);
	}
    
	double ans=-1;
	int len=cvxh.size();
	for (int i=0;i<len;i++) for (int j=i+1;j<len;j++)
		ans=max(ans, dist(cvxh[i], cvxh[j]));

    printf("%.10f", ans);
}

문제

https://www.acmicpc.net/problem/5696

풀이

$x,y$가 input으로 들어올때, $f(x)=$(1부터 $x$까지 적었을 때, 나타나는 0~9의 숫자의 배열)이라고 정의하자.

그럼 구하고자 하는 정답은 $f(y)-f(x-1)$이 된다.

그럼 $f(x)$는 어떻게 구할까?

자릿수별로 각 숫자의 개수를 계산한다는 아이디어를 기본적으로 생각해보자.

즉, 1의 개수를 셀때, 1의 자리에 오는 1, 10의 자리에 오는 1, 100의 자리에 오는 1,....들을 모두 세서 더해준다면 구하고자하는 전체 1의 개수를 구할 수 있을 것이다.

결국 위의 질문은 1~x까지의 숫자중 $10^t$자리가 $a$인 숫자가 모두 몇개인지를 각 $t$에 대해 모두 풀어서 더해주면 된다.

이는 다음과 같이 경우를 나누어 풀수 있다.

case 1) $a$가 $x$의 $10^t$자리 숫자보다 작을 경우

예를 들어서 $x=12345, a=1, 10^t=100$인 경우를 보자.

그러면 ??1?? 꼴의 숫자가 몇 개인지를 세는 것인데, 이는 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류) * 100이 된다.

또한 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류)는 위의 예시에서는 0부터 12까지이므로, 총 13개가 가능하다.

즉 1??, 11??, 21??, 31??, ... , 121??의 경우가 가능하다는 뜻이다.

수식으로 나타내면 $(x/10^{t+1}+1)\times 10^t$가지 경우임을 알 수 있다.

case 2) $a$가 $x$의 $10^t$자리 숫자와 같을 경우

$x=12345, a=3, 10^t=100$을 예로 들어보자.

이 경우에는 3??, 13??, ..., 113??까지는 자유롭게 가능하고, 123??의 경우에는 0~45까지 총 46개만 가능하다.

같은 방식으로 수식으로 나타내면 $(x/10^{t+1})\times 10^t+(x%10^t)+1$ 가지 경우가 있음을 알 수 있다.

case 3) $a$가 $x$의 $10^t$자리 숫자보다 클 경우

비슷한 방식으로  $x=12345, a=5, 10^t=100$을 예로 들어보자.

이 경우에는 5??, 15??, ..., 115??까지만 가능하므로 case 1)의 경우보자 $10^t$개 적게 된다.

따라서 이 경우는 $(x/10^{t+1})\times 10^t$ 가지이다.

따라서 이를 모두 각각 더해주면 된다.

주의할 점은 맨 앞자리에 0이 올수는 없으므로 0은 각 경우에서 $10^t$개만큼 빼주어야 한다는 점이다.

즉 10?? 꼴의 숫자는 있지만, 0?? 꼴의 숫자는 존재하지 않으므로, 이 경우를 빼주는 것이다.

위와 같은 방식으로 0~9까지 등장수를 모두 더해주면 $f(x)$를 구할 수 있다.

Time Complexity : $O(logx+logy)$

코드

#include<iostream>
#include<vector>
using namespace std;

vector<int> f(int t)
{
	vector<int> ret(10);
	for(int i=1;i<=t;i*=10)
	{
		for(int j=0;j<10;j++)
		{
			if( j<(t/i)%10) ret[j] += (t/(i*10)+1)*i;
			else if( j==(t/i)%10 ) ret[j] += (t/(i*10))*i+(t%i)+1;
			else ret[j] += (t/(i*10))*i;
		}
		ret[0]-=i;
	}
	return ret;
}
int main() {
	while(1)
	{
		int x,y;
		cin>>x>>y;
		if(x==0 && y==0)break;
		vector<int> a1 = f(y);
		vector<int> a2 = f(x-1);
		for(int i=0;i<10;i++)
		{
			cout<<a1[i]-a2[i]<<" ";
		}
		cout<<"\n";
	}
}

문제

https://www.acmicpc.net/problem/3392

풀이

단순히 생각하면 30000 * 30000 배열을 만들어 사각형이 입력으로 들어오면 해당 사각형의 영역에 1씩 더해준다.

그 후, 1이상의 값을 가지는 모든 칸의 값을 세주면 된다.

하지만 이와 같은 방법으로는 시간도 많이 소모하고, 공간도 많이 잡는다.

따라서 line sweeping 알고리즘을 사용하여 현재 line과 닿아있는 부분의 30000개 배열만 생각한다.

세로 선을 왼쪽 끝부터 오른쪽 끝까지 sweeping한다고 생각하자.

sweeping하면서 만나는 면적을 모두 더하면 구하고자 하는 정답이 된다.

sweeping 하면서 발생하는 event의 종류가 두 가지인데, 각각에 대해서 처리해 주면 된다.

case 1) 새로운 사각형의 등장

이 때는 현재 직사각형의 왼쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 증가시켜준다.

case 2) 사각형의 퇴장

이 때는 현재 직사각형의 오른쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 감소시켜준다.

위와 같은 과정을 거치면서 현재 line에 있던 1이상의 칸의 수를 모두 더해주면 된다.

하지만 이렇게 되면 $O(nC)$의 시간복잡도로 시간안에 통과할 수 없다.

따라서 전체 구간의 합을 segment tree를 이용하여 관리해주면 된다.

이 때, 등장하는 쿼리는 구간에 1을 더해주는 query이므로, lazy propagation의 아이디어를 사용한다.

lazy propagation처럼 게으르게 값을 관리하는데, 현재 구간이 전파될 예정이라면, 하위 노드의 값과 관계 없이 이 구간은 모두 값을 구하는데 사용되게 된다.

root 노드로 부터 내려가다가 처음으로 전파될 예정인 노드를 만나면 바로 그 하위 구간의 길이를 return해주면 되기 때문에, 전파과정은 진행하지 않아도 무방하다.

이러한 방법을 이용하여 segment tree를 업데이트 해주면, event마다 log 시간복잡도에 원하는 작업을 완료할 수 있다.

Time Complexity : $O(N(logN+logC))$

코드

#include<iostream>
#include<algorithm>
#define N 10005
#define C 40000
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

struct ev
{
	int x, y1, y2, z;
	bool operator<(const ev & t)
	{
		return x<t.x;
	}
}evt[N<<1];

ev make_ev(int X, int Y1, int Y2, int Z)
{
	ev r;
	r.x=X;
	r.y1=Y1;
	r.y2=Y2;
	r.z=Z;
	return r;
}
struct segtree
{
	int val;
	int num;
} seg[C<<2];

int n,pr,ans;

void update(int l, int r, int v, int t, int x, int y)
{
	if(y<l || r<x) return;
	if(l<=x && y<=r) seg[t].num+=v;
	else
	{
		int mid=(x+y)>>1;
		update(l,r,v,lc(t),x,mid);
		update(l,r,v,rc(t),mid+1,y);
	}
	if(seg[t].num) seg[t].val=y-x+1;
	else seg[t].val=(x==y?0:seg[lc(t)].val+seg[rc(t)].val);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;

		evt[i]=make_ev(a,b,d-1,1);
		evt[i+n]=make_ev(c,b,d-1,-1);
	}
	sort(evt,evt+2*n);
	for(int i=0;i<2*n;i++)
	{
		if(i>0) ans+=(evt[i].x-pr)*seg[1].val;
		update(evt[i].y1, evt[i].y2, evt[i].z,1,0,C);
		pr=evt[i].x;
	}
	cout<<ans;
}

문제

https://www.acmicpc.net/problem/16000

풀이

우선 flood fill을 이용하여 각 섬별로 넘버링을 한다.

같은 방법으로 0,0 구석의 물에서부터도 flood fill을 이용하여 안전한 바다를 전부 구할것이다.

flood fill을 할때, 4방향, 즉 상하좌우의 경우 인접한 바다를 모두 queue에 추가한다.

또한 추가적으로 대각선방향 4방향에서도 안전한 바다로 전파될 수 있는 바다들이 존재한다.

만약

#.

.#

모양처럼 대각선으로만 뚫려있고 상하로 막혀있지만, 왼쪽의 섬과 오른쪽의 섬이 서로 다른 섬이라면 사냥꾼은 두 섬에 동시에 존재할 수 없으므로, 둘 중 사냥꾼이 없는 쪽으로 빠져나올 수 있다.

따라서 대각선으로만 뚫려있어도 위의 조건에 해당한다면 queue에 추가해준다.

이 과정을 진행하면서 안전한 바다와 인접한 땅들을 모두 체크해주어 'O'로 바꾸고, 나머지를 'X'로 바꾸면 문제를 해결할 수 있다.

Time Complexity : $O(nm)$

코드

#include<iostream>
#include<string>
#include<queue>
#define N 2004

using namespace std;
typedef pair<int,int> pi;
string s[N];
int mp[N][N],n,m,color;
pi flag[4]={pi(1,0),pi(0,1),pi(-1,0),pi(0,-1)};
vector<char> ans;

pi operator+(const pi &x1, const pi &x2)
{
	return make_pair(x1.first+x2.first, x1.second+x2.second);
}

bool cango(pi t)
{
	return t.first>=0 && t.first<n && t.second>=0 && t.second<m;
}

void floodFillLand(pi st, int v)
{
	mp[st.first][st.second]=v;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			vector<int> V;

			if(!cango(next) || mp[next.first][next.second]!=0) continue;

			if(s[next.first][next.second]=='#')
			{
				mp[next.first][next.second] = v;
				Q.push(next);
			}
		}
	}
}

void floodFillWater(pi st)
{
	mp[st.first][st.second]=-1;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			if(!cango(next)) continue;
			if(mp[next.first][next.second]>0)
			{
				ans[mp[next.first][next.second]]='O';
				continue;
			}

			if(mp[next.first][next.second]==0 && s[next.first][next.second]=='.')
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}

		for(int k=0;k<4;k++)
		{
			pi next= f+flag[k]+flag[(k+1)&3];
			pi c1 = f+flag[k];
			pi c2 = f+flag[(k+1)&3];
			if(!cango(next) || s[next.first][next.second]=='#') continue;

			if(mp[next.first][next.second]!=-1 && mp[c1.first][c1.second]>0
				&& mp[c2.first][c2.second]>0 && mp[c1.first][c1.second]!=mp[c2.first][c2.second])
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}
	}
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i];

	color=0;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(mp[i][j] || s[i][j]=='.') continue;
		floodFillLand(make_pair(i,j),++color);
	}

	ans.resize(color+1,'X');
	floodFillWater(make_pair(0,0));

	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(s[i][j]=='.')continue;
		s[i][j] = ans[mp[i][j]];
	}

	for(int i=0;i<n;i++) cout<<s[i]<<"\n";
}