[[TableOfContents]] = 수업 = == ì§„í–‰ == 1. 장소 : 구글 밋으로 ì§„í–‰ 2. 시간 : 3/27 10:00 ~ 12:00(강사 ê°œì¸ ì‚¬ì •ìœ¼ë¡œ ì¸í•œ 시간 변경) == ë‚´ìš© == * [https://docs.google.com/presentation/d/1NddloGyeQDUZzB1Tz36b6nY1l71hHu2gsfJF5XeRiqI/edit?usp=sharing 수업 ì§„í–‰] = ìˆ™ì œ = 1. 수업 ë‚´ìš© ì •ë¦¬í•˜ê¸° 2. 후기 작성하기 3. 수업 PPT ë¬¸ì œë“¤ 풀어보기 = 수업 ë‚´ìš© ì •ë¦¬ = == ê¹€ë„ì—½ == {{{ ì—¬ê¸°ì— ì •ë¦¬í•´ì£¼ì„¸ìš”. }}} == 한윤호 == {{{ 그래프 - ì •ì (vertex)ê³¼ ê°„ì„ (edge)으로 êµ¬ì„±ëœ ìžë£Œêµ¬ì¡°, ë°©í–¥ / 무방향 그래프 (사ì´í´: 첫 ì •ì ê³¼ 마지막 ì •ì ì´ ë™ì¼í•œ 경로가 ì¡´ìž¬í• ê²½ìš°) ì¸ì ‘í–‰ë ¬ - ì§ê´€ì / 공간ë‚비 ì¸ì ‘리스트 - vector로 구현가능, ê³µê°„ë³µìž¡ë„ / ì§ê´€ì ì´ì§€ 못함 트리 - 사ì´í´ì´ 존재하지 않는 그래프, ë¶€ëª¨ì €ìž¥ë²• / ìžì‹ì €ìž¥ë²• DFS - ê¹Šì´ ìš°ì„ íƒìƒ‰ (스íƒ) ì¸ì ‘한 노드를 ë°©ë¬¸í•˜ê³ ë” ë°©ë¬¸í• ë…¸ë“œê°€ 없으면 ì´ì „ì— ë°©ë¬¸í•œ ë…¸ë“œì— ì¸ì ‘하면서 방문하지 ì•Šì€ ë…¸ë“œê°€ 있는지 íƒìƒ‰ BFS - í¬ê¸° ìš°ì„ íƒìƒ‰ (í) 한 노드ì—서 시작해서 ì¸ì ‘한 노드부터 ëª¨ë‘ íƒìƒ‰ ì´ì§„ íƒìƒ‰ 트리 - 왼쪽: 부모노드보다 ìž‘ì€ ê°’ / 오른쪽: 부모노드보다 í° ê°’ (트리 순회: ì „ìœ„, 중위, 후위) set - ì¤‘ë³µì„ í—ˆìš©í•˜ì§€ 않는 ìžë£Œêµ¬ì¡° map - key와 value ì €ìž¥ ㄴ트리 형태ì´ë©° ì •ë ¬ëœ ìƒíƒœë¡œ ìœ ì§€ë¨ ìš°ì„ ìˆœìœ„ í - ì›ì†Œë¥¼ pop í• ë•Œ ìš°ì„ ìˆœìœ„ê°€ ë†’ì€ ê²ƒë¶€í„° pop (prioirty_queue : ì›ì†Œ ê°’ì´ í° ê²ƒë¶€í„° pop) ìµœì†Œíž™ì€ ì €ìž¥í• ë•Œ -ê³±í•˜ê³ popí• ë•Œ -곱하는 ê²ƒì„ ì‘ìš© min, max - ë‘ ê°’ 중 최대최소 (C++11부터 ë°°ì—´ì„ ë„£ì–´ì„œ 최대최소 êµ¬í•˜ê¸°ë„ ê°€ëŠ¥) min_element, max_element - ë°°ì—´ì—서 최대최소, returnê°’ì´ ì´í„°ë ˆì´í„° string - 문ìžì—´ì— +로 잇기와 push_back으로 ë§¨ë’¤ì— ë¬¸ìž ì¶”ê°€ 가능 getline으로 공백까지 ìž…ë ¥ë°›ê³ ë¬¸ìžë§ˆë‹¤ ë¹„êµ -> 공백 개수+1=단어 개수 다른 ìžë£Œí˜•->stirng: to_string / string->다른 ìžë£Œí˜• stoi, stoll, stod 등 ìœ í´ë¦¬ë“œ í˜¸ì œë²• - A,Bì˜ ìµœëŒ€ê³µì•½ìˆ˜ëŠ” B,A%Bì˜ ìµœëŒ€ê³µì•½ìˆ˜ì™€ 같다. +)C++ 17부터는 std::gcd 활용가능 ì—ë¼í† ìŠ¤í…Œë„¤ìŠ¤ì˜ ì²´ - 배수를 ì „ë¶€ 걸러내면서 소수를 찾는 방법 (i*i<=n까지 비êµ) }}} == 한예준 == {{{ 그래프 - ì •ì (vertex)와 ê°„ì„ (edge)로 ì´ë£¨ì–´ì ¸ 있는 ìžë£Œêµ¬ì¡°. ì¸ì ‘í–‰ë ¬ - 노드 ê°„ì˜ ì—°ê²° ìƒíƒœë¥¼ 나타낸 í–‰ë ¬, adj[i][j]ì— ëŒ€í•´ 노드 iì—서 노드 j로 가는 ê°„ì„ ì´ ìžˆìœ¼ë©´ 1, 없으면 0. ì¸ì ‘ 리스트 - adj[i]ì— ëŒ€í•´ 노드 iì— ì—°ê²°ëœ ë…¸ë“œë“¤ì„ ì›ì†Œë¡œ 갖는 vector, ê³µê°„ë³µìž¡ë„ ì¸¡ë©´ì—서 ì¸ì ‘í–‰ë ¬ë³´ë‹¤ 좋지만, ì§ê´€ì ì´ì§€ 못하다. 트리 - 나무를 ë’¤ì§‘ì€ ëª¨ì–‘ì„ í•˜ëŠ” ìžë£Œêµ¬ì¡°. 부모노드, ìžì‹ë…¸ë“œ, í˜•ì œë…¸ë“œë¡œ 표현한다. 특히 ì´ì§„트리는 ëª¨ë“ ë¶€ëª¨ 노드가 ìžì‹ 노드를 2ê°œ ì´í•˜ë¡œ ê°€ì§€ê³ ìžˆëŠ” 트리를 ë§í•œë‹¤. 부모노드는 하나지만 ìžì‹ë…¸ë“œëŠ” 여러 개를 가질 수 있어서 보통 ë¶€ëª¨ì €ìž¥ì„ ì‚¬ìš©í•œë‹¤. íƒìƒ‰ - í¬ê²Œ ê¹Šì´ ìš°ì„ íƒìƒ‰(DFS)와 너비 ìš°ì„ íƒìƒ‰(BFS)로 ì´ë£¨ì–´ì§„다. ì´ì§„ íƒìƒ‰ 트리 - 왼쪽 서브트리 ë…¸ë“œê°’ì´ í•ìƒ ë¶€ëª¨ë…¸ë“œ 값보다 ìž‘ê³ , 오른쪽 서브트리 ë…¸ë“œê°’ì€ ë¶€ëª¨ë…¸ë“œ 값보다 í¬ë‹¤. 따로 ì •ë ¬ì„ ì“°ì§€ ì•Šê³ setì´ë‚˜ mapì„ ì¨ë„ ëœë‹¤. ìš°ì„ ìˆœìœ„ í - ìš°ì„ ìˆœìœ„ê°€ ë†’ì€ ê²ƒë¶€í„° pop하는 ìžë£Œêµ¬ì¡°. ì›ì†Œê°’ì´ í° ê²ƒì´ íž™ì´ ë†’ì€ê±¸ë¡œ 한다. ----------------------------------------------- min/max - ë‘ ê°œì˜ ê°’ 중 최솟값 ë˜ëŠ” ìµœëŒ“ê°’ì„ ì•Œë ¤ì¤€ë‹¤. min_element/max_element - ì–´ë–¤ ë°°ì—´ì—ì„œì˜ ìµœëŒ“ê°’ ë˜ëŠ” ìµœì†Œê°’ì„ ë”°ì§ˆ 때 사용한다. 문ìžì—´ ë¶„ì„ ë¬¸ì œ - getline으로 문ìžì—´ ì „ì²´ë¥¼ 받아와서 ë„어쓰기(공백)ì˜ ê°œìˆ˜ë¥¼ ì„¸ë„ ëœë‹¤. 최대공약수와 최소공배수 ë¬¸ì œ - ìœ í´ë¦¬ë“œ í˜¸ì œë²• 사용해서 풀기; std::gcd ì¨ë„ ëœë‹¤. 소수 찾기 ë¬¸ì œ - 소수로 íŒì •해야 하는 ì–‘ì´ ë§Žì„ ê²½ìš° ì—ë¼í† ìŠ¤í…Œë„¤ìŠ¤ì˜ ì²´ë¥¼ 사용하면 좋다. }}} = 후기 = * '''후기 작성 ìš”ë ¹''' : 후기는 F4(ThreeFs + Future Action Plan)ì— ë§žê²Œ 작성해주세요. * Facts, Feelings, Findings, Future Action Plan. 즉, 사실, ëŠë‚€ ì , ê¹¨ë‹¬ì€ ì , ì•žìœ¼ë¡œì˜ ê³„íš. ë°•ì¸ì„œ: ê¹€ë„ì—½: 한윤호: 한예준: 그래프, ì¸ì ‘í–‰ë ¬, ì¸ì ‘ 리스트, 트리, íƒìƒ‰ 방법 중 DFS와 BFS, ì´ì§„ íƒìƒ‰ 트리, ìš°ì„ ìˆœìœ„ íì— ëŒ€í•´ ë°°ì› ê³ , ì´ë¥¼ ì´ìš©í•œ ì˜ˆì œë“¤ê³¼ 몇 가지 ìˆ˜í•™ë¬¸ì œë„ ì•Œì•„ë³´ì•˜ë‹¤. 특히 ìˆ˜í•™ë¬¸ì œì—서 ìœ í´ë¦¬ë“œ í˜¸ì œë²•ì„ ì‚¬ìš©í•œë‹¤ë“ ì§€ ì—ë¼í† ìŠ¤í…Œë„¤ìŠ¤ì˜ ì²´ë¥¼ 사용하는 ë°©ë²•ë„ ìžˆë‹¤ëŠ” ê²ƒì„ ì•Œê²Œ ë˜ì—ˆë‹¤. ì•„ì§ ìˆ˜ì›”í•˜ê²Œ 사용하기ì—는 조금 ì–´ë µê²Œ ëŠê»´ì¡Œì§€ë§Œ 여러 ì˜ˆì œë¥¼ 풀면서 ìµí˜€ì•¼ê² ë‹¤ê³ ìƒê°í–ˆë‹¤. ---- ----------------------------------- [새싹êµì‹¤/2021] [새싹êµì‹¤/2021/시작ì´ë°˜]