LangChain์ ์ฌ์ฉํด์ ์ฌ์ฉ์๊ฐ ์ํ๋ ์ํ์ ์ฐพ์์ฃผ๋ URL์ ์์ฑํด์ฃผ๊ณ , FastAPI๋ฅผ ์์ฑํด Heroku์ ๋ฐฐํฌํด๋ณด์!
๋ฌธ์ ๋งํฌj == 0 ์ธ ๊ฒฝ์ฐ๋ ์ผ๊ฐํ ํ ์ค์ ๊ฐ์ฅ ์ผ์ชฝ์ ์๋ฏธ=> ์์ค์ ๊ฐ์ฅ ์ผ์ชฝ ๊ฐ์ ๋ํด์คj == i ์ธ ๊ฒฝ์ฐ๋ ์ผ๊ฐํ ํ ์ค์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ ์๋ฏธ=> ์์ค์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ๊ฐ์ ๋ํด์ค๊ทธ ์ธ์ ๊ฒฝ์ฐ๋ ์ผ๊ฐํ ํ ์ค์ ์ค๊ฐ์ ์์นํ ๊ฐ๋ค์ ์๋ฏธ=> ์ ์ค์ ์ผ์ชฝ/
๋ฌธ์ ๋งํฌ์ด ๋ธ๋ก๊ทธ๊ฐ ์ค๋ช ์ ์ํด๋ ๊ฒ ๊ฐ๋ค. ๋ธ๋ก๊ทธ ๊ทธ๋ฆผ ์ฐธ๊ณ ํ๊ธฐ.๐ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
๋์ ๋ง์ด ๊ฐ์ ธ๊ฐ ์ฌ๋์ด ์ด๊ธฐ๋ ๊ฒ ์๋๋ผ, ๋ง์ง๋ง์ผ๋ก ๋์ ๊ฐ์ ธ๊ฐ ์ฌ๋์ด ์ด๊ธฐ๊ธฐ ๋๋ฌธ์ ๋์ ์ผ๋ง๋ ๊ฐ์ ธ๊ฐ๋์ง๋ ์ค์ํ์ง ์๋ค.๊ฐ์ ธ๊ฐ ์ ์๋ ๋์ ๊ฐ์๊ฐ ํ์(1 or 3)์ด๊ธฐ ๋๋ฌธ์, N์ด ํ์์ธ์ง ์ง์์ธ์ง์ ๋ฐ๋ผ ๋ง์ง๋ง์ผ๋ก ๊ฐ์ ธ๊ฐ๋ ์ฌ๋์ด ์ ํด์ง๋ค.์๋ฅผ ๋ค์ด N
๋ฌธ์ ๋งํฌ์ฐธ๊ณ ํ ๋ธ๋ก๊ทธ๐ BFS๐ ๋ น์ ๋น์ฐ์ ๋ฐ๋ก ๋ฐ์ํ๋ฉด ์ฃผ๋ณ ๋น์ฐ์ ์ํฅ์ด ๊ฐ๊ธฐ ๋๋ฌธ์ ๋ฐ๋ก ๋ฆฌ์คํธ์ ์ ์ฅํ ํ, ๋ชจ๋ ๋น์ฐ์ ํ์์ด ๋๋ฌ์ ๋ ํ๊บผ๋ฒ์ ๋น์ฐ์ ๋ น์ธ๋ค.bsf(x, y)๋น์ฐ์ ์์น(x, y)๋ฅผ ๊ธฐ์ค์ผ๋ก ์ฃผ๋ณ ๋ฐ๋ค์ ๊ฐ์๋ฅผ ๊ตฌํ๋ค.๋น์ฐ์ ๋ฐ๋ก ๋ น
๋ฌธ์ ๋งํฌ์ฐธ๊ณ ํ ๋ธ๋ก๊ทธBFS๋ฅผ ์ด์ฉํ ํ์ด
๋ฌธ์ ๋งํฌ๐ ๊ธฐ๋ณธ์ ์ธ DFS ๋ฌธ์ ํ์ ์์ ๋ ธ๋๋ฅผ ์คํ์ ์ฝ์ ํ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ์คํ์ ์ต์๋จ ๋ ธ๋์ ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ๋ ธ๋๊ฐ ์๋ค๋ฉด ๊ทธ ์ธ์ ๋ ธ๋๋ฅผ ์คํ์ ๋ฃ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ๋ ธ๋๊ฐ ์๋ค๋ฉด ์คํ์์ ์ต์๋จ ๋ ธ๋๋ฅผ ๊บผ๋2๋ฒ์ ๊ณผ์ ์ ๋์ด์ ์ํํ ์ ์์
๋ฌธ์ ๋งํฌ๐ ๊ธฐ๋ณธ์ ์ธ ์ด์งํ์ ๋ฌธ์ ์ด์งํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ ๋ ๋ฐ์ดํฐ๋ ์ ๋ ฌ๋ ์ํ์ฌ์ผ ํ๊ธฐ ๋๋ฌธ์, N๊ฐ์ ์ ์ A1, ..., AN์ ๋จผ์ ์ ๋ ฌํ๋ค.๋ฆฌ์คํธ A๋ฅผ ์์์ /๋์ /์ค๊ฐ์ ์ผ๋ก ๋๋ ํ์ ๋ฒ์๋ฅผ ์ ๋ฐ์ฉ ์ขํ๊ฐ๋ฉฐ ๋ฐ์ดํฐ๋ฅผ ํ์ํ๋ค. ์ฐพ์ผ๋ ค๋ ๋ฐ์ดํฐ์ ์ค๊ฐ์
2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ๋ฌธ์ ๋งํฌ๋ค์ ํ์ด๋ณด๊ธฐ!
๋์ด๋: ๐๐ํ์ด์๊ฐ: 40๋ถ์๊ฐ์ ํ: 1์ด๋ฉ๋ชจ๋ฆฌ์ ํ: 256MB๊ธฐ์ถ: ํต์ฌ ์ ํ๋งํฌ: https://www.acmicpc.net/problem/11404
ATM์์์๊ฐ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌn=5๋ผ๊ณ ํ๋ฉด 0๋ฒ ์ธ๋ฑ์ค๋ 5๋ฒ ๋ํด์ง๊ณ , 1๋ฒ ์ธ๋ฑ์ค๋ 4๋ฒ ๋ํด์ง๊ณ ,,, ์ฆ (n-idx) \* timeidx๋ก ๊ตฌํํ ์ ์๋ค.์คํ ๋ฐฐ๋ฌ5๋ก ๋๋์ด์ง๋ฉด ๊ทธ ๋ชซ์ result์ ๋ํ๊ธฐ, ์ ๋๋ ์ง๋ฉด 5๋ก ๋๋ ์ง๋๊น์ง 3์ ๋นผ๊ธฐํต๊ณผ
๋์ด๋: โญโญํ์ด์๊ฐ: 30๋ถ์๊ฐ์ ํ: 1์ด๋ฉ๋ชจ๋ฆฌ์ ํ: 128MB๊ธฐ์ถ: Zoho ์ธํฐ๋ทฐN๊ฐ์ ์์๊ฐ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ์์ด์ด ์๋ค. ์ด๋ ์ด ์์ด์์ x๊ฐ ๋ฑ์ฅํ๋ ํ์๋ฅผ ๊ณ์ฐํ์์ค.๋จ, ์๊ฐ ๋ณต์ก๋ O(logN)์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ค๊ณํ์ง ์์ผ๋ฉด '์๊ฐ ์ด๊ณผ' ํ์ ์
์ด๋ฒ ํํธ์์ ์์คํ ๋ชจ๋ธ์ด ๋น์ ํ์ธ ๊ฒฝ์ฐ์ ์ ์ฉ ๊ฐ๋ฅํ ๋น์ ํ ์นผ๋ง ํํฐ์ ๋ํด ์์๋ณด์!๋๋ถ๋ถ์ ์ค์ ์์คํ ์ ๋น์ ํ ๋ชจ๋ธ๋ก ํํ๋๋๋ฐ, ์นผ๋ง ํํฐ๋ ์ ํ ๋ชจ๋ธ ๋์!โก ๋น์ ํ ๋ชจ๋ธ์ ์ ํ์ผ๋ก ๊ทผ์ฌํด์ ์ ํ ์นผ๋ง ํํฐ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๋ ํ์ฅ ์นผ๋ง ํํฐ(Ch12),
์ง๊ธ๊น์ง ์ดํด๋ณธ ์นผ๋ง ํํฐ์ ์ฉ๋๋์ก์ ์ ๊ฑฐ์ธก์ ํ์ง ์์ ์ํ ๋ณ์ ์ถ์ ์ด๋ฒ ์ฅ์์ ์นผ๋ง ํํฐ์ ์ผ์ ์ตํฉ ๋ฅ๋ ฅ์ ์ดํด๋ณด์!์นผ๋ง ํํฐ๋ ํนํ ํญ๊ณต๊ธฐ๋ ์ธ๊ณต์์ฑ์ ์์น์ ์์ธ๋ฅผ ์ธก์ ํ๋ ํญ๋ฒ(navigation) ๋ถ์ผ์์ ์ ๋์ ์ผ๋ก ๋ง์ด ์ฌ์ฉ!๊ฐ์๋๊ณ(accelerome
์นผ๋ง ํํฐ๋ก 2์ฐจ์ ํ๋ฉด ์์์ ์์ง์ด๋ ๋ฌผ์ฒด๋ฅผ ์ถ์ ํ๋ ๋ฐฉ๋ฒ์ ๋ํด ์์๋ณด์!๋ณดํต 2์ฐจ์ ์์์์ ํน์ ํ์ ์ ๊ฐ์ํ๊ณ ์ ํ ๋ ์ฌ์ฉ! ๐ ํ์ ์ ์์น๋ ์์ ์ฒ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์์๋ด์ผ ํ๋ค!(์นผ๋ง ํํฐ๋ ์์์์ ๋ฌผ์ฒด์ ์์น๋ฅผ ์ฐพ์๋ด์ง ๋ชปํ๋ค.)์นผ๋ง ํํฐ๋ ์์
๐ ์งฑ ์ค์ํ ์์ ! ๐์ง์ ์ ๋ก์์ ์ด์ฐจ๊ฐ 80m/s์ ์๋๋ฅผ ์ ์งํ๋์ง ์ํํด๋ณด์. ์์น์ ์๋ ์ ๋ณด๋ 0.1์ด ๊ฐ๊ฒฉ์ผ๋ก ์ธก์ ํด์ ์ ์ฅํ๋๋ก ๋์ด ์๋ค. ์ํ ๊ฒฐ๊ณผ๋ฅผ ๋ดค๋๋ ์๋ ๋ฐ์ดํฐ๊ฐ ๋ชจ๋ 0์ด๋ค. ์์น ์ ๋ณด๋ ์ด์์ด ์๋ค. ์ด๋ป๊ฒ ํ๋ฉด ๋ ๊น?์ง๊ธ๊น์ง๋ ์ฃผ๋ก
๋ฐฐํฐ๋ฆฌ์ ์ ์์ ์ธก์ ํ๋๋ฐ, ์ก์์ด ์ฌํด์ ์ด ๋๋ง๋ค ์ ์๊ฐ์ด ๋ฌ๋๋ค. ๊ทธ๋์ ์นผ๋ง ํํฐ๋ก ์ธก์ ๋ฐ์ดํฐ์ ์ก์์ ์ ๊ฑฐํด๋ณด๊ธฐ๋ก ํ๋ค. ์ ์์ 0.2์ด ๊ฐ๊ฒฉ์ผ๋ก ์ธก์ ํ๋ค.์ฒซ ๋ฒ์งธ ์์ ๋ฐฐํฐ๋ฆฌ์ ์ ์์ด ์ด๋ป๊ฒ ๋ณํ๊ธฐ๋์ง๋ฅผ ๋ํ๋ด๋ ์๋ฐฐํฐ๋ฆฌ์ ์ ์์ด ์ผ์ ํ๊ฒ ์ ์ง๋๊ณ ์์ (