[[TableOfContents]] = 수업 = == 진행 == 1. 장소 : 구글 밋으로 진행 2. 시간 : 4/3 14:45 ~ 16:00(강사 개인 사정으로 인한 늦은 시작) == 내용 == * 정렬, 완전탐색, 이분탐색 * 순열, 기타 STL 문법 * [https://docs.google.com/presentation/d/1t6UbPqhEfXPy5FbPn3ExvXqoUiejiNLW8BO5C3Rq76I/edit?usp=sharing 수업 진행] = 숙제 = 1. 수업 내용 정리하기 2. 후기 작성하기 3. 수업 PPT 문제들 풀어보기 = 수업 내용 정리 = == 김도엽 == {{{ }}} == 한윤호 == {{{ <정렬> 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: 옆 원소와 비교 bogo sort 등등 기본은 오름차순, greater -> 내림차순 compare 함수 (사용자 정의) ㄴC++ 11부터 람다표현식으로 표현가능하여 심플해짐 <완전탐색> 브루트포스 - 모든 경우의 수 전부 탐색 (for문, if문 사용) 비트마스크 - 비트연산자 이용 순열 - 모든 경우의 수를 구함 (next_permutation() 함수) DFS/BFS - 트리 탐색 (백트래킹) 재귀적 호출 (백트래킹) <이분탐색> 정렬된 값을 가운데 기준으로 탐색을 반복하여 원하는 값을 탐색 C++에서 binary_search(), upper_bound(), lower_bound() 함수 사용가능 ㄴ포인터값으로 반환한다 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/ }}} == 한예준 == {{{ }}} = 후기 = * '''후기 작성 요령''' : 후기는 F4(ThreeFs + Future Action Plan)에 맞게 작성해주세요. * Facts, Feelings, Findings, Future Action Plan. 즉, 사실, 느낀 점, 깨달은 점, 앞으로의 계획. * 박인서: * 김도엽: * 한윤호: * 한예준: ---- ----------------------------------- [새싹교실/2021] [새싹교실/2021/시작이반]