U E D R , A S I H C RSS

새싹교실/2021/시작이반/3회차 (rev. 1.5)

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


1. 수업

1.1. 진행

1. 장소 : 구글 밋으로 진행
2. 시간 : 4/3 14:45 ~ 16:00(강사 개인 사정으로 인한 늦은 시작)

1.2. 내용

  • 정렬, 완전탐색, 이분탐색
  • 순열, 기타 STL 문법
  • 수업 진행

2. 숙제

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

3. 수업 내용 정리

3.1. 김도엽


3.2. 한윤호

<정렬>
selection sort (O(n^2)): 최솟값을 앞으로 정렬 
insertion sort (O(n^2)): 원소마다 위치를 찾아주는 정렬
quick sort (O(nlogn)): pivot 중심으로 작으면 왼쪽, 크면 오른쪽으로 정렬
merge sort (O(nlogn)): 데이터를 합쳐가며 정렬, 작은 것부터 큰 것으로 순서로 합치기
heap sort (O(nlogn)): 우선순위 큐에 넣고 빼서 정렬
radix sort: 숫자 자릿수값 기준
std sort: merge sort와 유사하지만 quick sort 기반, 순서보장X
stable sort: merge sort 기반, 순서보장 O
bubble sort: 옆 원소와 비교
cocktail sort, bogo sort 등등

기본은 오름차순, greater -> 내림차순

compare 함수 (사용자 정의)
ㄴC++ 11부터 람다표현식으로 표현가능하여 심플해짐
연산자 오버로딩 (사용자 정의) (C++ 문법)

<완전탐색>
브루트포스 - 모든 경우의 수 전부 탐색 (for문, if문 사용)
비트마스크 - 비트연산자 이용
순열 - 모든 경우의 수를 구함 (next_permutation() 함수)
DFS/BFS - 트리 탐색 (백트래킹)
재귀적 호출 (백트래킹)

<이분탐색>
정렬된 값을 가운데 기준으로 탐색을 반복하여 원하는 값을 탐색
C++에서 binary_search(), upper_bound(), lower_bound() 함수 사용가능
ㄴ포인터값으로 반환한다

<STL 문법>
count (O(n)): 범위에 포함되어 있는 원소 중에서 해당 원소의 개수를 찾기
count_if (O(n)): 범위에 포함되어 있는 해당 조건의 원소 개수를 찾기
find (O(n)): 범위에 포함되어 있는 원소 중에서 해당 원소의 위치를 찾아 반환, 못 찾으면 end를 리턴
find_if (O(n)): 범위에 포함되어 있는 해당 조건의 원소 위치를 찾아 반환, 못 찾으면 end를 리턴
fill (O(n)): 컨테이너 초기화시 사용
reverse (O(n)): 컨테이너 역순으로 정렬
swap: 두 값 바꾸기
ㄴsort를 쓰면 거의 필요하지 않다

+)참고
STL 함수 파라미터 참고 사이트
http://cppreference.com/
https://www.cplusplus.com/

3.3. 한예준



4. 후기

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

  • 박인서:

  • 김도엽:

  • 한윤호: 백준 문제를 풀면서 마주쳤던 정렬, 완전탐색, 이분탐색에 대해서 배웠다. 생각보다 다양한 정렬방법이 있었고 어떻게 적용할지는 더 공부해야겠다는 생각이 들었다. 백준 문제를 풀 때 관련 내용을 조금씩 찾아보면서 풀지만 문제를 풀어도 개념에 대해서는 막연한 느낌이 있었는데 이번 회차에 배우면서 앞으로는 문제를 이해하고 풀 수 있을 것 같다.

  • 한예준:



Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-05-19 03:12:45
Processing time 0.0245 sec