๐ Algorithm/๐ C++ ๋ฌธ์ ํ์ด(6)
-
C++ ๋ฐฑ์ค 1213 _ ํฐ๋ฆฐ๋๋กฌ ๋ง๋ค๊ธฐ
[C++ - ๋ฐฑ์ค 1213] ๋ฌธ์ ๊ทธ๋์ a~z ์์ผ๋ก cnt์ ์ํ๋ฒณ ๊ฐฏ์๋ฅผ ์ถ๊ฐํ๋ค. i = 'Z' ~ 'A' ๊น์ง ์ํ ํ๊ธฐ - ๋ฌธ์ ์์ ์ ๋ต์ด ์ฌ๋ฌ๊ฐ์ธ ๊ฒฝ์ฐ, ์ฌ์ ์์ผ๋ก ์์๋ ๊ฒ์ ์ถ๋ ฅํ๋ผ ํ๊ธฐ ๋๋ฌธ์ ret ๋ฌธ์์ด์ ์ถ๊ฐํ ๋๋ 'Z' ๋ถํฐ ์ถ๊ฐํด์ค๋ค. ๊ทธ๋์ผ ex) ZAZ -> BZAZB -> ABZAZBA ์ด๋ ๊ฒ ์ถ๊ฐ๋๊ธฐ ๋๋ฌธ! cnt[i] & 1 ์ ๋นํธ ์ฐ์ฐ์๋ก ํ์์ธ์ง ์ง์์ธ์ง ์ฌ๋ถ๋ฅผ ์ฒดํฌํด์ค๋ค - ํ์ ์ธ๊ฒฝ์ฐ mid ๊ฐ์ ์ ์ฅํ๊ณ flag๋ก ํ์์ธ ์ํ๋ฒณ์ ๊ฐ์๋ฅผ ํ์ธํ๋ค (2๊ฐ ์ด์์ผ ๊ฒฝ์ฐ ํฐ๋ฆฐ๋๋กฌ์ ๋ง๋ค ์ ์๊ธฐ ๋๋ฌธ!) ์ถํ ์์์ ์ ์ฅํ mid char ์ ret ๋ฌธ์์ด ์ ์ค์ (๊ฐ์ด๋ฐ)์ ์ถ๊ฐํด์ฃผ๋ฉด ํฐ๋ฆฐ๋๋กฌ์ด ์์ฑ๋๋ค #include using namespace std; in..
2023.02.10 -
C++ ๋ฐฑ์ค 1620 _ ๋๋์ผ ํฌ์ผ๋ชฌ ๋ง์คํฐ ์ด๋ค์ ๋ฌธ์ ํ์ด
[C++ - ๋ฐฑ์ค 1620] ๋ฌธ์ 1620๋ฒ: ๋๋์ผ ํฌ์ผ๋ชฌ ๋ง์คํฐ ์ด๋ค์ ์ฒซ์งธ ์ค์๋ ๋๊ฐ์ ์๋ก๋์ด ์๋ ํฌ์ผ๋ชฌ์ ๊ฐ์ N์ด๋ ๋ด๊ฐ ๋ง์ถฐ์ผ ํ๋ ๋ฌธ์ ์ ๊ฐ์ M์ด ์ฃผ์ด์ ธ. N๊ณผ M์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ธ๋ฐ, ์์ฐ์๊ฐ ๋ญ์ง๋ ์์ง? ๋ชจ๋ฅด๋ฉด www.acmicpc.net ๋ฌธ์ ์ค๋ช ์ฒซ์งธ ์ค์๋ ๋๊ฐ์ ์๋ก๋์ด ์๋ ํฌ์ผ๋ชฌ์ ๊ฐ์ N์ด๋ ๋ด๊ฐ ๋ง์ถฐ์ผ ํ๋ ๋ฌธ์ ์ ๊ฐ์ M์ด ์ฃผ์ด์ ธ. N๊ณผ M์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ธ๋ฐ, ์์ฐ์๊ฐ ๋ญ์ง๋ ์์ง? ๋ชจ๋ฅด๋ฉด ๋ฌผ์ด๋ด๋ ๊ด์ฐฎ์. ๋๋ ์ธ์ ๋ ์ง ์ง๋ฌธ์ ๋ตํด์ค ์ค๋น๊ฐ ๋์ด์์ด. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ํฌ์ผ๋ชฌ์ ๋ฒํธ๊ฐ 1๋ฒ์ธ ํฌ์ผ๋ชฌ๋ถํฐ N๋ฒ์ ํด๋นํ๋ ํฌ์ผ๋ชฌ๊น์ง ํ ์ค์ ํ๋์ฉ ์ ๋ ฅ์ผ๋ก ๋ค์ด์. ํฌ..
2023.02.10 -
C++ ๋์ ํฉ
์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ๋ค๋ณด๋ฉด ์ข ์ข for ๋ฌธ ๋์ '๋์ ํฉ'์ ์ฌ์ฉํด์ผํ๋ ๋ฌธ์ ๊ฐ ๋์จ๋ค ๋์ ํฉ์ด๋? - ์์๋ค์ด ๋์ ๋ ํฉ์ผ๋ก, ์ด๋ค ๋ฐฐ์ด์ ๊ธฐ๋ฐ์ผ๋ก ์์๋ค์ ๋์ ๋ ํฉ์ ์ ์ฅํด ์๋ก ๋ฐฐ์ด์ ๋ง๋ค์ด ์ด๋ฅผ ํ์ฉํ๋ ๋ฐฉ๋ฒ - ์์์ ๋ํ๋ prefix sum (์ฃผ๋ก ์ฝ๋ฉํ ์คํธ์์๋ prefix sum๋ง ๋์ด!!) - ๋ค์์ ๋ํ๋ suffix sum prefix sum ๋ง๋ค ๋ ์ฃผ์ํด์ผ ํ ์ - 0๋ฒ์งธ ์์๋ ๋น์๋๊ณ 1๋ฒ์งธ ์์๋ถํฐ ์ฌ์ฉํ์ psum[1] -> 0, 1 psum[2] -> 0,1,2 psum[3] -> 0, 1,2,3 psum[4] -> 0,1,2,3,4 ๋์ ํฉ์ ์ฝ๋๋ก ๊ตฌํํด๋ณด์! for(int i = 1; i > a[i]; psum[i] = psum[i-1] + a[i]; } for(i..
2023.02.10 -
C++ String ์๊ณ ๋ฆฌ์ฆ์์ ์์ฃผ ์ฐ์ด๋ ๋ฉ์๋
using namespace std; int main() { string a = "love is"; a += "pain!"; a.pop_back(); cout
2023.02.06 -
C++ ์์ด(permutation)๊ณผ ์กฐํฉ(combination)
์์ด(Permutation)์ด๋? ์์๊ฐ ์ ํด์ง ์์์ ์งํฉ์ ๋ค๋ฅธ ์์๋ก ์๋ ์ฐ์ฐ ex) n๊ฐ์ ์งํฉ ์ค n ๊ฐ๋ฅผ ๊ณจ๋ผ๋ผ ์ํ ๊ณต์ ) nPr = n! / (n-r)! ์์ด ๊ตฌํํ๊ธฐ 1. next_permutation / prev_permutation next_permutation : ์ค๋ฆ์ฐจ์ ๋ฐฐ์ด ๊ธฐ๋ฐ prev_permutation : ๋ด๋ฆผ์ฐจ์ ๋ฐฐ์ด ๊ธฐ๋ฐ next_permutation([first, last)) - first : ์์ด์ ์์ํ ๋ฒ์์ ์ฒซ๋ฒ์งธ ์ฃผ์ - last : ํฌํจ๋์ง ์์ ๋ง์ง๋ง ์ฃผ์ #include #include #include void printV(vector &v) { for(int i = 0; i < v.size(); i++) { cout
2023.02.01 -
0. C++ ์ ์ถ๋ ฅ
์ ๋ ฅ 1. std::cin ์ด์ฉํ๊ธฐ ๊ฐํ ๋ฌธ์ (๋์ด์ฐ๊ธฐ ์ํฐ) ๊น์ง๋ง ์ ๋ ฅ ๋ฐ๋๋ค int main() { std::string s; std::cin >> s; // ์๋ ํ์ธ์ ํ์ด std::cout
2023.01.27