Algorithm (๋ฐฐ์ด)
(๋ณธ ๊ธ์ https://www.youtube.com/watch?v=mBeyFsHqzHg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=4 ์ฐธ์กฐ)
[ ํน์ง ]
์์์ ์์น์ ์๋ ์์๋ฅผ ํ์ธ / ๋ณ๊ฒฝ => O(1)
์์๋ฅผ ๋์ ์ถ๊ฐ => O(1)
๋ง์ง๋ง ์์๋ฅผ ์ ๊ฑฐ => O(1)
์์์ ์์น์ ์์๋ฅผ ์ถ๊ฐ / ์ ๊ฑฐ => O(N)
(๋๋จธ์ง ์์๋ค์ ๋ฏธ๋ฃจ๊ณ / ๋น๊ฒจ์ผ ํ๊ธฐ ๋๋ฌธ)
[ ํ ]
- ๋ฐฐ์ด์ ํน์ ๊ฐ์ผ๋ก ์ด๊ธฐํ ์ํฌ ๋ -> fillํจ์ ์ด์ฉ(algorithm ํค๋)
: 3๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์ผ๋ fill์ด ๊ฐ์ฅ ์ค์ ์ฌ์ง๊ฐ ์ ๊ณ ํธํ๋ค!
1) 1์ฐจ์ ๋ฐฐ์ด
int a[21]; fill(a,a+21,0);
2) 2์ฐจ์ ๋ฐฐ์ด
int b[21][31]; for(int i=0; i<21;i++) fill(b[i],b[i]+31,0);
[ vector ]
[ ๊ฐ๋ ]
STL์์ ์ ๊ณตํ๋ ๋ฐฐ์ด๊ณผ ๋น์ทํ ์๋ฃ๊ตฌ์กฐ
์์๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์ฐ์ํด์ ์ ์ฅ๋๋ค.
๋ฐฐ์ด๊ณผ ๋ค๋ฅด๊ฒ ๊ฐ๋ณ์
์๋ก์ด ์์ ์ถ๊ฐ ์ ๋ฉ๋ชจ๋ฆฌ ์ฌ ํ ๋น ํ ์ด์ ์์ ๋ณต์ฌํ๋ค
(2^n๊ฐ ๋จ์๋ก ๋ฉ๋ชจ๋ฆฌ ํ ๋น)
[ ์์ฑ ]
vector<int> v; // ๋น์ด์๋ ๋ฒกํฐ ์์ฑ vector<int> v(5); // 0์ผ๋ก ์ด๊ธฐํ๋ 5๊ฐ์ ์์๋ฅผ ๊ฐ์ง๋ ๋ฒกํฐ vector<int> v(5,2) // 2๋ก ์ด๊ธฐํ๋ 5๊ฐ์ ์์๋ฅผ ๊ฐ์ง๋๋ฒกํฐ vector<int> v2(v1) // v1์ ๋ณต์ฌํ ๋ฒกํฐ v2
[ ๋ด์ฅํจ์ ]
: ์๋๋ 'vector' ํค๋ํ์ผ์ ์ถ๊ฐํด์ผ ํ๋ค!
- insert()
- O(N) : ์์๋ฅผ ๋ฐ๊ณ ์ ์ฅํ๊ธฐ ๋๋ฌธ
v.insert(v.begin(),1) // ์ธ๋ฑ์ค 0์ 1 ์ฝ์ v.insert(v.begin()+2, 3) // ์ธ๋ฑ์ค 2์ 3 ์ฝ์ v.insert(v.end(), 5) // v.end()๋ ๋ง์ง๋ง ๋ค์ ๋ถ๋ถ์ ๊ฐ๋ฆฌํด // ์ฆ, ๋ง์ง๋ง ์์ ๋ค์๋ถ๋ถ์ 5 ์ฝ์ v.insert(v.end()-1, 5) // ๋ง์ง๋ง ์์์๋ฆฌ์ 5 ์ฝ์ /* ๋ฐํ ๊ฐ์ ์ฝ์ ํ ์์น์ iterator */ vector<int>::iterator it = v.insert(v.begin()+1,2); // it๋ ์ฝ์ ํ ์์น์ธ ์ธ๋ฑ์ค 1์ ๊ฐ๋ฆฌํจ๋ค.
- erase()
- O(N) : ์์๋ฅผ ์ญ์ ํ๊ณ ๋น๊ธฐ๊ธฐ ๋๋ฌธ
/* ๋๋ฒ์งธ ๋งค๊ฐ๋ณ์ ์์น ์ ๊น์ง ์ญ์ ! */ v.erase(v.begin()+2) // ์ธ๋ฑ์ค 2 ์ญ์ v.erase(v.begin(), v.begin()+3) // ์ธ๋ฑ์ค 0~2 ์ญ์ v.erase(v.begin(), v.end()) // ์ฒ์~๋ ๋ชจ๋ ์ญ์
- push_back
- O(1)
v.push_back(1); // ๊ฐ์ฅ ๋ค์ 1 ์ฝ์
- pop.back
- O(1)
v.pop_back(); // ๊ฐ์ฅ ๋ง์ง๋ง ์์ ์ญ์
- size : vector์ ์์ดํ ๊ฐ์ ๋ฐํ
- capacity : vector์ ํฌ๊ธฐ ๋ฐํ
- vector์ ํฌ๊ธฐ๋ ์์ ๊ฐ์๋ฅผ ํฌํจํ ์ ์๋ ์ต์์
2์ ์ ๊ณฑ์์ ํฌ๊ธฐ๋ฅผ ๊ฐ๋๋ค
ex) 3 item -> 4
5 item -> 8
9 item -> 16
[ iterator ]
- v.begin() : vector์ ์ฒซ๋ฒ์งธ ์์น๋ฅผ ๊ฐ๋ฆฌํค๋ iterator
- v.end() : vector์ ๋ง์ง๋ง ์์ ๋ค์ ์์น๋ฅผ ๊ฐ๋ฆฌํค๋ iterator
[ vector ์ํ ]
1) vector ํฌ๊ธฐ ์ด์ฉ
for(int i=0; i < v.size(); i++) cout << v.at(i); // v[i]๋ ๊ฐ๋ฅ
2) iterator ์ด์ฉ
for(auto i=v.begin(); i != v.end(); i++) cout << *i ;
3) range-based for loop (C++11)
: c++ 11 ์ด์์ ์ง์ํด์ผ ํ๋ค.for(int e : v) cout << e ; /* ๋ด๋ถ์์ ๊ฐ์ ๋ฐ๊ฟ์ผ ํ ๋! */ for(int& e : v) // ์ฐธ์กฐ์๋ก ์ ๊ทผํ๋ฉด ์๋ณธ์ด ๋ฐ๋๋ค. cout << e ;
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(Algorithm (๋ฐฐ์ด)), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@neity16/Algorithm-๋ฐฐ์ด์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ
์ธ ๋ฐ๊ฒฌ์ ์ ๋
(Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค