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

위 문제를 O(1)로 풀 방법이 있나 찾아보다가

[중국인의 나머지 정리]라는 것을 찾았다.

이론에 대한 설명은 아래에 자세히 나와있다.

https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC#fn-10

다음은 BOJ 1476 날짜계산을 푸는 과정이다.

(28 * 19 * e) % 15 == (532 * e) % 15 == (7 * e) % 15 == 1

(15 * 19 * s) % 28 == (285 * s) % 28 == (5 * s) % 28 == 1

(15 * 28 * m) % 19 == (420 * m) % 19 == (2 * m) % 19 == 1

e == 13, s == 17, m == 10

[포인트 1]

(532 * e) % 15 == (7 * e) % 15

[포인트 2]

(7 * e) % 15 == 1

e의 값은 위 식을 만족하는 수 아무거나 고르면 되긴 하지만, 가장 작은 값을 찾는게 빠름

ANSWER = (E * 28 * 19 * 13 + S * 15 * 19 * 17 + M * 15 * 28 * 10) %  (15 * 28 * 19)

             = (E * 6916 + S * 4845 + M * 4200) % 7980

BOJ 6588 골드바흐의 추측

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

https://github.com/simjaemun2/BaekJoon/blob/bbb6bed5763440f079afa91844f0632558e8c30e/BOJ6588/BOJ6588.cpp

분류 : 소수 구하기, 에라토스테네스의 체

난이도 : MH

소수 배열을 만든 후, 3부터 답에 맞는지 확인한다.

Trie

<소개>

single string word로 이루어진 dictionary를 만든다고 가정

set<string> 대신 tries를 사용하는 이유?

1. trie는 string을 insert 하거나 find 할 때, O(L)의 시간으로 가능하다. (L : length of single word)

2. set<string> 이나 hash table은 정확한 word만 찾을 경우에만 사용이 가능하다.

하지만  trie는 예외의 경우가 있다.

- 한 글자만 다른 word를 찾을 때

- 공통 prefix가 있는 word를 찾을 때

- 한 글자가 빠진 word를 찾을 때

etc...

<Trie 란?>

retrieval 에서 따온 말

다음과 같은 자료구조로 되어 있다.

1. trie는 tree의 종류 중 하나로, 각각의 vertex는 하나의 word나 prefix를 나타낸다.

2. root는 empty string ("") 을 나타냄

3. 임의의 vertex가 root로 부터 K개의 edge 만큼 떨어져 있으면, 길이 K의 prefix를 나타낸다.

4. V와 W가 trie의 vertex이고 V가 W의 direct father이면,

V는 W의 associated prefix를 반드시 가지고 있다.

<coding>

- find exactly matched word

- 4 functions

1. addWord        - add a single string word to the dictionary

2. countPreffixes - dictionary 내의 특정 prefix를 갖는 모든 word의 수를 반환

3. countWords    - dictionary 내의 특정 word(인풋으로 주어짐)의 개수를 반환

4. 알파벳만 지원

shell sort는 일정한 인덱스 간격으로 사전 insertion sort를 수행한다.

insertion sort를 큰 인덱스에서 작은 인덱스 순서로 진행을 한다.

O( 1 ) : hashing

O( log n ) : speedy

----------------------------------------

O( n )

O( n log n )

----------------------------------------

O( n^2 )

O( n^3 )

----------------------------------------

O( n^n )

O( n! )

sorting은 1차원 data만 가능하다

Partial Order : 부분순서

Total Order : 전(체) 순서

Tree : Hierarchy "Parent - Child"

Bubble

compare : n - 1

swap : 0 ~ n - 1 까지 (Common work)

Selection

compare : n - 1 (Common work)

swap : 0 ~ 1 까지

Insertion

compare : n - 1까지

swap : 1 까지 + Shifting

Shifting -> Common work