๐ฅ๊ณ ๋ฆฌ์ฆ
[Algorithms] String(Pattern) Matching
[Algorithms] String(Pattern) Matching
2023.06.01String ์ด๋ ๊ธธ์ด๊ฐ 0 ์ด์์ธ Character ๋ค์ ๋์ด์ ์๋ฏธํฉ๋๋ค. ๊ธธ์ด๊ฐ 0 ์ธ String ์ "" ์ ๊ฐ์ด ํํํ ์ ์์ผ๋ฉฐ, Empty String ์ด๋ผ๊ณ ๋ถ๋ฆ
๋๋ค. ๊ทธ์ ๋ฐ๋๋ก, ๊ธธ์ด๊ฐ 1 ์ด์์ธ String ์ Non-empty String ์ด๋ผ๊ณ ๋ถ๋ฆ
๋๋ค. String ์ ์์ - C++ Program : C++ ๋ก ์์ฑํ .cpp ํ์ผ๋ ํ๋์ ๋ฌธ์์ด์ด๋ผ๊ณ ํ ์ ์์ต๋๋ค. - HTML Document : ํธํธ์!! ๊ณผ ๊ฐ์ด ์ฐ๋ฆฌ๊ฐ ๋ธ๋ผ์ฐ์ ๋ฅผ ํตํด์ ์นํ์ด์ง๋ฅผ ์ด์ฉํ ๋, ์ฌ์ฉ๋๋ HTML ํ์ผ๋ ํ๋์ ๋ฌธ์์ด์
๋๋ค. - DNA Sequence : {A, C, G, T} ๋ก ๊ตฌ์ฑ๋ ์ผ๊ธฐ์์ด์ ๋์ด๋ ๋ฌธ์์ด์
๋๋ค. - Digitized Image : ๋์งํธ ์ด๋ฏธ์ง๋ {0, 1} ๋ก..
[Algorithms] Dynamic Programming
[Algorithms] Dynamic Programming
2023.05.26/* ๊ฐ์ ์ ๋ฆฌ */ Dynamic Programming(๋์ ๊ณํ๋ฒ) ์ด๋? ์ฒ์์ ์ฃผ์ด์ง ํฐ ๋ฌธ์ ๋ฅผ ์ฌ๋ฌ๊ฐ์ ์์ ๋ฌธ์ ๋ก ๋๋์ด ํธ๋ ๋ฐฉ๋ฒ์ ๋งํฉ๋๋ค. ์ด๋? Divide&Conquer(๋ถํ ์ ๋ณต๊ธฐ๋ฒ)๋ ๊ฐ์๊ฑฐ ์๋๊ฐ? ํ ์๋ ์์ง๋ง, ํฐ ์ฐจ์ด์ ํ๋๊ฐ ์์ต๋๋ค. Dynamic Programming ์ ์ค๋ณต ๊ณ์ฐ์ ํ์ง ์๋๋ค๋ ์ ์
๋๋ค. Divide&Conquer ์์๋ ํฐ ๋ฌธ์ ๋ฅผ ์ฌ๋ฌ๊ฐ์ ์์ ๋ฌธ์ ๋ก ๋๋ ํ์, ์์ ๋ฌธ์ ๋ฅผ ๊ณ์ฐํ๊ณ ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ๊ฒฐํฉํด ์ ๋จ๊ณ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ์์ด์์ต๋๋ค. Dynamic Programming ์์๋ ์ด์ ๊ฑฐ์ ์ ์ฌํ์ง๋ง, ๋๋ ์ง ์์ ๋ฌธ์ ๋ค ์ค ์ด๋ฏธ ์์ ๊ณ์ฐํ ์ ์ด ์๋ ์ฐ์ฐ์ด๋ผ๋ฉด ์ด๋ฅผ ์ค๋ณตํด์ ๊ณ์ฐํ์ง ์๊ณ ์ด์ ์ ๊ฒฐ๊ณผ๊ฐ์ ๋ถ๋ฌ์ ์ฌ์ฉํฉ๋๋ค. ์ด๋ฌํ ์ด์ ์ฐ..
[C++] ๋ฐฑ์ค BOJ 21939 ๋ฌธ์ ์ถ์ฒ ์์คํ
Version 1
[C++] ๋ฐฑ์ค BOJ 21939 ๋ฌธ์ ์ถ์ฒ ์์คํ Version 1
2021.11.18/* BOJ 21939 ๋ฌธ์ ์ถ์ฒ ์์คํ
Version 1 ์ ์ฝ๋์
๋๋ค. ํจ์จ์ ์ด์ง ์์ ํ์ด์ด๋,, ๋ค๋ฅธ ๋ถ์ ํ์ด๋ฅผ ์ฐธ๊ณ ํ์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค..! */ ๋ฌธ์ ๋งํฌ : https://www.acmicpc.net/problem/21939 21939๋ฒ: ๋ฌธ์ ์ถ์ฒ ์์คํ
Version 1 tony9402๋ ์ต๊ทผ ๊นํ์ ์ฝ๋ฉํ
์คํธ ๋๋น ๋ฌธ์ ๋ฅผ ์ง์ ๋ฝ์์ "๋ฌธ์ ๋ฒํธ, ๋์ด๋"๋ก ์ ๋ฆฌํด๋จ๋ค. ๊นํ์ ์ด์ฉํ์ฌ ๊ณต๋ถํ์๋ ๋ถ๋ค์ ์ํด ์๋ก์ด ๊ธฐ๋ฅ์ ์ถ๊ฐํด๋ณด๋ ค๊ณ ํ๋ค. ๋ง๋ค๋ ค๊ณ ํ๋ ๋ช
๋ น www.acmicpc.net ์ ๋ต ์ฝ๋ #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); ..
[C++] ๊ฑฐ๋ฆฌ๋๊ธฐ ํ์ธํ๊ธฐ(2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ ์ฝ๋ฉํ
์คํธ)
[C++] ๊ฑฐ๋ฆฌ๋๊ธฐ ํ์ธํ๊ธฐ(2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ ์ฝ๋ฉํ ์คํธ)
2021.11.03/* 2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ ์ฝ๋ฉํ
์คํธ ๋ฌธ์ ์ ๋ํ C++ ํด๊ฒฐ๋ฐฉ๋ฒ์
๋๋ค. 2๋ฒ์งธ ์ฝ๋๋ ๊ฐ์ ๋ฌธ์ ๋ฅผ BFS๋ก ํด๊ฒฐํ ์ฝ๋์
๋๋ค. */ ๋ฌธ์ ๋งํฌ : https://programmers.co.kr/learn/courses/30/lessons/81302 ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ๊ฑฐ๋ฆฌ๋๊ธฐ ํ์ธํ๊ธฐ [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXP..
[Python] ์ซ์ ๋ฌธ์์ด๊ณผ ์๋จ์ด(2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ ์ฝ๋ฉํ
์คํธ)
[Python] ์ซ์ ๋ฌธ์์ด๊ณผ ์๋จ์ด(2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ ์ฝ๋ฉํ ์คํธ)
2021.11.03/* 2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ ์ฝ๋ฉํ
์คํธ ๋ฌธ์ ์ ๋ํ C++ ํด๊ฒฐ๋ฐฉ๋ฒ์
๋๋ค. ๋ฌธ์์ด์ ์ฌ์ฉํ๋ ๋ฌธ์ ์ด๊ธฐ์ python์ ์ฌ์ฉํ์ต๋๋ค. */ ๋ฌธ์ ๋งํฌ https://programmers.co.kr/learn/courses/30/lessons/81301 ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ์ซ์ ๋ฌธ์์ด๊ณผ ์๋จ์ด ๋ค์ค์ ํ๋ก๋๊ฐ ์ซ์๋์ด๋ฅผ ํ๊ณ ์์ต๋๋ค. ๋ค์ค๊ฐ ํ๋ก๋์๊ฒ ์ซ์๋ฅผ ๊ฑด๋ฌ ๋ ์ผ๋ถ ์๋ฆฟ์๋ฅผ ์๋จ์ด๋ก ๋ฐ๊พผ ์นด๋๋ฅผ ๊ฑด๋ค์ฃผ๋ฉด ํ๋ก๋๋ ์๋ ์ซ์๋ฅผ ์ฐพ๋ ๊ฒ์์
๋๋ค. ๋ค์์ ์ซ์์ ์ผ๋ถ ์ programmers.co.kr def solution(s): str_arr = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"] ..
[C++] ๋ฐฑ์ค BOJ 5525 IOIOI
[C++] ๋ฐฑ์ค BOJ 5525 IOIOI
2021.10.28์ด ๊ธ์ ๋ณดํธ๋์ด ์๊ธฐ ๋๋ฌธ์ ์ด๊ฒ์ ๋ณด๋ ค๋ฉด ์ํธ๊ฐ ํ์ํฉ๋๋ค.
2์ n์น ๊ฐ ๋นํธ์ฐ์ฐ์๋ฅผ ์ด์ฉํด์ ๊ฐ๋จํ๊ฒ ํํํ์..!
2์ n์น ๊ฐ ๋นํธ์ฐ์ฐ์๋ฅผ ์ด์ฉํด์ ๊ฐ๋จํ๊ฒ ํํํ์..!
2021.09.27/* BOJ 1074 ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค๊ฐ ์๊ฒ๋ ์ ์ ๋ํด ์์ฑํ ๊ธ์
๋๋ค..! */ ์ง๊ธ๊น์ง C++์์ ์ด๋ค ์์ n์น ๊ฐ์ ๊ณ์ฐํ๊ณ ์ฌ์ฉํ๊ธฐ ์ํ์ฌ cmath ๋ผ์ด๋ธ๋ฌ๋ฆฌ์ ํฌํจ๋์ด ์๋ pow ํจ์๋ฅผ ์ฌ์ฉํ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, 2์ 12์น์ ๊ตฌํ๊ณ ์ ํ๋ค๋ฉด cmath ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ include ํด์ฃผ๊ณ pow(2, 12) ๊ณผ ๊ฐ์ด ํจ์๋ฅผ ์ฌ์ฉํ์ฌ ๊ฐ์ ๊ตฌํด์ฃผ์ด ์ฌ์ฉํ์ต๋๋ค. ๊ทผ๋ฐ...! ๋นํธ ์ฐ์ฐ์๋ฅผ ์ด์ฉํ์ฌ ์กฐ๊ธ ๋ ๊ฐ๋จํ๊ฒ ํํํ ์ ์์ต๋๋ค! ์ฌ๊ธฐ์ ๋นํธ ์ฐ์ฐ์(Bitwise operators)๋!? Operator Symbol Form Operation left shift > y all bits in x shifted right y bits bitwise NOT ~ ~x all bits in x..
[C++] ์กฐํฉ(combination)
[C++] ์กฐํฉ(combination)
2021.08.27long long ans = 1; cin >> m >> n; for (int i = 1; i
[c++] scanf & cin ์๋ ์ฐจ์ด(์
๋ ฅ ์๊ฐ ์ด๊ณผ)
[c++] scanf & cin ์๋ ์ฐจ์ด(์ ๋ ฅ ์๊ฐ ์ด๊ณผ)
2021.08.27์ด๋ถ ํ์์ ์ด์ฉํ๋ ๊ฐ๋จํ ๋ฌธ์ ์๋ค. ์ฒซ๋ฒ์งธ ์๋์์ ์ด๋ถ ํ์์ ์ฌ์ฉํ์ง ์์์๊ณ , ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋๊ฑธ ๋ณด๊ณ ์ด๋ถ ํ์์ ๋์
ํ๋๋ฐ ๊ณ์ํด์ ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. ์์ง..? ์์ธ์ ์๊ฐ์ง๋ ๋ชปํ ๊ณณ์ ์์๋ค. ๋ ์ฝ๋์ ์ฐจ์ด์ ์ด ๊ทธ ์์ธ์ด๋ค. #include using namespace std; vector v; int N, M; int main() { cin >> N; int input; for (int i = 0; i > input; v.push_back(input); } sort(v.begin(), v.end()); cin >> M; for (int i = 0; i > input; if (binary_search(v.begin(),..
[C++] pair vector๋ฅผ sort! ๋ค์ด์จ ์์๋ ๊ธฐ์ค์ผ๋ก ๋ ์ ์๋ค๊ฑฐ!
[C++] pair vector๋ฅผ sort! ๋ค์ด์จ ์์๋ ๊ธฐ์ค์ผ๋ก ๋ ์ ์๋ค๊ฑฐ!
2021.08.06/* BOJ 10814์ ๊ด๋ จ๋ ๊ธ์
๋๋ค */ ์ด ๋ฌธ์ ๋ฅผ pair์ vector์ ์กฐํฉ์ผ๋ก ํ์ด๋ณด๋ ค๊ณ ํ๋๋ฐ!! ๊ฑธ๋ฆฌ๋๊ฒ ์๋ค. ๊ทธ๋ฅ ์
๋ ฅ๊ฐ์ผ๋ก ์ฃผ์ด์ง ๋์ด์ ์ด๋ฆ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๋ฉด ์ฌ์ด๋ฐ! ์ด ๋ฌธ๊ตฌ๊ฐ ๊ฑธ๋ฆฐ๋ค.. ์ด๋ ์ฌ์ฉํ ์ ์๋๊ฒ stable_sort๋ค! ์ฌ์ฉ๋ฒ์ sort์ ์์ ๋๊ฐ์๋ฐ ์ด stable_sort๋ ๊ธฐ์ค์ด ๋๋ ๋น๊ต๊ฐ์ด ์ผ์นํ ๋ ๊ธฐ์กด์ ์์๋ฅผ ๋ณด์กดํ๋ค. ๊ทธ๋ ๊ธฐ์ ์ด stable_sort ํจ์๋ ๊ธฐ์ค์ ๋ง์๋๋ก ์ค์ ํ ์๋ ์์ผ๋ฉฐ!? ์
๋ ฅ๋ ์์๋ ๋ณด์กดํ ์ ์๋ ์ด์ด๋ ์น๊ตฌ๋ค~ ์ด stable_sort ํจ์๋ฅผ ์ฌ์ฉํ BOJ 10814 ํ์ด๋ ์๋์ ๊ฐ๋ค. // BOJ 10814 With stable_sort #include using namespace std; bool cmp(p..
[C++] pair vector๋ฅผ sort! ๋๋ฒ์งธ๊ฐ์ ๊ธฐ์ค์ผ๋ก๋ ์ ๋ ฌ ๊ฐ๋ฅํ๋ค๊ฑฐ!
[C++] pair vector๋ฅผ sort! ๋๋ฒ์งธ๊ฐ์ ๊ธฐ์ค์ผ๋ก๋ ์ ๋ ฌ ๊ฐ๋ฅํ๋ค๊ฑฐ!
2021.08.06vector v1; vector v2; vector v3; ์ขํ, ์ด๋ฆ์ด ๋ฐ๋ก ์๋ ์ซ์ ๋ฑ์ ๋ด์ ๋ ์์ฃผ ์ฐ๋ pair๋ก ์ด๋ฃจ์ด์ง ๋ฒกํฐ๋ฅผ ์ ๋ ฌํ๊ณ ์ ํ๋ค..! // test.cpp #include using namespace std; int main() { vector v; v.push_back(make_pair(1, 2)); v.push_back(make_pair(1, 0)); v.push_back(make_pair(2, 0)); v.push_back(make_pair(2, 2)); sort(v.begin(), v.end()); for (int i = 0; i < 4; ++i) { cout
[MAC] bits/stdc++.h ์ฌ์ฉํ๋ ๋ฒ
[MAC] bits/stdc++.h ์ฌ์ฉํ๋ ๋ฒ
2021.07.30/* ๋งฅ์์ bits/stdc++.h๋ฅผ ์ฌ์ฉํ๋ ค๊ณ ํ ๋ ์ฌ์ฉํ๋ ๋ฒ์
๋๋ค..! */ ์ฐ์ bits/stdc++.h๋ ๋ง์ด ์ฐ์ด๋ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ค์ ํฌํจํ ๋ชจ๋ ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ค์ด ํฌํจ๋ ํค๋๋ก ํ์ํ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ค๋ง๋ค ์ถ๊ฐํด์ค์ผ๋๋ ์๊ณ ๋ฅผ ๋์ด์ค ์ ์๋ ๊ทธ๋ฐ ์๋ตฅํ ํค๋์
๋๋ค. ์ด๋ฅผ ๋งฅ์์ ์ฌ์ฉํ๊ธฐ ์ํด์๋ ๋ฐ๋ก ์ถ๊ฐ๋ฅผ ํด์ค์ผํฉ๋๋ค..! cd /usr/local/include ์ฐ์ ์์ ๋ช
๋ น์ด๋ฅผ ํฐ๋ฏธ๋์ ์
๋ ฅํด /usr/local/include ๋๋ ํ ๋ฆฌ๋ก ์ด๋ํด์ค๋๋ค. ๋ฐฑ์ค, ํ๋ก๊ทธ๋๋จธ์ค ๋ฑ ์ฝ๋ฉํ
์คํธ ๋ฌธ์ ์ฌ์ดํธ์ ์ฑ์ ์๋ฒ์์๋ ์ปดํ์ผ๋ฌ๋ก gcc๋ฅผ ์ฌ์ฉํฉ๋๋ค. gcc์ default include path๋ฅผ ํ์ธํด๋ณด๋ฉด ์ ์ฌ์ง๊ณผ ๊ฐ์ด /usr/local/include ์์ ๊ฐ์ ธ์ค๋ ๊ฒ์ ํ์ธํ ์ ์์ต..