
Euclidean Algorithm์ ๋๋์ผ๋ก ์๊ฐํ๋ฉด, ax+by=s๋ฅผ ๋ง์กฑํ๋ ์์ด ์๋๊ณ ์๋ก์์ธ ๋ ์ ์ x,y๋ฅผ ์ฐพ์ผ๋ฉด ๋๋ค.(UPD: ์ฌ์ค ์ด ์ ์ ์ฆ๋ช ํ๋ ๊ฒ๋ trivial ํ ๊ฒ์ ์๋๋ค. ๋จธ๋ฆฌ๋ฅผ ์ข ์ฐ๊ธด ํด์ผํจ) ์ผ๋ฐ์ ์ผ๋ก ax+by=s๋ฅผ ํธ๋ ๊ฒ์

์คํ๋ง์ ํต์ฌ ๋์์ ๋ด๋นํ๋ DispatcherServlet์์ ์์ฒญ ์ฒ๋ฆฌ์ ์ฌ์ฉ๋ ํธ๋ค๋ฌ๋ฅผ ์ฐพ์์ฃผ๊ณ , ์คํํ ๋ ์ฌ์ฉ๋๋ค.HandlerMapping์ ์์ฒญ์ ๋ฐ๋ฅธ ํธ๋ค๋ฌ๋ฅผ ์ฐพ์์ค๋ค.HandlerAdapter๋ ์ฐพ์๋ธ ํธ๋ค๋ฌ๋ฅผ ์คํ์์ผ์ค Adapter์ด๋ค.์ฝ๋์ ๋์

์ผ๋จ @Transactional(readonly=true)๋ ๋ฉ์๋๋ ํด๋์ค์ ์ ์ฉํด์ ํด๋น ํธ๋์ญ์ ์ ์ฝ๊ธฐ ์ ์ฉ์ผ๋ก ์ค์ ํ๋ ๊ธฐ๋ฅ์ ํ๋ค. ํด๋น ํธ๋์ญ์ ๋ด์์๋ ๋ฐ์ดํฐ๋ฅผ ์ฝ๊ธฐ๋ง ํ๊ณ ๋ณ๊ฒฝ ์์ ์ ์ํํ์ง ์์ ๊ฒ์์ ๋ช ์์ ์ผ๋ก ๋ํ๋ด์ค๋ค.๋์์ด ๋๋๋ ์ง๋ฌธ์ด๋ผ ์๋ฌด

์ฑ๋ฅ์ ์ต์ ํํ๊ธฐ ์ํด ์ฌ์ฉํ ์๋ ์๊ณ , ํน์ ํธ๋์ญ์ ์์ ์์์ ์ฐ๊ธฐ ์์ ์ด ์ผ์ด๋๋ ๊ฒ์ ์๋์ ์ผ๋ก ๋ฐฉ์งํ๊ธฐ ์ํด ์ฌ์ฉํ ์๋ ์๋ค. https://velog.io/@subinmun1997/Transactionreadonlytrue%EB%8A%94-%E

๋ฌธ์ ์ ๊ทธ๋ฆผ์ฒ๋ผ m x n ํ๋ ฌ์์ m x l ํ๋ ฌ์ ์ฌ๋ผ์ด๋ฉ ์ํค๋ฉด์ ๊ทธ ์์น์์ ๋ ํ๋ ฌ์ pointwise multiplication sum์ ๊ตฌํ๋ค. ๊ทธ ๊ฐ์ด w๋ฅผ ๋๋ ํ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. naive ํ๊ฒ ๊ตฌํ๋ฉด O(nml)๋ก ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค.์ฆ, ์ด ๋ฌธ์

2-SAT์ N๊ฐ์ ๋ถ๋ฆฌ์ธ ๋ณ์ (x_1, x_2, ..., x_n)๊ฐ ์์ ๋, 2-CNF ์์ true๋ก ๋ง๋ค๊ธฐ์ํด (x_i)๋ฅผ ์ด๋ค ๊ฐ์ผ๋ก ์ ํด์ผํ๋์ง๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. ์ด๋ฒ ๋ฌธ์ ๋ ๋ณ์์ ๊ฐ์ N๊ณผ ์ ์ ๊ฐ์ M, ๊ทธ๋ฆฌ๊ณ ์ (f)๊ฐ ์ฃผ์ด์ก์ ๋, ์ (f)๋ฅผ

์ ์ ๋ถํ ์ด๋ ์ ์ ์๋ ๊ฐ์ ์ฒ๋ผ ๊ฐ์ค์น๋ฅผ ์ฃผ๊ธฐ ์ํด ์ ์ ์ ํ๋์ ๊ฐ์ ์ผ๋ก ๋ง๋๋ ๊ธฐ๋ฒ์ด๋ค.์ด๋ ๊ฐ์ ์ ์ ์ ์ฒ๋ผ ์ทจ๊ธํ๊ธฐ ์ํด ์ ์ ์ ๋๊ฐ์ ์ ์ (in๊ณผ out)์ผ๋ก ๋ถํ ํ๋ค.in ์ ์ ์ ํด๋น ์ ์ ์ผ๋ก ๋ค์ด์ค๋ ๊ฐ์ ๋ค๊ณผ ์ฐ๊ฒฐํด์ฃผ๊ณ out ์ ์ ์ ํด๋น ์ ์ ์์ ๋ค๋ฅธ ์ ์ ์ผ