์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- ์๊ณ ๋ฆฌ์ฆ
- ๋ค์ด๋๋ฏนํ๋ก๊ทธ๋๋ฐ
- ๋ณํฉ์ ๋ ฌ
- ๊น์ด์ฐ์ ํ์
- DP
- ์ฐ์ ์์ํ
- ์ํ
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ์์๊ตฌํ๊ธฐ
- ๋๋น์ฐ์ ํ์
- db
- ๊ทธ๋ํ์ํ๋ฌธ์
- ๊ทธ๋ฆฌ๋
- ๊ทธ๋ํํ์
- ๋ฐฑ์ค
- LIS
- ํ๋ก๊ทธ๋๋จธ์ค
- ์์ํ์
- ๋จธ์ง์ํธ
- ๊ทธ๋ํ
- 11650
- BFS
- ์๋ฃ๊ตฌ์กฐ
- ํ๋ก์ด๋์์ฌ
- ์ ๋ ฌ
- DFS
- SQL
- ๊ตฌํ
- Side Menu
- ๋์ ๊ณํ๋ฒ
๋ชฉ๋ก์ฝ๋ฉํ ์คํธ ์ค๋น/ํ๋ก๊ทธ๋๋จธ์ค (8)
๐๐ญ๐ฐ๐ธ ๐ฃ๐ถ๐ต ๐ด๐ต๐ฆ๐ข๐ฅ๐บ
๋ฌธ์ ๊ณ ์๋๋ก๋ฅผ ์ด๋ํ๋ ๋ชจ๋ ์ฐจ๋์ด ๊ณ ์๋๋ก๋ฅผ ์ด์ฉํ๋ฉด์ ๋จ์์ฉ ์นด๋ฉ๋ผ๋ฅผ ํ ๋ฒ์ ๋ง๋๋๋ก ์นด๋ฉ๋ผ๋ฅผ ์ค์นํ๋ ค๊ณ ํฉ๋๋ค. ๊ณ ์๋๋ก๋ฅผ ์ด๋ํ๋ ์ฐจ๋์ ๊ฒฝ๋ก routes๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฐจ๋์ด ํ ๋ฒ์ ๋จ์์ฉ ์นด๋ฉ๋ผ๋ฅผ ๋ง๋๋๋ก ํ๋ ค๋ฉด ์ต์ ๋ช ๋์ ์นด๋ฉ๋ผ๋ฅผ ์ค์นํด์ผ ํ๋์ง๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์. ์ ํ ์ฌํญ ์ฐจ๋์ ๋์๋ 1๋ ์ด์ 10,000๋ ์ดํ์ ๋๋ค. routes์๋ ์ฐจ๋์ ์ด๋ ๊ฒฝ๋ก๊ฐ ํฌํจ๋์ด ์์ผ๋ฉฐ routes[i][0]์๋ i๋ฒ์งธ ์ฐจ๋์ด ๊ณ ์๋๋ก์ ์ง์ ํ ์ง์ , routes[i][1]์๋ i๋ฒ์งธ ์ฐจ๋์ด ๊ณ ์๋๋ก์์ ๋๊ฐ ์ง์ ์ด ์ ํ ์์ต๋๋ค. ์ฐจ๋์ ์ง์ /์ง์ถ ์ง์ ์ ์นด๋ฉ๋ผ๊ฐ ์ค์น๋์ด ์์ด๋ ์นด๋ฉ๋ผ๋ฅผ ๋ง๋๊ฒ์ผ๋ก ๊ฐ์ฃผํฉ๋๋ค. ์ฐจ๋์ ์ง์ ์ง์ , ์ง์ถ ..
๋ฌธ์ ๋งค์ด ๊ฒ์ ์ข์ํ๋ Leo๋ ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๋ฅผ K ์ด์์ผ๋ก ๋ง๋ค๊ณ ์ถ์ต๋๋ค. ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๋ฅผ K ์ด์์ผ๋ก ๋ง๋ค๊ธฐ ์ํด Leo๋ ์ค์ฝ๋น ์ง์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๋ ๊ฐ์ ์์์ ์๋์ ๊ฐ์ด ํน๋ณํ ๋ฐฉ๋ฒ์ผ๋ก ์์ด ์๋ก์ด ์์์ ๋ง๋ญ๋๋ค. ์์ ์์์ ์ค์ฝ๋น ์ง์ = ๊ฐ์ฅ ๋งต์ง ์์ ์์์ ์ค์ฝ๋น ์ง์ + (๋ ๋ฒ์งธ๋ก ๋งต์ง ์์ ์์์ ์ค์ฝ๋น ์ง์ * 2) Leo๋ ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๊ฐ K ์ด์์ด ๋ ๋๊น์ง ๋ฐ๋ณตํ์ฌ ์์ต๋๋ค. Leo๊ฐ ๊ฐ์ง ์์์ ์ค์ฝ๋น ์ง์๋ฅผ ๋ด์ ๋ฐฐ์ด scoville๊ณผ ์ํ๋ ์ค์ฝ๋น ์ง์ K๊ฐ ์ฃผ์ด์ง ๋, ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๋ฅผ K ์ด์์ผ๋ก ๋ง๋ค๊ธฐ ์ํด ์์ด์ผ ํ๋ ์ต์ ํ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ ์ฌํญ scoville์..
๋ฌธ์ ์๋์ ๊ฐ์ด 5์ ์ฌ์น์ฐ์ฐ๋ง์ผ๋ก 12๋ฅผ ํํํ ์ ์์ต๋๋ค. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5๋ฅผ ์ฌ์ฉํ ํ์๋ ๊ฐ๊ฐ 6,5,4 ์ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ด์ค ๊ฐ์ฅ ์์ ๊ฒฝ์ฐ๋ 4์ ๋๋ค. ์ด์ฒ๋ผ ์ซ์ N๊ณผ number๊ฐ ์ฃผ์ด์ง ๋, N๊ณผ ์ฌ์น์ฐ์ฐ๋ง ์ฌ์ฉํด์ ํํ ํ ์ ์๋ ๋ฐฉ๋ฒ ์ค N ์ฌ์ฉํ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์. ์ ํ์ฌํญ N์ 1 ์ด์ 9 ์ดํ์ ๋๋ค. number๋ 1 ์ด์ 32,000 ์ดํ์ ๋๋ค. ์์์๋ ๊ดํธ์ ์ฌ์น์ฐ์ฐ๋ง ๊ฐ๋ฅํ๋ฉฐ ๋๋๊ธฐ ์ฐ์ฐ์์ ๋๋จธ์ง๋ ๋ฌด์ํฉ๋๋ค. ์ต์๊ฐ์ด 8๋ณด๋ค ํฌ๋ฉด -1์ return ํฉ๋๋ค. ์ ์ถ๋ ฅ ์ N number return 5 12 4..
๋ฌธ์ ์กฐ์ด์คํฑ์ผ๋ก ์ํ๋ฒณ ์ด๋ฆ์ ์์ฑํ์ธ์. ๋งจ ์ฒ์์ A๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ex) ์์ฑํด์ผ ํ๋ ์ด๋ฆ์ด ์ธ ๊ธ์๋ฉด AAA, ๋ค ๊ธ์๋ฉด AAAA ์กฐ์ด์คํฑ์ ๊ฐ ๋ฐฉํฅ์ผ๋ก ์์ง์ด๋ฉด ์๋์ ๊ฐ์ต๋๋ค. โฒ - ๋ค์ ์ํ๋ฒณ โผ - ์ด์ ์ํ๋ฒณ (A์์ ์๋์ชฝ์ผ๋ก ์ด๋ํ๋ฉด Z๋ก) โ - ์ปค์๋ฅผ ์ผ์ชฝ์ผ๋ก ์ด๋ (์ฒซ ๋ฒ์งธ ์์น์์ ์ผ์ชฝ์ผ๋ก ์ด๋ํ๋ฉด ๋ง์ง๋ง ๋ฌธ์์ ์ปค์) โถ - ์ปค์๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ (๋ง์ง๋ง ์์น์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ๋ฉด ์ฒซ ๋ฒ์งธ ๋ฌธ์์ ์ปค์) ์๋ฅผ ๋ค์ด ์๋์ ๋ฐฉ๋ฒ์ผ๋ก "JAZ"๋ฅผ ๋ง๋ค ์ ์์ต๋๋ค. - ์ฒซ ๋ฒ์งธ ์์น์์ ์กฐ์ด์คํฑ์ ์๋ก 9๋ฒ ์กฐ์ํ์ฌ J๋ฅผ ์์ฑํฉ๋๋ค. - ์กฐ์ด์คํฑ์ ์ผ์ชฝ์ผ๋ก 1๋ฒ ์กฐ์ํ์ฌ ์ปค์๋ฅผ ๋ง์ง๋ง ๋ฌธ์ ์์น๋ก ์ด๋์ํต๋๋ค. - ๋ง์ง๋ง ์์น์์ ์กฐ์ด์คํฑ์ ์๋๋ก 1๋ฒ ์กฐ์ํ์ฌ..
๋ฌธ์ ์ด์์ฒด์ ์ ์ญํ ์ค ํ๋๋ ์ปดํจํฐ ์์คํ ์ ์์์ ํจ์จ์ ์ผ๋ก ๊ด๋ฆฌํ๋ ๊ฒ์ ๋๋ค. ์ด ๋ฌธ์ ์์๋ ์ด์์ฒด์ ๊ฐ ๋ค์ ๊ท์น์ ๋ฐ๋ผ ํ๋ก์ธ์ค๋ฅผ ๊ด๋ฆฌํ ๊ฒฝ์ฐ ํน์ ํ๋ก์ธ์ค๊ฐ ๋ช ๋ฒ์งธ๋ก ์คํ๋๋์ง ์์๋ด๋ฉด ๋ฉ๋๋ค. 1. ์คํ ๋๊ธฐ ํ(Queue)์์ ๋๊ธฐ์ค์ธ ํ๋ก์ธ์ค ํ๋๋ฅผ ๊บผ๋ ๋๋ค. 2. ํ์ ๋๊ธฐ์ค์ธ ํ๋ก์ธ์ค ์ค ์ฐ์ ์์๊ฐ ๋ ๋์ ํ๋ก์ธ์ค๊ฐ ์๋ค๋ฉด ๋ฐฉ๊ธ ๊บผ๋ธ ํ๋ก์ธ์ค๋ฅผ ๋ค์ ํ์ ๋ฃ์ต๋๋ค. 3. ๋ง์ฝ ๊ทธ๋ฐ ํ๋ก์ธ์ค๊ฐ ์๋ค๋ฉด ๋ฐฉ๊ธ ๊บผ๋ธ ํ๋ก์ธ์ค๋ฅผ ์คํํฉ๋๋ค. 3.1 ํ ๋ฒ ์คํํ ํ๋ก์ธ์ค๋ ๋ค์ ํ์ ๋ฃ์ง ์๊ณ ๊ทธ๋๋ก ์ข ๋ฃ๋ฉ๋๋ค. ์๋ฅผ ๋ค์ด ํ๋ก์ธ์ค 4๊ฐ [A, B, C, D]๊ฐ ์์๋๋ก ์คํ ๋๊ธฐ ํ์ ๋ค์ด์๊ณ , ์ฐ์ ์์๊ฐ [2, 1, 3, 2]๋ผ๋ฉด [C, D, A, B] ์์ผ๋ก ์คํํ๊ฒ ๋ฉ๋๋ค. ํ์ฌ ์ค..
๋ฌธ์ โณโณ ๊ฒ์๋ํ๊ฐ ๊ฐ์ต๋์์ต๋๋ค. ์ด ๋ํ๋ N๋ช ์ด ์ฐธ๊ฐํ๊ณ , ํ ๋๋จผํธ ํ์์ผ๋ก ์งํ๋ฉ๋๋ค. N๋ช ์ ์ฐธ๊ฐ์๋ ๊ฐ๊ฐ 1๋ถํฐ N๋ฒ์ ์ฐจ๋ก๋๋ก ๋ฐฐ์ ๋ฐ์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ , 1๋ฒ↔2๋ฒ, 3๋ฒ↔4๋ฒ, ... , N-1๋ฒ↔N๋ฒ์ ์ฐธ๊ฐ์๋ผ๋ฆฌ ๊ฒ์์ ์งํํฉ๋๋ค. ๊ฐ ๊ฒ์์์ ์ด๊ธด ์ฌ๋์ ๋ค์ ๋ผ์ด๋์ ์ง์ถํ ์ ์์ต๋๋ค. ์ด๋, ๋ค์ ๋ผ์ด๋์ ์ง์ถํ ์ฐธ๊ฐ์์ ๋ฒํธ๋ ๋ค์ 1๋ฒ๋ถํฐ N/2๋ฒ์ ์ฐจ๋ก๋๋ก ๋ฐฐ์ ๋ฐ์ต๋๋ค. ๋ง์ฝ 1๋ฒ↔2๋ฒ ๋ผ๋ฆฌ ๊ฒจ๋ฃจ๋ ๊ฒ์์์ 2๋ฒ์ด ์น๋ฆฌํ๋ค๋ฉด ๋ค์ ๋ผ์ด๋์์ 1๋ฒ์ ๋ถ์ฌ๋ฐ๊ณ , 3๋ฒ↔4๋ฒ์์ ๊ฒจ๋ฃจ๋ ๊ฒ์์์ 3๋ฒ์ด ์น๋ฆฌํ๋ค๋ฉด ๋ค์ ๋ผ์ด๋์์ 2๋ฒ์ ๋ถ์ฌ๋ฐ๊ฒ ๋ฉ๋๋ค. ๊ฒ์์ ์ต์ข ํ ๋ช ์ด ๋จ์ ๋๊น์ง ์งํ๋ฉ๋๋ค. ์ด๋, ์ฒ์ ๋ผ์ด๋์์ A๋ฒ์ ๊ฐ์ง ์ฐธ๊ฐ์๋ ๊ฒฝ์์๋ก ์๊ฐํ๋ B๋ฒ ์ฐธ๊ฐ์์ ๋ช ๋ฒ์งธ ..
๋ฌธ์ ๊ดํธ๊ฐ ๋ฐ๋ฅด๊ฒ ์ง์ง์ด์ก๋ค๋ ๊ฒ์ '(' ๋ฌธ์๋ก ์ด๋ ธ์ผ๋ฉด ๋ฐ๋์ ์ง์ง์ด์ ')' ๋ฌธ์๋ก ๋ซํ์ผ ํ๋ค๋ ๋ป์ ๋๋ค. ์๋ฅผ ๋ค์ด "()()" ๋๋ "(())()" ๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ ๋๋ค. ")()(" ๋๋ "(()(" ๋ ์ฌ๋ฐ๋ฅด์ง ์์ ๊ดํธ์ ๋๋ค. '(' ๋๋ ')' ๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด s๊ฐ ์ฃผ์ด์ก์ ๋, ๋ฌธ์์ด s๊ฐ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด๋ฉด true๋ฅผ return ํ๊ณ , ์ฌ๋ฐ๋ฅด์ง ์์ ๊ดํธ์ด๋ฉด false๋ฅผ return ํ๋ solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์. ์ ํ์ฌํญ ๋ฌธ์์ด s์ ๊ธธ์ด : 100,000 ์ดํ์ ์์ฐ์ ๋ฌธ์์ด s๋ '(' ๋๋ ')' ๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ์ ์ถ๋ ฅ ์ ๊ธฐ๋ณธ ์๋ฃ๊ตฌ์กฐ ๋ฌธ์ ์ ๋ ๋ฒจ2์ง?? STL ์ฐ๋ฉด ๋์ด๋ค ์๋ฃ๊ตฌ์กฐ ์๊ฐ์ ์คํ ๋ฐฐ์ธ ๋ ๊ฐ์ฅ ํํ๊ฒ ์์๋ฅผ ๋๋ ๊ดํธ ๋ฌธ์ ๋ฅผ ์ค์ ..
๋ฌธ์ ์ขํํ๋ฉด์ ์ข์ํ๋ ์ง์๋ x์ถ๊ณผ y์ถ์ด ์ง๊ตํ๋ 2์ฐจ์ ์ขํํ๋ฉด์ ์ ์ ์ฐ์ผ๋ฉด์ ๋๊ณ ์์ต๋๋ค. ์ง์๋ ๋ ์์ ์ ์ k, d๊ฐ ์ฃผ์ด์ง ๋ ๋ค์๊ณผ ๊ฐ์ด ์ ์ ์ฐ์ผ๋ ค ํฉ๋๋ค. ์์ (0, 0)์ผ๋ก๋ถํฐ x์ถ ๋ฐฉํฅ์ผ๋ก a*k(a = 0, 1, 2, 3 ...), y์ถ ๋ฐฉํฅ์ผ๋ก b*k(b = 0, 1, 2, 3 ...)๋งํผ ๋จ์ด์ง ์์น์ ์ ์ ์ฐ์ต๋๋ค. ์์ ๊ณผ ๊ฑฐ๋ฆฌ๊ฐ d๋ฅผ ๋๋ ์์น์๋ ์ ์ ์ฐ์ง ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, k๊ฐ 2, d๊ฐ 4์ธ ๊ฒฝ์ฐ์๋ (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) ์์น์ ์ ์ ์ฐ์ด ์ด 6๊ฐ์ ์ ์ ์ฐ์ต๋๋ค. ์ ์ k์ ์์ ๊ณผ์ ๊ฑฐ๋ฆฌ๋ฅผ ๋ํ๋ด๋ ์ ์ d๊ฐ ์ฃผ์ด์ก์ ๋, ์ ์ด ์ด ๋ช ๊ฐ ์ฐํ๋์ง return ํ๋ solution ํจ์๋ฅผ ์์ฑ..