Revision as of 02:07, 19 May 2021

수업

진행

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

내용

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

숙제

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

수업 내용 정리

김도엽

 정렬
15가지 정렬 알고리즘 시각화 : https://www.youtube.com/watch?v=kPRA0W1kECg&t=1s&ab_channel=TimoBingmann

 stl sort, stable_sort
stl sort는 O(nlogn)의 시간복잡도를 가지는 정렬이다. 하지만 입력 순서는 보장하지 않는다. 이를 보완하는 것이 stable_sort이다.

 stl sort로 내림차순 정렬하기
기본적으론 오름차순 정렬이다. 만약 내림차순 정렬을 하고 싶다면 다음의 4가지 방법이 있다.
 1. greater<int>() [from functional]
sort(s.begin(), s.end(), greater<int>());
 2. reverse() [from algorithm]
sort(s.begin(), s.end());
reverse(s.begin(), s.end());
 3. bool operator

한윤호

<정렬>
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/

한예준

후기

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

박인서:

김도엽:

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

한예준:

새싹교실/2021 새싹교실/2021/시작이반

@@ Line 17: / Line 17: @@
 = 수업 내용 정리 =
 == 김도엽 ==
    정렬
 가지 정렬 알고리즘 시각화 : https://www.youtube.com/watch?v=kPRA0W1kECg&amp;t=1s&amp;ab_channel=TimoBingmann