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 ;

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ