2021๋ 08์ 03์ผ ํ์์ผ 21:00~24:00
๐ฅ Baekjoon ๋ฌธ์ ํด๊ฒฐ ๐ฅ
โ 1748 ์ ์ด์ด ์ฐ๊ธฐ 1 _ Python
https://www.acmicpc.net/problem/1748
๋ฌธ์ ) 1๋ถํฐ N๊น์ง์ ์๋ฅผ ์ด์ด์ ์ฐ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์๋ก์ด ํ๋์ ์๋ฅผ ์ป์ ์ ์๋ค.
1234567891011121314151617181920212223...
์ด๋ ๊ฒ ๋ง๋ค์ด์ง ์๋ก์ด ์๋ ๋ช ์๋ฆฟ์์ผ๊น? ์ด ์์ ์๋ฆฟ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒ์์ ์๊ฐํ ๋ฐฉ๋ฒ์ ๋ฐ๋ณต๋ฌธ๊ณผ ์กฐ๊ฑด๋ฌธ์ ์ฌ์ฉํ์ฌ ์ฒ์๋ถํฐ ๋๊น์ง ๊ธธ์ด๋ฅผ ๋ํด์ฃผ๋ ๋ฐฉ๋ฒ์ด์๋ค.
ํ์ง๋ง ์๊ฐ์ ํ 0.15์ด๋ก ๋น์ฐํ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ์๋ค.
๋, ๊ฒ์์ ํ์ ๋ฐ์ ํด๊ฒฐํ ๋ฐฉ๋ฒ์ ์ผ์ ์๋ฆฌ, ์ญ์ ์๋ฆฌ, ๋ฐฑ์ ์๋ฆฌ ์ด๋ฐ ์์ผ๋ก ์๊ฐํด๋ณด๋ ๋ฐฉ๋ฒ์ด์๋ค.
์ผ์ ์๋ฆฌ = 1 ~ ๋๊น์ง
์ญ์ ์๋ฆฌ = 10 ~ ๋๊น์ง
๋ฐฑ์ ์๋ฆฌ = 100 ~ ๋๊น์ง
์ด๋ฐ ์์ผ๋ก ๋์ค๋ ๊ฒ์ ์ด์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์๋ค.
โก 1003 ํผ๋ณด๋์น ํจ์ _ Python
https://www.acmicpc.net/problem/1003
fibonacci(3)์ ํธ์ถํ๋ฉด ๋ค์๊ณผ ๊ฐ์ ์ผ์ด ์ผ์ด๋๋ค.
fibonacci(3)์ fibonacci(2)์ fibonacci(1) (์ฒซ ๋ฒ์งธ ํธ์ถ)์ ํธ์ถํ๋ค.
fibonacci(2)๋ fibonacci(1) (๋ ๋ฒ์งธ ํธ์ถ)๊ณผ fibonacci(0)์ ํธ์ถํ๋ค.
๋ ๋ฒ์งธ ํธ์ถํ fibonacci(1)์ 1์ ์ถ๋ ฅํ๊ณ 1์ ๋ฆฌํดํ๋ค.
fibonacci(0)์ 0์ ์ถ๋ ฅํ๊ณ , 0์ ๋ฆฌํดํ๋ค.
fibonacci(2)๋ fibonacci(1)๊ณผ fibonacci(0)์ ๊ฒฐ๊ณผ๋ฅผ ์ป๊ณ , 1์ ๋ฆฌํดํ๋ค.
์ฒซ ๋ฒ์งธ ํธ์ถํ fibonacci(1)์ 1์ ์ถ๋ ฅํ๊ณ , 1์ ๋ฆฌํดํ๋ค.
fibonacci(3)์ fibonacci(2)์ fibonacci(1)์ ๊ฒฐ๊ณผ๋ฅผ ์ป๊ณ , 2๋ฅผ ๋ฆฌํดํ๋ค.
1์ 2๋ฒ ์ถ๋ ฅ๋๊ณ , 0์ 1๋ฒ ์ถ๋ ฅ๋๋ค. N์ด ์ฃผ์ด์ก์ ๋, fibonacci(N)์ ํธ์ถํ์ ๋, 0๊ณผ 1์ด ๊ฐ๊ฐ ๋ช ๋ฒ ์ถ๋ ฅ๋๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ด์ ํผ๋ณด๋์น๋ ๊ฐ๋ฟํ๋ค๋ ์๊ฐ์ ํ์ฌ์ญํ๊ฒ ๋ง๋ ๋ฌธ์
์ฌ๊ท๋ก ํ์ด๋ณธ ๊ฒฐ๊ณผ ์๊ฐ์ ํ 0.25์ด๋ผ๋ ๋ฒฝ์ ๋งํ๊ฒ ๋์๋ค.
์กฐ๊ธ์ ๊ฒ์์ ํ์ผ๋ก dp๋ก ํด๊ฒฐํ๋ฉด ๋๋ค๋ ๋ง์ ์ฝ๋๋ฅผ ๋๋๋ ๐
์ด๋ฒ์๋ 20%์์ ํ๋ ธ์ต๋๋ค ๋ผ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ฐ๊ฒ ๋์๋ค. ์? Why?
๋ค์ ๊ฒ์ํด๋ณธ ๊ฒฐ๊ณผ ๋์ ์ฝ๋์ ๋ค๋ฅธ ๋ถ๋ถ์ด ์์ง๋ง ์ด ๋ถ๋ถ์์ ์ ํ๋ ธ์ต๋๋ค๊ฐ ๋ฐ์ํ๋์ง๋
์์ง๋ ์๋ฌธ์ด๋ค. ๐
โข 2751 ์ ์ ๋ ฌํ๊ธฐ 2 _ PyPy3
https://www.acmicpc.net/problem/2751
- ๋๊ฐ์ ์ฝ๋๋ฅผ Python3๋ก ์ ์ถ ์ ์๊ฐ ์ด๊ณผ ๋ฐ์
- PyPy3๋ก ์ ์ถ ์ ์ฑ๊ณต! (sort, sorted ๋ ๋ค ์ฑ๊ณต)
โฃ 9935 ๋ฌธ์์ด ํญ๋ฐ _ Python
https://www.acmicpc.net/problem/9935
์๊ทผ์ด๋ ๋ฌธ์์ด์ ํญ๋ฐ ๋ฌธ์์ด์ ์ฌ์ด ๋์๋ค. ํญ๋ฐ ๋ฌธ์์ด์ด ํญ๋ฐํ๋ฉด ๊ทธ ๋ฌธ์๋ ๋ฌธ์์ด์์ ์ฌ๋ผ์ง๋ฉฐ, ๋จ์ ๋ฌธ์์ด์ ํฉ์ณ์ง๊ฒ ๋๋ค. ํญ๋ฐ์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์งํ๋๋ค.
๋ฌธ์์ด์ด ํญ๋ฐ ๋ฌธ์์ด์ ํฌํจํ๊ณ ์๋ ๊ฒฝ์ฐ์, ๋ชจ๋ ํญ๋ฐ ๋ฌธ์์ด์ด ํญ๋ฐํ๊ฒ ๋๋ค. ๋จ์ ๋ฌธ์์ด์ ์์๋๋ก ์ด์ด ๋ถ์ฌ ์๋ก์ด ๋ฌธ์์ด์ ๋ง๋ ๋ค.
์๋ก ์๊ธด ๋ฌธ์์ด์ ํญ๋ฐ ๋ฌธ์์ด์ด ํฌํจ๋์ด ์์ ์๋ ์๋ค.
ํญ๋ฐ์ ํญ๋ฐ ๋ฌธ์์ด์ด ๋ฌธ์์ด์ ์์ ๋๊น์ง ๊ณ์๋๋ค.
์๊ทผ์ด๋ ๋ชจ๋ ํญ๋ฐ์ด ๋๋ ํ์ ์ด๋ค ๋ฌธ์์ด์ด ๋จ๋์ง ๊ตฌํด๋ณด๋ ค๊ณ ํ๋ค. ๋จ์์๋ ๋ฌธ์๊ฐ ์๋ ๊ฒฝ์ฐ๊ฐ ์๋ค. ์ด๋๋ "FRULA"๋ฅผ ์ถ๋ ฅํ๋ค. ํญ๋ฐ ๋ฌธ์์ด์ ๊ฐ์ ๋ฌธ์๋ฅผ ๋ ๊ฐ ์ด์ ํฌํจํ์ง ์๋๋ค.
- ๋ด์ฅ ํจ์๋ฅผ ์ฌ์ฉํ์ ๋ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค.
- ๋ ๋ฒ์งธ๋ก๋ stack์ ์ฌ์ฉํ์๋ค. ์คํ์ ๋ฃ๊ธฐ ์ ์ bomb์ ๋ง์ง๋ง ๋ฌธ์์ ๊ฐ์ ๋ฌธ์๋ฉด
stack์ ๋ค์ด์๋ ์์ ๊ธ์๋ค๊ณผ ๋น๊ตํด์ ์ง์ฐ๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฝ๋๋ฅผ ์์ฑํ์๋ค.
ํ์ง๋ง ์ด ๋ฐฉ๋ฒ์ ์๊ฐ ์ด๊ณผ๋ ๋ฐ์ํ์ง ์์์ง๋ง 50%์ฏค์์ ํ๋ ธ๋ค๊ณ ๋์๋ค.
- ๋ง์ง๋ง ๋ฐฉ๋ฒ์ผ๋ก๋ ์ฒ์์ stack์ ๋ฃ๊ณ ๋ง์ง๋ง์ผ๋ก ๋ฃ์ ๊ฒ์ด bomb์ ๋ง์ง๋ง ๋ฌธ์์ ๊ฐ์ผ๋ฉด
stack์์ bomb์ ๊ธธ์ด๋งํผ ๋น๊ตํ์ฌ ๊ฐ์ผ๋ฉด ์ง์ฐ๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฝ๋๋ฅผ ์์ฑํ์๋ค.
๋ ๋ฒ์งธ ๋ฐฉ๋ฒ๊ณผ ๋น์ทํ์ง ์์๊ฐ...? ์ฐจ์ด์ ์ ์์ง๋ ์ ๋ชจ๋ฅด๊ฒ ๋ค. ๐ฅ
'๐ฉโ๐ปStudy Group > ๐ซง2021 ํ๊ณ ๋ชจ๊ฐ์ฝ_์ํํฌ์ผ์ํธ๋ก' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
08์ 10์ผ ๋ชจ๊ฐ์ฝ_์ํฌํธ 6ํ์ฐจ ๊ฒฐ๊ณผ ๋ณด๊ณ ์ (0) | 2021.08.10 |
---|---|
08์10์ผ ๋ชจ๊ฐ์ฝ_์ํฌํธ 6ํ์ฐจ ๊ณํ (0) | 2021.08.10 |
08์03์ผ ๋ชจ๊ฐ์ฝ_์ํฌํธ 5ํ์ฐจ ๊ณํ (0) | 2021.08.03 |
07์ 27์ผ ๋ชจ๊ฐ์ฝ_์ํฌํธ 4ํ์ฐจ ๊ฒฐ๊ณผ ๋ณด๊ณ ์ (0) | 2021.07.27 |
07์27์ผ ๋ชจ๊ฐ์ฝ_์ํฌํธ 4ํ์ฐจ ๊ณํ (0) | 2021.07.27 |