Intent

다른 apllication component가 어떤 action을 수행하도록 요청하기 위해 사용되는 메시징 객체.

대표적인 use cases - Activity를 시작 - Service를 시작 - Broadcast를 전달

명시적 인텐트

실행하고자 하는 component의 이름을 명시적으로 지정하여 호출한다. > 같은 앱 내의 다른 액티비티에 접근하고 할 때 명시적 인텐트를 사용한다.

//MainActivity.java
 
Intent intent = new Intent(this, SubActivity.class);
startActivity(intent);

Intent 객체 선언 후 startActivity를 통해 Intent에 명시된 액티비티를 시작한다. 위의 코드에서는 호출한 액티비티로부터 반환값을 받지 않는다.

//MainActivity.java
 
Intent in = new Intent(MainActivity.this, SubActivity.class);
startActivityForResult(in, GET_STRING);

startActivityForResult를 사용하게 되면 호출한 액티비티로부터 반환 값을 받을 수 있다.

//SubActivity.java
 
Intent intent = new Intent();
 
intent.putExtra("key", "value");
 
setResult(RESULT_CANCELED);

호출된 액티비티에서 인텐트에 데이터를 담아 setResult함수를 통해 반환값을 보낼 수 있다.

@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
    if(requestCode == GET_STRING) {
        if(resultCode == RESULT_OK) {
            text.setText(data.getStringExtra("INPUT_TEXT"));
        } else if(resultCode == RESULT_CANCELED) {
            //
        }
    } else if(requestCode == GET_NUMBER) {
        //
    }
}

onActivityResult를 통해 반환 값을 받을 수 있다.

암시적 인텐트

자신이 작성한 어플리케이션이 아닌 다른 어플리케이션의 component를 구동하는데 사용된다.

각 component는 자신이 처리할 수 있는 인텐트의 종류를 인텐트 필터 를 사용하여 안드로이드 운영체제에 알려줘야 한다. > 어떤 앱에서 액티비티나 서비스 등의 component를 외부에 공개하고자 할 때 인텐트 필터를 지정한다. 그렇지 않은 경우에는 인텐트 필터를 지정하지 않으면 된다.(암시적 인텐트 허용 않음)

Intent(String action, Uri uri)

intent = new Intent(Intent.ACTION_VIEW, Uri.parse("http://wwww.google.com"));

위와 같이 액션 수행시 필요한 데이터를 Uri 클래스의 객체로 제공한다. > Uri란 어떤 자원에 접근하기 위한 유일한 식별자를 의미. 일반적으로 URL과 URN을 포괄하는 개념으로 URL을 통해 프토토콜, 도메일, 자원의 위치정보를 얻고 URN을 통해 자원의 위치와 무관한 영속적인 유일환 자원의 정보를 얻는다.

if(intent != null) {
  if(intent.resolveActivity(getPackageManager()) != null) { startActivity(intent); }
}

startActivity(intent) 로 암시적 인텐트를 시작한다.  intent.resolveActivity()의 의미는 null이 아닌 경우 처리할 앱이 최소한 하나가 있다는 의미이다.

• 인텐트 액션 종류

//AndroidManifest.xml
 
<application
     android:allowBackup="true"
     android:icon="@mipmap/ic_launcher"
     android:label="@string/app_name"
     android:supportsRtl="true"
     android:theme="@style/AppTheme">
     <activity android:name=".MainActivity">
         <intent-filter>
             <action android:name="android.intent.action.MAIN" />
 
             <category android:name="android.intent.category.LAUNCHER" />
         </intent-filter>
     </activity>
 
     <activity
        android:name=".SecondActivity"
        android:label="@string/app_name_second">
 
        <intent-filter>
            <action android:name="android.intent.action.SEND"/>
            <category android:name="android.intent.category.DEFAULT"/>
            <data android:mimeType="image/*"
        </intent-filter>
     </activity>
</application>

위의 MainActivity에 설정된 intent-filter는 실행시키는 앱의 메인 시작점이기 때문에 action.MAIN과 category.LAUNCHER가 기본적으로 설정된다.

추가한 SecondActivity를 살펴보자.

기본적으로 인텐트 필터 매칭은 액션 / 카테고리 / 데이터 비교로 이루어진다.

1. 액션

   • 인텐트 객체에 설정된 액션은 인텐트 필터에 나열된 액션 중 하나와 반드시 일치해야 한다.

2. 카테고리

   • 인텐트 객체에 포함된 모든 카테고리가 인테트 필터에 나열되어 있어야 한다.

   • startActivity, startActivityForResult 로 전달되는 모든 암시적 인텐트는 android.intent.category.DEFAULT 카테고리에 속하는 것으로 자동 설정한다. -> 암시적 인테트를 받고자 하는 액티비티는 반드시 default category를 포함해야 한다.

3. 데이터

   • 데이터 타입이나 URI가 지정한 대로 똑같이 매칭이 된 경우에만 통과된다.

Action bar

안드로이드 상단에 출력되는 디자인 요소

아래와 같은 용도로 사용된다.

• 앱의 아이덴티티를 부여하는 공간 제공 (앱 아이콘, 로고)

• 검색과같은중요기능을눈에띄게함

• 앱 내에서 일관된 내비게이션과 뷰 전환을 지원함 - 탭, 드롭다운 메뉴

• 별로 사용하지 않는 액션을 액션 오버플로우로 제공하여 산만함을 줄임

@Override
    public boolean onCreateOptionsMenu(Menu menu) {
        getMenuInflater().inflate(R.menu.actions, menu);
        return super.onCreateOptionsMenu(menu);
    }
 
    @Override
    public boolean onOptionsItemSelected(MenuItem item) {
        switch(item.getItemId()) {
            case R.id.action_refresh:
                Toast.makeText(getApplicationContext(), "refresh", Toast.LENGTH_SHORT).show();
                return true;
            case R.id.action_search:
                Toast.makeText(getApplicationContext(), "search", Toast.LENGTH_SHORT).show();
                return true;
            case R.id.action_settings:
                Toast.makeText(getApplicationContext(), "settings", Toast.LENGTH_SHORT).show();
                return true;
            default:
                return super.onOptionsItemSelected(item);
        }
    }

onOptionsItemSelected를 사용하여 각 메뉴에 대한 이벤트를 설정한다.

<?xml version="1.0" encoding="utf-8"?>
<menu xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto">
 
    <item
        android:id="@+id/action_refresh"
        android:title="refresh"
        app:showAsAction="always|withText"
        />
 
    <item
        android:id="@+id/action_search"
        android:title="search"
        app:showAsAction="never"
        />
 
    <item
        android:id="@+id/action_settings"
        android:title="settings"
        app:showAsAction="always"
        />
</menu>

menu 리소스의 xml파일은 위와 같다.

app:showAsAction 옵션을 사용하기 위해 위에 보이는 xmlns:app을 선언해줘야 한다.

각 설정 타입의 내용은 아래와 같다.

표시되지 않은 메뉴항목에 대해서는 오른쪽에 오버플로우 메뉴로 합쳐지게 된다.

참고링크 : 커니의 안도로이드 이야기

Dialog

사용자에게 메시지를 출력하고 사용자로부터 입력을 받는 인터페이스

AlertDialog • DatePickerDialog / TimePickerDialog

AlertDialog

AlertDialog는 Activity 클래스를 이용해서 구현할 수 있다.

public class MainActivity extends AppCompatActivity {
    Button mButton1;
 
    private static final int DIALOG_YES_NO_MESSAGE = 1;
 
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
 
        mButton1 = (Button)findViewById(R.id.button1);
        mButton1.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View view) {
                showDialog(DIALOG_YES_NO_MESSAGE);
            }
        });
    }

showDialog()를 통해 대화상자를 호출한다.

    @Override
    protected Dialog onCreateDialog(int id) {
        switch(id) {
            case DIALOG_YES_NO_MESSAGE:
                AlertDialog.Builder builder = new AlertDialog.Builder(this);
                builder.setTitle("메시지")
                        .setMessage("종료하시겠어요?")
                        .setPositiveButton("Yes", new DialogInterface.OnClickListener() {
                            @Override
                            public void onClick(DialogInterface dialogInterface, int i) {
                                finish();
                            }
                        })
                        .setNegativeButton("No", new DialogInterface.OnClickListener() {
                            @Override
                            public void onClick(DialogInterface dialogInterface, int i) {
                                dialogInterface.dismiss();
                            }
                        });
 
                AlertDialog alert = builder.create();
                return alert;
        }
        return null;
    }
}

onCreateDialog는 showDialog 함수 호출시 호출되는 메소드이다. AlertDialog.Builder를 통해 대화상자를 설정하고 builder.create()를 통해 설정된 값으로 대화상자를 생성한다.

DialogFragment를 이용하여 AlertDialog 구현하기

Activity 클래스를 이용하는 것 외에 DialogFragment를 이용하는 방식이 있다.

public static class ButtonDialogFragment extends DialogFragment {
        @Override
        public Dialog onCreateDialog(Bundle savedInstanceState) {
            AlertDialog.Builder builder = new AlertDialog.Builder(getActivity());
            builder.setTitle("메시지")
                    .setMessage("종료하시겠어요?")
                    .setPositiveButton("Yes", new DialogInterface.OnClickListener() {
                        @Override
                        public void onClick(DialogInterface dialogInterface, int i) {
                            getActivity().finish();
                        }
                    })
                    .setNegativeButton("No", new DialogInterface.OnClickListener() {
                        @Override
                        public void onClick(DialogInterface dialogInterface, int i) {
                            dialogInterface.dismiss();
                        }
                    });
 
            return builder.create();
        }
    }

내부적으로 DialogFragment를 상속받는 내부 클래스를 선언하였다.

AlertDialog.Builder builder = new AlertDialog.Builder(getActivity());
 
//...
 
getActivity().finish();

첫번째 방법과 다른 점은 this 부분이 getActivity()로 바꼇다는 점이다.

mButton1.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View view) {
                DialogFragment dialogFragment = new ButtonDialogFragment();
                dialogFragment.show(getSupportFragmentManager(), "test");
            }
        });

해당 리소스에 리스너를 등록한다. 이 때 getSupportFragmentManager()를 이용하여 FragmentManager를 가져온다.(지원 라이브러리 사용할 경우)

DatePickerDialog

DialogFragment를 이용하여 구현한다.

public static class DatePickerFragment extends DialogFragment implements DatePickerDialog.OnDateSetListener {
        TextView mT;
 
        public void setEditText(TextView et) {
            mT = et;
        }
 
        @Override
        public Dialog onCreateDialog(Bundle savedInstanceState) {
            Calendar cal = Calendar.getInstance();
 
            return new DatePickerDialog(getActivity(), this, cal.get(Calendar.YEAR), cal.get(Calendar.MONTH), cal.get(Calendar.DATE));
        }
 
        @Override
        public void onDateSet(DatePicker view, int year, int monthOfYear, int dayOfMonth) {
            mT.setText(year + "/" + (monthOfYear + 1) + "/" + dayOfMonth);
        }
    }

onCreateDialog와 onDateSet 함수를 사용한다.

DatePickerDialog(Context context, DatePickerDialog.OnDateSetListener listener, int year, int month, int dayOfMonth)

Button bt = (Button) findViewById(R.id.button);
 
        // 버튼을 클릭했을 때 대화상자를 표시하도록 처리
        // OnClickListener를 설정(무명클래스로 이벤트 리스너 객체를 생성하는 방식)하고 onClick 메소드 구현
        bt.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                TextView editText = (TextView) findViewById(R.id.dateText);
 
                DatePickerFragment dpf = new DatePickerFragment();
                dpf.setEditText(editText);
                dpf.show(getFragmentManager(), "datePicker");
            }
        });

Context Menu

Context 메뉴란 UI에서 특정한 항목에 영향을 주는 동작을 선택할 수 있는 메뉴를 말한다.

Context 메뉴 생성방법은 크게 2가지가 있는데 floating context menu, context action menu 이다. 각 메뉴 생성방법에 대해 알아보자.

Floating Context Menu

화면을 long click 하면 나타나는 방식이다.

@Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
 
        mButton1 = (Button)findViewById(R.id.button1);
 
        registerForContextMenu(mButton1);
    }

registerForContextMenu에 해당 위젯을 등록시킨다.

    //floating context menu
    @Override
    public void onCreateContextMenu(ContextMenu menu, View v, ContextMenu.ContextMenuInfo menuInfo) {
        super.onCreateContextMenu(menu, v, menuInfo);
 
        menu.setHeaderTitle("Context menu");
        menu.add(0, 1, 0, "apple");
        menu.add(0, 2, 0, "grape");
    }

onCreateContextMenu는 Context 메뉴를 보여줘야 할 시점에 호출된다.

    @Override
    public boolean onContextItemSelected(MenuItem item) {
        switch (item.getItemId()) {
            case 1:
                return true;
            case 2:
                return true;
            default:
                return super.onContextItemSelected(item);
        }
    }

onContextItemSelected는 메뉴 이벤트 처리함수이다.

Context Action Mode

Context Action Mode를 구현하기 위해서는 View.OnLongClickListener, ActionMode.Callback 인터페이스르 구현해야 한다.

ActionMode 인터페이스를 구현하기 위해서는 아래의 4개의 메소드를 오버라이딩 해야 한다.

  ActionMode mActionMode;
 
    @Override
    public boolean onCreateActionMode(ActionMode mode, Menu menu) {
        MenuInflater inflater = mode.getMenuInflater();
 
        inflater.inflate(R.menu.actions, menu);
 
        return true;
    }

onCreateActionMode는 startActivity가 호출될 때 호출되는 콜백 메소드

    @Override
    public boolean onPrepareActionMode(ActionMode mode, Menu menu) {
        return false;
    }

onPrepareActionMode는 액션모드를 refresh하는 목적으로 아무것도 하지 않으면 false, 액션 메뉴가 업데이트되면 true 반환

    @Override
    public boolean onActionItemClicked(ActionMode mode, MenuItem item) {
        switch(item.getItemId()) {
            case R.id.apple:
                mode.finish();
                return true;
            case R.id.grape:
                mode.finish();
                return true;
            default:
                return false;
        }
    }

onActionItemClicked는 사용자가 액션 메뉴의 항목을 클릭했을 때 호출

    @Override
    public void onDestroyActionMode(ActionMode mode) {
        mActionMode = null;
    }

onDestroyActionMode는 액션 모드를 종료시켰을 때 호출

@Override
public boolean onLongClick(View view) {
    if(mActionMode!=null) {
        return false;
    }
 
    mActionMode = this.startSupportActionMode(this);
    view.setSelected(true);
    return true;
}

리스너를 등록한 위젯에서 LongClick시 ActionMode를 실행시키기 위해 startSupportActionMode를 사용하여 컨텍스트의 액션 모드를 실행한다.

스키마 모델링

일반 RDBMS는 중복을 최소화하기 위해 정규화를 한다. 하지만 Mongodb는 물리적인 특성상 객체를 내장할 경우 디스크에서 같은 곳에 위치하기 때문에 더 효율적이다.

예를 들어 같은 컬렉션내에 있는 도큐먼트에 접근하기 위해서는 내장되어 있을 때 같은 위치에 접근하기 때문에 효율적이지만, 내장되어있는 도큐먼트가 다른 컬렉션을 참조하는 경우에는 추가적인 비용이 필요하다.

스키마 디자인 할 때 일반적인 규칙이 있는데 고민하게 만든 사항을 살펴보겠다.

1. 한 객체에 포함관계로 모델링된 객체들은 내장

2. 다대다 관계는 보통 참조

3. 성능 이슈가 생기면 무조건 내장한다.

여기서 내장한다는게 정확히 무슨 말은 한다는 걸까?

아래와 같이 서브 도큐먼트를 내장한다는 걸까?

collection = {
  doc : new Schema {
    name: String
  }
}

아래와 같이 다른 컬렉션에 대한 도큐먼트의 id를 내장한다는 걸까?

collection2 = {
  doc2 : [
    {type: Schema.ObjectId}
  ]
}

그리고 일반 임베디드 도큐먼트라는 타입이 있는데 이걸 말하는걸가?

collection3 = {
  doc3 : {
    name: String
  }
}

각 타입에 대한 설명은 다음 링크를 참조한다.

mongoose와 유용한 schema 기능

모델링 타입은 2가지가 있다.

1. Normalized Data Models

   • 장점 : 다대다 관계, 복잡한 계층을 표현할 수 있다.

   • 단점 : 컬렉션에 중복된 데이터가 있어서 전체 읽기 성능은 떨어질 수 있다.

2. Embedded Data Models

   • 장점 : 1대1, 1대다 관계를 표현할 수 있다.

   • 단점 : 내장 도큐먼트의 크기는 한계가 있다. 따라서 도큐먼트의 크기가 생성 이후 계속 커진다면 사용을 지양해야 한다.

각 타입에 대한 자세한 설명은 다음 링크를 참조한다.

데이터 모델링 타입

스키마 디자인 팁

우선 객체간에 관계를 생각해보자.

객체간에 관계에서 생각해보는 입장을 취해보면 다음과 같이 나뉘어진다.

1. One-to-Few

2. One-to-Many

3. One-to-Squillions

4. 양방향 참조

그리고 읽기 대 쓰기 효율을 고려하여 비정규화를 시킬 수 있다.

1. Many-to-One 관계 비정규화

2. One-to-Many 관계 비정규화

3. One-to-Squillions 관계 비정규화

하나씩 살표보자

One-to-Few

{
  name:"John",
  address: [
    { p1: 'village', p2: 'village', p3: 'village'}
    { p1: 'pocket', p2: 'pocket2', p3: 'pocket3'}
  ]
}

하나 당 적은 관계의 수는 내포하여 한 번의 쿼리에 모든 정보를 보낼 수 있다. 하지만 내포된 데이터만 독자적으로 불러올 수 없다.

One-to-Many

//comments
{
  _id: ObjectId('AAA'),
  name: "John"
}
 
//boards
{
  _id: ObjectId('BOA');
  comments: [
    ObjectId('AAA'),
    ObjectId('BBB')
  ]
}

각각의 문서를 독자적으로 다룰 수 있지만 여러번 호출해야 하는 단점이 있다. 이 경우 DB 레벨이 아닌 어플리케이션 레벨의 join으로 두 문서를 연결해야 한다.

  boards = db.boards.findOne({_id: ObjectId('BOA')})
 
  comments_array = db.comments.find({_id: {$id: boards.comments}}).toArray();

One-to-Squillions

//host
{
  _id: ObjectId('AAA'),
  ipAddr: '111.111.111.111'
}
 
//logs
{
  time: ISODate()
  host: ObjectId('AAA')
}

엄청나게 큰 많은 데이터가 필요한 경우 단일 문서의 크기가 한정되어 있기 때문에 부모 참조 방식을 활용해야 한다. 조인 방식은 다음과 같다.

host = db.hosts.findOne({_id: ObjectId('AAA')})
 
last_logs = db.logs.find({host: host._id}).sort({time:-1}).limit(5000);

양방향 참조

//comments
{
  parent: ObjectId('BOA')
  _id: ObjectId('AAA'),
  name: "John"
}
 
//boards
{
  _id: ObjectId('BOA');
  comments: [
    ObjectId('AAA'),
    ObjectId('BBB')
  ]
}

양방향 참조는 One-to-Many에서 서로 참조하는 경우이다. 각 컬렉션에서 다른 컬렉션에 쉽게 접근할 수 있지만 문서를 삭제하는데 있어 쿼리를 두 번 보내야 한다.

그 외에 비정규화의 관계를 사용하게 되면(중복을 허용) 쓰기 성능보다 읽기 성능이 높아진다.

다음 링크에서 관련된 자세한 내용을 확인할 수 있다.

스키마 디자인 6가지 전략

성능을 높이기 위해 Index를 사용할 때 주의할 점.

Mongodb의 물리적 데이터 저장 구조를 살펴 보면 아래와 같다.

먼저 살펴보자면, 데이터 저장 시 논리적 메모리 공간에 write하고 일정 주기에 따라서 disk로 flsuh를 하는 Write Back 방식을 사용한다.(이 때문에 메모리에만 적재하면 되는 특성으로 인해 Write 속도가 빠르다는 말이 나오는 것 같다.)

데이터의 Read시에도 파일의 index를 메모리에 로딩해놓고 그 후 검색을 한다. 이 점에서 메모리에 저장되는 내용을 실제 데이터 블럭과 index 자체가 저장된다. 이 때문에 index를 남용하면 안된다. index를 생성하거나 업데이트할 때는 자원이 들어가며 index가 메모리에 상주하고 있어야 제대로 된 성능을 낸다.

메모리에 공간이 부족하면 page fault가 일어나게 되고 메모리에서 disk로부터 해당 데이터 블록을 요청하여 page와 disk 사이에 스위칭이 일어나게 되고 disk i/o 가 발생하여 성능을 떨어뜨리게 된다.

Index 선택에도 다음과 같은 규칙이 있다.

1. 찾고자 하는 키에 대한 필드는 인덱스 한다.

2. 보통 정렬하는 필드에 인덱스 한다.

인덱스를 사용하게 되면 쓰기의 성능은 떨어지기에 쓰기보다 읽기 비율이 높은 컬렉션에 인덱스를 사용하면 좋다.(위에서 말한것처럼 인덱스를 과용 사용하게 되면 메모리에 과잉문제가 생길 수 있다.)

결론

답은 없는 것 같다. 우선 구현 해보고 쿼리를 이용해 성능 테스트 해보면서 서비스 특성에 맞게 조정해봐야 할 것 같다. 여기에 많은 시간을 사용하였지만 아직 잘 모르겠다. 다음에 알아봐야 할 점으로는 다음과 같다.

• Mongodb는 많은 수의 collection을 제공한다. collection의 수가 성능에 미치는 영향이 있는가?(하나의 컬렉션에다가 관리하는 것보다 각 컬렉션에서 쿼리를 사용하는게 더 효율적인 것 같지만.. 컬렉션이 많다고 좋은 점만 있는 것 같지는 않다.)

• 네트워크 호출 비용 vs 몽고디비 쿼리 조인 비용(이건 네트워크 호출보다 쿼리로 조인하는게 좋다고 생각하지만 알아볼 가치는 있는 것 같다.)

참조링크 :

Mongodb의 물리 데이터 저장 구조

스키마 디자인 6가지 전략

스키마 디자인

mongoose 스키마와 유용한 기능

데이터 모델링 타입

참고사이트

http://bcho.tistory.com/999

[문제]

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

[풀이]

필요한 입력데이터를 간추려 보면 현재 자릿수, 값, 그리고 각 자리수를 한번이라도 넣었는지 확인하는 변수가 필요합니다.

chairCount(location, value, state)는 해석하면 현재 자릿수에서 해당 값을 넣었을 때의 경우의 수에 대한 정보를 가지고 있습니다. 

주의 깊게 봐야할 점은 2가지가 있습니다.

1. long long 타입을 사용. 경우의 수가 상당히 크기 때문에 long long 타입을 사용하였고 출력서식형태는 %lld 입니다.

2. state는 해당 값을 이전에 넣었다면 true/false로 관리하기 위해 배열을 사용할 수 있지만 아래와 같이 비트마스크를 이용하여 관리할 수 있습니다. (state | 1<<value) 로 하여 value 자리에 1을 채워넣을 수 있습니다.

#include <stdio.h>

#include <string.h>

#define MOD 1000000000

int n;

long long cache[101][11][1<<11];

int chairCount(int location, int value, int state) {

if(value<0 || value>9) return 0;

if(location == n) {

if((state | (1<<value)) == (1<<10)-1) return 1;

else return 0;

}

long long & ret = cache[location][value][state];

if(ret!=-1) return ret;

state |= (1<<value);

return ret = (chairCount(location+1, value+1, state) + chairCount(location+1, value-1, state) ) % MOD;

}

int  main() {

scanf("%d", &n);

memset(cache, -1, sizeof(cache));

long long count = 0;

for(int i=1 ; i<=9 ; i++) {

count = (count + chairCount(1, i, 0)) % MOD;

}

printf("%lld", count);

return 0;

}

[더블릿] fac

N!의 끝에서 연속하는 0의 개수를 출력하는문제이다. 단, N! = N * (N-1) * (N-2) . . . * 3 * 2 * 1

예를들어 10! = 3628800 임으로 끝에서 연속하는0의 개수는 2이다.

입력

N이 주어진다. ( 1 <= N <= 1,000,000,000,000,000,000 )

출력

끝에서 연속하는 0의 개수를 출력한다. 단, 숫자가 너무커질수 있으므로 500,000,000,000,000,007로 나눈 나머지 값을 출력한다.

입출력 예

입력 

1

출력

0

입력

10

출력

2

입력

100

출력

24

입력

1422534662

출력

355633660

[풀이]

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120    <--- 1개

6! = 720

7! = 5040

8! = 40320

9! =362880

10! = 3628800   <--- 2개

15! = 1307...000 <--- 3개

20! = 243...0000 <--- 4개

25! =1551..000000 <--- 6개

n!에서 n이 5로 나누어지면 0이 1씩 증가함을 알 수 있다.

n이 25이면 n/5 로 나누어져 5개의 0을 가지고, 추가적으로 25로 또 나누어지기 때문에 한개의 0을 가진다는 점근법을 세울 수 있다.

n이 50이면 50/5로 나누어져 10개의 0을, 추가적으로 50/25로 또 나누어지기 때문에 2개의 0을 가진다고 예측할 수 있다.

for (int i = 1; i <= 25; ++i) {

      cnt += (long long)(num / pow(5, i)) % 500000000000000007;

 }