U E D R , A S I H C RSS

새싹교실/2021/시작이반/2회차


1. 수업

1.1. 진행

1. 장소 : 구글 밋으로 진행
2. 시간 : 3/27 10:00 ~ 12:00(강사 개인 사정으로 인한 시간 변경)

1.2. 내용

  • 그래프(인접행렬, 인접리스트), 트리, 탐색(DFS, BFS)
  • set, map, 우선순위 큐
  • 최대/최소, 문자열, 수학
  • 수업 진행

2. 숙제

1. 수업 내용 정리하기
2. 후기 작성하기
3. 수업 PPT 문제들 풀어보기

3. 수업 내용 정리

3.1. 김도엽

 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 <string>
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<vector<int>> adj;
 adj.resize(n, vector<int>(n));
  10-2. set, map
 set<int> s; s,insert(x);
 map<string, string> girlmap; girlmap[name]=group; cout << it.first;
  10-3. queue
 priority_queue<int> 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, ',');

3.2. 한윤호

그래프 - 정점(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까지 비교)

3.3. 한예준

그래프 - 정점(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 써도 된다.

소수 찾기 문제 - 소수로 판정해야 하는 양이 많을 경우 에라토스테네스의 체를 사용하면 좋다.

4. 후기

  • 후기 작성 요령 : 후기는 F4(ThreeFs + Future Action Plan)에 맞게 작성해주세요.
  • Facts, Feelings, Findings, Future Action Plan. 즉, 사실, 느낀 점, 깨달은 점, 앞으로의 계획.

  • 박인서: 오늘은 그래프, 트리, 문자열과 관련 있는 자료구조들과, 최대/최소, 수학과 관련된 알고리즘들을 배웠다. 비대면 상황에서 다들 힘들겠지만 생각보다 잘 이해하고 따라오려고 노력하는 것이 보인다. 앞으로 많은 준비를 하도록 스스로 노력해야겠다고 생각했다.

  • 김도엽: set, map, vector 등 STL 자료구조들이 많이, 다양하게 있다. 이들을 공부하다보면 배열만 쓰던 것보다 훨씬 간편하게 알고리즘 문제들을 해결할 수 있었을 것이라는 생각이 들었다. 배열만 사용해서 풀어온 경험이 나쁘다고 할 순 없겠지만 그래도 인생 손해본 느낌이었다. 실제로 자료구조를 알면 알수록 문제를 어떻게 풀어야 할지가 더 선명하게 보였다. 하지만 아직 자료구조를 다루는 것이 미숙해서 다른 사람들의 코드를 더 많이 읽어보고 내 것으로 만드는 공부를 계속해 나갈 것이다. 사담으로 데이터 추가를 했던 1152번 문제가 연습문제로 나와서 굉장히 반가웠다.

  • 한윤호: 그래프, 트리, 우선순위 큐 등의 자료구조와 탐색, 그리고 c++에서 문자열을 다루는 방법과 함께 수학문제 풀이방법을 배웠다. 에라토스테네스의 체를 for문으로 구현한 코드가 기억에 남는다. 코드를 보면 이해할 수 있지만 문제만 보고 혼자 c++로 코드를 짤 수 있을까 생각할만큼 아직 낯설지만 코드를 많이 접하고 문제를 풀면서 익숙해져야겠다는 생각을 했다.

  • 한예준: 그래프, 인접행렬, 인접 리스트, 트리, 탐색 방법 중 DFS와 BFS, 이진 탐색 트리, 우선순위 큐에 대해 배웠고, 이를 이용한 예제들과 몇 가지 수학문제도 알아보았다. 특히 수학문제에서 유클리드 호제법을 사용한다든지 에라토스테네스의 체를 사용하는 방법도 있다는 것을 알게 되었다. 아직 수월하게 사용하기에는 조금 어렵게 느껴졌지만 여러 예제를 풀면서 익혀야겠다고 생각했다.



Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-04-03 04:25:17
Processing time 0.0299 sec