{{{
그래프 - 정점(vertex)과 간선(edge)으로 구성된 자료구조, 방향/무방향 그래프가 있다.
(사이클: 첫 정점과 마지막 정점이 동일한 경로가 존재할 경우)
인접행렬 - 직관적 / 공간낭비
인접리스트 - 공간복잡도= 한윤호 ==
{{{
그래프 - 정점(vertex)과 간선(edge)으로 구성된 자료구조, 방향/무방향 그래프가 있다.
(사이클: 첫 정점과 마지막 정점이 동일한 경로가 존재할 경우)
인접행렬 - 직관적 / 공간낭비
인접리스트 - vector로 구현가능, 공간복잡도 / 직관적이지 못함
트리 - 사이클이 존재하지 않는 그래프, 부모저장법 / 자식저장법
DFS - 깊이 우선 탐색
BFS - 크기 우선 탐색== 한윤호 ==
{{{
그래프 - 정점(vertex)과 간선(edge)으로 구성된 자료구조, 방향/무방향 그래프가 있다.
(사이클: 첫 정점과 마지막 정점이 동일한 경로가 존재할 경우)
인접행렬 - 직관적 / 공간낭비
인접리스트 - 공간복잡도= 한윤호 ==
{{{
그래프 - 정점(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/시작이반]
