[[TableOfContents]] = 수업 = == 진행 == 1. 장소 : 구글 밋으로 진행 2. 시간 : 3/27 10:00 ~ 12:00(강사 개인 사정으로 인한 시간 변경) == 내용 == * 그래프(인접행렬, 인접리스트), 트리, 탐색(DFS, BFS) * set, map, 우선순위 큐 * 최대/최소, 문자열, 수학 * [https://docs.google.com/presentation/d/1NddloGyeQDUZzB1Tz36b6nY1l71hHu2gsfJF5XeRiqI/edit?usp=sharing 수업 진행] = 숙제 = 1. 수업 내용 정리하기 2. 후기 작성하기 3. 수업 PPT 문제들 풀어보기 = 수업 내용 정리 = == 김도엽 == {{{ 1. 그래프 정점(vertex)와 간선(edge)로 이루어진 자료구조. (무)방향 그래프. 간선에 가중치 부여 가능. 완전 그래프 : 모든 정점끼리 연결된 그래프. 정점의 개수 n -> 간선 수 n(n-1)/2 사이클 : 첫 정점과 마지막 정점이 동일한 경로가 존재하는 그래프. 다만 같은 정점을 두 번 이상 지나는 경로는 보통 사이클로 보지 않는다. 1-1. 그래프를 표현하는 방법(인접 행렬) 이차원 배열, i에서 j로 가는 간선이 있다면 arr[i][j] = 1; 직관적이다. 1-2. 그래프를 표현하는 방법(인접 리스트) i와 연결된 노드들을 리스트 형태로 저장. (ex. 1번 노드가 2번, 3번 노드와 연결 : 헤더 1 to 2 -> 2 to 3 -> 3 to NULL) 행렬보다 공간복잡도가 낮다. 2. 트리 나무를 뒤집은 모양의 자료구조. 그래프의 한 종류. 노드의 종류 : 부모 노드, 자식 노드, 형제 노드 ... 이진 트리 : 모든 부모 노드의 자식 노드의 개수가 최대 2개인 트리. 3. 탐색 3-1. DFS(Depth First Search) stack으로 구현. 더이상 갈 수 없을 때까지 전진. 막히면 막히지 않은 곳이 나올 때까지 후진. 그리고 다시 직진. 반복. 3-2. BFS(Breadth First Search) queue로 구현. 노드에서 갈 수 있는 모든 노드로 전진. 다시 전진한 모든 노드에서 갈 수 있는 모든 노드로 전진. 반복. 3-3. 이진 탐색 트리 왼쪽 서브트리 노드 값은 부모 노드보다 작은 값 오른쪽 서브트리 노드 값은 부모 노드보다 큰 값 4. set 중복을 혀용하지 않는 자료구조. 5. map key와 value를 쌍으로 저장하는 자료구조. 6. 우선순위 큐 우선순위가 높은 원소부터 pop하는 자료구조. 6-1. priority_queue 원소 값이 큰 것부터 pop 1927번 최소 힙 문제 힌트 : priority_queue는 최대힙을 기준으로 만들어 졌다. 따라서 -1을 곱하면 가장 작은 원소부터 pop할 수 있다. 7. STL min/max initialize lists를 이용한 배열을 넣으면 세 개 이상의 값 비교가 가능하다. (since C++11) 8. min_element/max_element 배열에서 최소/최대 값을 가진 iterator를 return 9. STL string C++에서 문자열을 다루기 쉬워짐. #include C 문자열(char*)로 바꾸려면 c_str()을 사용. ( string alpha="abc"; printf("%s\n", alpha.c_str()); ) string으로 전환 : to_string() string에서 전환 : stoi(), stoll(), stod() 10. 숙제 문제 solution 중 STL 10-1. vector vector> adj; adj.resize(n, vector(n)); 10-2. set, map set s; s,insert(x); map girlmap; girlmap[name]=group; cout << it.first; 10-3. queue priority_queue q; q.top(); 10-4. min, max min({a, b, c}), max({a, b, c}); //{}은 배열 선언할 떄 많이 봤는데, min, max에 배열을 넣어도 작동할까? 10-5. min_element, max_element cout << *min_element(a.begin(), a.end()); 10-6. string s.size(); stoi(s); stoll(s); stod(s); to_string(arr); getline(cin, s); getline(cin, s, ','); }}} == 한윤호 == {{{ 그래프 - 정점(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. 즉, 사실, 느낀 점, 깨달은 점, 앞으로의 계획. * 박인서: 오늘은 그래프, 트리, 문자열과 관련 있는 자료구조들과, 최대/최소, 수학과 관련된 알고리즘들을 배웠다. 비대면 상황에서 다들 힘들겠지만 생각보다 잘 이해하고 따라오려고 노력하는 것이 보인다. 앞으로 많은 준비를 하도록 스스로 노력해야겠다고 생각했다. * 김도엽: set, map, vector 등 STL 자료구조들이 많이, 다양하게 있다. 이들을 공부하다보면 배열만 쓰던 것보다 훨씬 간편하게 알고리즘 문제들을 해결할 수 있었을 것이라는 생각이 들었다. 배열만 사용해서 풀어온 경험이 나쁘다고 할 순 없겠지만 그래도 인생 손해본 느낌이었다. 실제로 자료구조를 알면 알수록 문제를 어떻게 풀어야 할지가 더 선명하게 보였다. 하지만 아직 자료구조를 다루는 것이 미숙해서 다른 사람들의 코드를 더 많이 읽어보고 내 것으로 만드는 공부를 계속해 나갈 것이다. 사담으로 데이터 추가를 했던 1152번 문제가 연습문제로 나와서 굉장히 반가웠다. * 한윤호: 그래프, 트리, 우선순위 큐 등의 자료구조와 탐색, 그리고 c++에서 문자열을 다루는 방법과 함께 수학문제 풀이방법을 배웠다. 에라토스테네스의 체를 for문으로 구현한 코드가 기억에 남는다. 코드를 보면 이해할 수 있지만 문제만 보고 혼자 c++로 코드를 짤 수 있을까 생각할만큼 아직 낯설지만 코드를 많이 접하고 문제를 풀면서 익숙해져야겠다는 생각을 했다. * 한예준: 그래프, 인접행렬, 인접 리스트, 트리, 탐색 방법 중 DFS와 BFS, 이진 탐색 트리, 우선순위 큐에 대해 배웠고, 이를 이용한 예제들과 몇 가지 수학문제도 알아보았다. 특히 수학문제에서 유클리드 호제법을 사용한다든지 에라토스테네스의 체를 사용하는 방법도 있다는 것을 알게 되었다. 아직 수월하게 사용하기에는 조금 어렵게 느껴졌지만 여러 예제를 풀면서 익혀야겠다고 생각했다. ---- ----------------------------------- [새싹교실/2021] [새싹교실/2021/시작이반]