Difference between r1.2 and the current
@@ -17,7 +17,70 @@
= 수업 내용 정리 =
== 김도엽 ==
{{{
== 한윤호 ==
{{{
== 김도엽 ==
{{{
정렬
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
struct
{
bool operator()(int a, int b) const
{
return a < b;
}
} comp;
sort(s.begin(), s.end(), comp);
4. lambda expression
sort(s.begin(), s.end(), [](int a, int b) {
return a > b;
});
*완전 탐색
브루트 포스 : for + if로 모든 경우를 탐색
비트 마스크
순열
DFS/BFS
주로 재귀적 호출을 사용함
*이분 탐색
탐색하고자 하는 구역을 계속 둘로 쪼개가며 탐색하는 방법
굉장히 빠르지만 미리 정렬이 되어있어야 한다.
*binary_search
이분 탐색을 사용한다. 데이터의 유무를 확인할 수 있다. return값은 bool.
*upper_bound / lower/bound
upper_bound : value보다 작지 않은 첫 iterator
lower_bound : value보다 큰 첫 iterator
*next_permutation
말 그대로 다음 순열을 찾는 함수
*count
count(a.begin(), a.end(), 4); : a에 4가 몇 개 있는지 return
count_if(a.begin(), a.end(), [](int x) {return x%2==0;}); : 조건에 맞는 원소의 개수 return
엑셀의 count 함수와 닮아있다.
*find, find_if
해당 원소의 위치 / 해당 조건의 원소 위치 반환
못 찾으면 end return
*fill
fill(a.begin(), a.end(), 0); //a를 0으로 채움
container 초기화 시에 사용 가능
*swap
두 값을 바꾼다. 변수부터 구조체까지도 바꿀 수 있다.
}}}== 한윤호 ==
{{{
@@ -31,12 +94,13 @@
std sort: merge sort와 유사하지만 quick sort 기반, 순서보장X
stable sort: merge sort 기반, 순서보장 O
bubble sort: 옆 원소와 비교
기본은 오름차순, greater -> 내림차순
compare 함수 (사용자 정의)
ㄴC++ 11부터 람다표현식으로 표현가능하여 심플해짐
<완전탐색>
브루트포스 - 모든 경우의 수 전부 탐색 (for문, if문 사용)
stable sort: merge sort 기반, 순서보장 O
bubble sort: 옆 원소와 비교
bogo sort 등등
cocktail sort, bogo sort 등등
기본은 오름차순, greater -> 내림차순
compare 함수 (사용자 정의)
ㄴC++ 11부터 람다표현식으로 표현가능하여 심플해짐
연산자 오버로딩 (사용자 정의) (C++ 문법)
<완전탐색>
브루트포스 - 모든 경우의 수 전부 탐색 (for문, if문 사용)
@@ -78,7 +142,7 @@
* 김도엽:
* 한윤호:
* 한윤호: 백준 문제를 풀면서 마주쳤던 정렬, 완전탐색, 이분탐색에 대해서 배웠다. 생각보다 다양한 정렬방법이 있었고 어떻게 적용할지는 더 공부해야겠다는 생각이 들었다. 백준 문제를 풀 때 관련 내용을 조금씩 찾아보면서 풀지만 문제를 풀어도 개념에 대해서는 막연한 느낌이 있었는데 이번 회차에 배우면서 앞으로는 문제를 이해하고 풀 수 있을 것 같다.
* 한예준:
3.1. 김도엽 ¶
정렬 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 struct { bool operator()(int a, int b) const { return a < b; } } comp; sort(s.begin(), s.end(), comp); 4. lambda expression sort(s.begin(), s.end(), [](int a, int b) { return a > b; }); *완전 탐색 브루트 포스 : for + if로 모든 경우를 탐색 비트 마스크 순열 DFS/BFS 주로 재귀적 호출을 사용함 *이분 탐색 탐색하고자 하는 구역을 계속 둘로 쪼개가며 탐색하는 방법 굉장히 빠르지만 미리 정렬이 되어있어야 한다. *binary_search 이분 탐색을 사용한다. 데이터의 유무를 확인할 수 있다. return값은 bool. *upper_bound / lower/bound upper_bound : value보다 작지 않은 첫 iterator lower_bound : value보다 큰 첫 iterator *next_permutation 말 그대로 다음 순열을 찾는 함수 *count count(a.begin(), a.end(), 4); : a에 4가 몇 개 있는지 return count_if(a.begin(), a.end(), [](int x) {return x%2==0;}); : 조건에 맞는 원소의 개수 return 엑셀의 count 함수와 닮아있다. *find, find_if 해당 원소의 위치 / 해당 조건의 원소 위치 반환 못 찾으면 end return *fill fill(a.begin(), a.end(), 0); //a를 0으로 채움 container 초기화 시에 사용 가능 *swap 두 값을 바꾼다. 변수부터 구조체까지도 바꿀 수 있다.
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/
4. 후기 ¶
- 후기 작성 요령 : 후기는 F4(ThreeFs + Future Action Plan)에 맞게 작성해주세요.
- Facts, Feelings, Findings, Future Action Plan. 즉, 사실, 느낀 점, 깨달은 점, 앞으로의 계획.
- 박인서:
- 김도엽:
- 한윤호: 백준 문제를 풀면서 마주쳤던 정렬, 완전탐색, 이분탐색에 대해서 배웠다. 생각보다 다양한 정렬방법이 있었고 어떻게 적용할지는 더 공부해야겠다는 생각이 들었다. 백준 문제를 풀 때 관련 내용을 조금씩 찾아보면서 풀지만 문제를 풀어도 개념에 대해서는 막연한 느낌이 있었는데 이번 회차에 배우면서 앞으로는 문제를 이해하고 풀 수 있을 것 같다.
- 한예준: