DailyBread

조합은 수를 세는 것에 관한 수학

기초적인 셈

곱의 법칙

 집합 A의 원소가 |A|개, 집합 B의 원소가 |B|개일때 , A와 B에서 하나씩 뽑아서 조합하는 경우의 수가 |A|X|B|

합의 법칙

 집합 A의 원소가 |A|개, B의 원소가 |B|개일때, A또는 B에서 하나를 뽑는 경우의 수는 |A|+|B|

합집합의 원소의 개수 

  두 집합이 겹치는 부분이 있는 경우에 하나를 뽑는 경우의 수는 |AUB| = |A|+|B|-|A∩B|

  집합 세 개의 합집합 원소의 갯수를 구할때는 |AUBUC| = |A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|

중복해서 세를 것은 조합론에서 골치 아픈 부분

다른 방법으로는 bijection을구 구하는 방법, 한 집합의 원소와 다른 집합의 원소 사이에 일대일 대응이 되는 경우, 한 집 합의 원소 개수를 세면 자동으로 달느 집합의 원소의 갯수를 셀 수 있음

기본적인 조합론

순열 (Permutation)

모든 항목이 정확하게 한번씩만 등장하는 경우 n개의 항목을 배열하는 방법

세개의 항목을 배열하며 3!=6 으로 123, 132, 213, 231, 312, 321 이지만 n=10이면 10! = 3,628,800 이기에 완전 검색에 한계에 다다른다.

부분집합

n개의 가능한 항목 중에서 임의의 원소를 뽑아낸 것을 부분 집합 (subset)이라고 한다.

 n개의 원소가 있으면 부분 집합의 개수는 2^n개가 된다. 항목이 세 개 있으면 2^3=8로 각각 1, 2, 3, 12, 13, 23, 123, 공집합이 된다. 공집합도 부분집합임에 주의하자. n=20이면 2^20 = 1,048,576이므로 완전 검색에 한계에 다다른다

문자열

중복을 허용하여 항목을 늘어놓는 것을 문자열(string, 중복 순열)이라고 한다.

n개의 항목중에 r개의 항모을 중복하여 뽑는다면 m^n개의 서로 다른 시퀀스를 만들 수 있다.

123을 가지고 길이가 3인 문자열을 만들면 27개의 문자열을 만들 수 있으며, 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 321, 322, 331, 333이다.

길이가 n인 이진 문자열(2개의 항목으로 만드는 문자열) n개의 원소를 가진 집합의 부분집합 갯수와 같다.

(왜 그럴까???)

참고 : Programming Challenges : 알고리즘 트레이닝 북

Memorize following code and logic !!

DFS example for grouping :

#include <iostream>

using namespace std;

int a[104][104];
bool visited[104][104];

int M=0,N=0;
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};

int dfs(int x, int y){
	int nx,ny;
	cout << y << " : " << x << '\n';

	visited[x][y] = 1;
	
	for (int i=0;i<4;i++){
		nx = x+dx[i];
		ny = y+dy[i];
		if ( nx<0 || ny<0 || nx>=N || ny >=M ) continue;
		
		if ( a[nx][ny]==1 && visited[nx][ny]!=1){
			dfs(nx,ny);
		}
	}
	
}

int main(){

	int cnt=0;
	
    cin.tie(NULL);
    cout.tie(NULL);

	cin >> M >> N;
	
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			cin >> a[i][j] ;
		}
	}
	
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			if ( a[i][j]==1 && visited[i][j]!=1){
				cnt++;
				dfs(i,j);
			}
		}
	}
	cout << cnt << "\n";
	
	return 0;
}

BFS example for shorted path :

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

queue< pair<int,int> > q;
int a[104][104];
int visited[104][104];
int N,M;

int dx[4] = { 0, 1, 0, -1};
int dy[4] = { 1, 0,-1, 0};

void bfs(int sx, int sy){
	int nx,ny;
	int x,y;
	
	visited[sx][sy] = 1;
	q.push({sx,sy});
		
	while (q.size()){
		tie(x,y) = q.front();
		q.pop();
		
		for (int i=0;i<4;i++){
			nx = x + dx[i];
			ny = y + dy[i];
			
			if ( nx<0 || ny<0 || nx>=N || ny>=M ) continue;
			
			if ( a[nx][ny]==1 && visited[nx][ny]==0){
				visited[nx][ny] = visited[x][y]+1;
				q.push({nx,ny});
			}
		}
	}
	
	return;
}

int main(){

	int sx,sy;
	int tx,ty;
	
	cin >> N >> M;
	cin >> sy >> sx;
	cin >> ty >> tx;
	
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			cin >> a[i][j];
		}
	}
	
	bfs(sx,sy);
	
	cout << visited[tx][ty] << "\n";
	
	for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
        	cout << visited[i][j] << ' '; 
        }
        cout << '\n';
    } 

	return 0;
}

Point 1 :

From quiz, BFS for shorted path ?

Point 2 : To get the 1 or 0, cin ? or scanf ?

4 6
101111
101010
101011
111011

Solution : Memorize the BFS pattern

//shorted path
//DFS ? 
//BFS ? > BFS
#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int N, M;
int a[104][104];
int d[104][104];

queue< pair<int,int> > q;

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void makeBFS(int sx, int sy)
{
	int x,y;
	int nx,ny;
	
	d[sx][sy] = 1;
	q.push({sx,sy});
	
	while (q.size())  // remember
	{
		tie(x,y) = q.front();
		q.pop();
		
		for (int i=0;i<4;i++)
		{
			
			nx = x + dx[i];
			ny = y + dy[i];
			
			if (nx<0 || ny<0 || nx > N || ny > M ) continue;
			if ( a[nx][ny]==1 && d[nx][ny]==0){
				d[nx][ny] = d[x][y]+1;
				q.push({nx,ny});
			}
		}	
	}
	
	return ;
}

int main()
{
	cin >> N >> M;
	
	for (int i=0;i<N;i++)
	{
		for (int j=0;j<M;j++)
		{
			scanf("%1d",&a[i][j]);	// remember
		}
	}

	makeBFS(0,0);
	
	cout << d[N-1][M-1] << "\n";
	
	return 0;
}

어떻게 하면 코드 작성자가 사용자에게 더 편의를 제공할 것인가?

C에서는 structure의 멤버들에 대한 정보/사용법을 사용자가 모두 알아야만 한다.

#include <stdio.h>

//code writer
typedef struct USERDATA
{
	int nAge;
	char szName[32];
	void(*Print)(struct USERDATA *);	//step 3 improvement
} USERDATA;
 
void PrintData(USERDATA *pUser)			//step 2 improvement
{
	printf("%d, %s\n", pUser->nAge, pUser->szName);
}

// code user
int main(void)
{
	USERDATA user = { 20, "Peter", PrintData };
	//printf("%d, %s\n", user.nAge, user.szName);		//step 1 C style
	//PrintData(&user);					//step 2 improvement
	user.Print(&user);					//step 3 improvement
    
	return 0;
}

From step 3, it seems the function is working as structure's member in code user point of view.

But it looks redundant which is using 'user' stucture's address agin from Print member function.

// code user
int main(void)
{
	USERDATA user = { 20, "Peter", PrintData };
    //printf("%d, %s\n", user.nAge, user.szName);	//step 1 C style
    //PrintData(&user);					//step 2 improvement
    //user.Print(&user);				//step 3 improvement
    user.Print();					//step 4 improvement
    
	return 0;
}

In C++, it's decided to hide &user parameter. it's related with 'this' pointer.

#include "stdafx.h"
#include <iostream>
using namespace std;

// code writer
class CTest
{
public :
	CTest() {}
    
	int m_nData1 = 10;
	int m_nData2 = 20;
    
	void PrintData(void)
	{
		cout << m_nData1 << endl;
		cout << m_nData2 << endl;
	}
};

// user code
int _tmain(int argc, _TCHAR* argv[])
{
	CTest t;
	t.PrintData();

	return 0;
}

2.4.1 Namespace

C++가 지원하는 각종 요소들(변수, 함수, 클래스 등)을 한 범주로 묶어주기 위한 문법

소속이나 구역이라는 개념

#include "stdafx.h"
#include <iostream>

namespace TEST
{
	int g_nData = 100;
    
	void TestFunc(void)
	{
		std::cout << "TEST::TestFunc()" << std::endl;
	}
}
 
// _tmain은 Global namespace 소속
int _tmain(int argc, _TCHAR* argv[])
{
	TEST::TestFunc();
	// cout은 std 네임스페이스 소속
	std::cout << TEST::g_nData << std::endl;
    
	return 0;
}

2.4.2 Using

네임스페이스를 임의로 생략

#include "stdafx.h"
#include <iostream>

// declare std namespace with 'using' keyword
using namespace std;

namespace TEST
{
	int g_nData = 100;
    
	void TestFunc(void)
	{
		cout << "TEST::TestFunc()" << endl;
	}
}

// declare TEST namespace with 'using' keyword
using namespace TEST;

int _tmain(int argc, _TCHAR* argv[])
{
	TestFunc();
	cout << g_nData << endl;
    
	return 0;
}

2.4.3 nested Namespace

네임스페이스 안에 또 다른 네임스페이스가 속할 수 있음

#include "stdafx.h"
#include <iostream>

using namespace std;

namespace TEST
{
	int g_nData = 100;
    namespace DEV
    {
    	int g_nData = 200;
        namespace WIN
		{
        	int g_nData = 300;
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	cout << TEST::g_nData << endl;
    cout << TEST::DEV::g_nData << endl;
    cout << TEST::DEV:WIN::g_nData << endl;
    
    return 0;
}

2.4.4 Namespace의 다중정의

#include "stdafx.h"
#include <iostream>

using namespace std;

//global
void TestFunc(void) { cout << "::TestFunc()" << endl;

namespace TEST
{
	void TestFunc(void){
    	cout << "TEST:TestFunc()" << endl;
	}
}

namespace MYDATA
{
	void TestFunc(void){
    	cout << "MYDATA::TestFunc()" << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{

	TestFunc();	//implicitly global
    ::TestFunc();	//explicitly global
    TEST::TestFunc();
    MYDATA::TestFunc();
    
    return 0;
}

첫번째 TestFunc()은 별도의 Namespace를 지정하지 않았는데, _tmain()함수의 namespace가 전역이기 때문이다.

int TestFunc(int);
int Data::TestFunc(int);
int CMyData::TestFunc(int);
int CMyData::TestFunc(int) const;

1번은 소속이 없음, 2~3번은 속해 있는 namespace나 class가 존재함, 4번은 CMyData라는 클래스의 상수형 Method임

2.5.4 using 선언과 전역 변수

#include "stdafx.h"
#include <iostream>

using namespace std;

namespace TEST
{
	int nData = 200;
}

using namespace TEST;

int _tmain(int argc, _TCHAR* argv[])
{
	cout << nData << endl;
    
    return 0;
}

위의 예제에서 컴파일 에러가 발생함. nData가 전역 네임스페이스일 수도 TEST 네인스페이스일수도 있음

::nData라고 범위 식별자를 기술하거나, TEST::nData라고 정확하게 네임스페이스를 기술해야 함