![▪ Vector와 달리 크기가 고정된 정적 배열이다.
▪ 하지만 int[]와 같은 배열과 달리 STL 알고리즘 함수들에 적용이 가능하며, 그 외에도 다
양한 것을 지원한다.
▪ 그러나 메모리를 여유 있게 잡아 사용하는 대회에서는 크게 활용성은 없는 듯 하다;;](https://image.slidesharecdn.com/3-cc11andetc-170828020810/85/3-C-C-11-and-ETC-29-320.jpg)
![▪ 아래와 같이 사용이 가능하며, []연산자와 기존의 bit 연산자를 지원한다.](https://image.slidesharecdn.com/3-cc11andetc-170828020810/85/3-C-C-11-and-ETC-32-320.jpg)
![▪ memset(초기화 시작할 주소,초기화 할 값(1바이트),초기화할 바이트 수)
▪ int dy[50][50];
▪ memset(dy,0x3f,sizeof(dy)
▪ 0x7f : 0x7f7f7f7f memset으로 초기화 할 수 있는 최대 int 크기
▪ 0x3f : 0x3f3f3f3f 오버 플로우 방지를 위한 적당한 int 크기
▪ 0 : 0으로 초기화
▪ 0xff : -1로 초기화, 메모이제이션에서 많이 사용
▪ 0x80 : 0x80808080 memset으로 초기화 할 수 있는 최소 int크기](https://image.slidesharecdn.com/3-cc11andetc-170828020810/85/3-C-C-11-and-ETC-51-320.jpg)
![std::map<std::string,int> map;
int num(std::string& str){
if(!map.count(str))map[str]=map.size();
return map[str];
}](https://image.slidesharecdn.com/3-cc11andetc-170828020810/85/3-C-C-11-and-ETC-58-320.jpg)
{return i+1;};
auto R=[&](int i){return i+n+1;};
s
0
1
n-1
0
1
m-1
t](https://image.slidesharecdn.com/3-cc11andetc-170828020810/85/3-C-C-11-and-ETC-61-320.jpg)
![▪ 문자열 처리의 경우 char[]보다 std::string이 확실히 효과적일 때가 많다.
▪ 하지만, 입출력 속도 문제로 std::cin,std::cout은 꺼려하기가 보통인데, scanf나 printf에
서는 다음과 같은 방법으로 쓸 수 있다.](https://image.slidesharecdn.com/3-cc11andetc-170828020810/85/3-C-C-11-and-ETC-78-320.jpg)
알고리즘 연합캠프 세미나 3-C (C++11 and ETC)
- 1. Seo youngsun(nein) Soongsil Univ.
- 2. ▪ C++11 ▪ Auto ▪ Initializer Lists ▪ Range-based for ▪ Tuple ▪ Lambda ▪ STL ▪ ETC
- 4. ▪ Problem Solving을 하는데 C++11로 해야하는 이유 ▪ 기존 C++으로는 표현하기 어려웠던 코드들을 비교적 간단하게 짤 수 있다.(=디버깅이 쉬워진 다.) ▪ 성능이 조금이지만 향상된다고 한다.
- 5. ▪ Auto는 컴파일 타임에 변수 타입을 자동으로 추론하여 선언한다.
- 6. ▪ STL 컨테이너나 구조체,클래스의 초기화나 min,max 등 다양하게 사용된다.
- 8. ▪ STL의 컨테이너나 배열 등등에서 모든 원소를 순회하는 for문
- 9. ▪ String의 경우는 다음 아래를 주의해야 한다.
- 10. ▪ Initializer Lists도 사용 가능하다.
- 11. ▪ Range-based for문에서 선언하는 변수가 레퍼런스 타입이 아니면, 값 복사가 발생하므 로 주의
- 12. ▪ Tuple은 pair의 확장형으로 1~10개의 원소를 담을 수 있다.
- 13. ▪ 원소는 get을 통하여 접근할 수 있다.
- 14. ▪ 아쉽게도 아래와 같이는 사용이 불가능하다.
- 15. ▪ Tie는 C++에서는 지원을 안하는 multi return이나 tuple, pair의 원소를 한번에 복사할 때 사용된다.
- 16. ▪ Minmax 함수에서 return 되는 값이 pair이기 때문에 다음과 같이도 쓸 수 있다.
- 17. ▪ Lambda는 익명 함수로, 기본적인 형태는 아래와 같다.
- 18. ▪ C++에 수많은 STL과 함수들이 Lambda함수를 지원한다.
- 19. ▪ 만약 바깥의 원소를 참조하여 정렬을 할 경우, 다음과 같이 할 수 있다.
- 20. ▪ Lambda함수의 자료형을 정의하고 싶으면, 아래와 같이 정의할 수 있다. Funtion은 functional헤더 파일 안에 정의되어 있다.
- 21. ▪ Lambda함수의 리턴타입을 지정하려 한다면 아래와 같이 할 수 있다.
- 22. ▪ 1) sort함수
- 23. ▪ 2) 정점 분류
- 24. ▪ 3) DFS
- 25. ▪ 4) all_of
- 26. ▪ vector나 queue, stack 등에서 원소를 넣을 때 emplace를 사용하면 constructor에 맞춰 서 원소가 들어간다.
- 27. ▪ C++11이 되면서 추가된 STL이 몇가지 있다. ▪ unordered_map ▪ unordered_multimap ▪ unordered_set ▪ unordered_multiset ▪ array
- 28. ▪ Hash를 이용하여 구현된 map으로 이론적으로는 O(1)의 시간복잡도를 가진 dictionary 이다. ▪ Hash를 이용하기 때문에 원소가 정렬이 되어있지는 않다. ▪ 기존의 std::map과 매우 유사하므로 거의 그대로 사용하면 된다. ▪ 다른 STL또한 큰 차이가 없으며, multi가 붙은 것은 원소를 중복해서 가질 수 있다.
- 29. ▪ Vector와 달리 크기가 고정된 정적 배열이다. ▪ 하지만 int[]와 같은 배열과 달리 STL 알고리즘 함수들에 적용이 가능하며, 그 외에도 다 양한 것을 지원한다. ▪ 그러나 메모리를 여유 있게 잡아 사용하는 대회에서는 크게 활용성은 없는 듯 하다;;
- 30. ▪ C++11 부터 정규표현식을 지원한다. ▪ 사용하기에 따라서 꽤 쓸 만하겠지만, 일단 패스
- 31. ▪ C++11에 추가된 것은 아니고, 기존에 있는 클래스이지만 간단하게 나마 다뤄볼까 한다. ▪ Bit의 경우 Bitmask를 통한 동적계획법 해결을 하는 경우가 있기 때문에 PS에서 종종 사 용된다. ▪ 대표적인 Bit 연산을 외워서 사용하여도 괜찮지만, 그것이 싫다면 Bitset을 찾아서 사용 해보는 것도 한 방법이 될 것이다.
- 32. ▪ 아래와 같이 사용이 가능하며, []연산자와 기존의 bit 연산자를 지원한다.
- 33. ▪ 다음과 같은 것도 지원한다.
- 34. ▪ 많이들 당연시 된다고 착각하는 거지만 C++11부터 되는 것이다. ▪ class나 struct에서 맴버 변수를 정의할때 초기화 할 수 있다.
- 35. ▪ using이 C++11으로 오면서 typedef과 거의 같은 효과를 가지게 되었다.
- 38. ▪ 문제를 풀 때 각 상황별로 해결해야하는 사소한 문제들이 많다. ▪ 입력부터 시작하여 데이터는 어떻게 저장해야 하는가 등 아주 여러가지 상황에 직면한 다. ▪ 이러한 문제들을 해결할 때 각자 매우 다양하고 참신한 방법들로 해결한다. ▪ 이러한 문제들을 각자 해결하고 공유해보는 시간을 가지자.
- 39. 1. 붙어있는 숫자 떨어트려 받기 2. EOF 3. char 입력 4. 문자열 파싱해서 받기
- 46. ▪ 많은 문제들이 한번 실행에 여러 테스트 케이스를 통과하여야 한다. ▪ 문제를 많이 풀다보면 이 부분을 코딩하기가 점점 귀찮아져 코드가 짧아진다.
- 47. int main(){ int tc; scanf(“%d”,&tc); while(tc--){ //solve problem } }
- 48. ▪ 테스트 케이스의 수를 주는 경우도 있지만, 처음 입력이 전부 0이거나 아예 아무 입력도 안주어지는 경우 등 다양한 경우가 있다.
- 49. // 0 0 일 때 종료 int n,m; scanf(“%d%d”,&n,&m); if(n+m==0)break; // EOF일때 종료 if(scanf(“%d%d”,&n,&m)==EOF)break;
- 50. ▪ for loop를 돌려 초기화를 해주는 경우도 있지만, memset함수를 이용하여 전체를 초기 화를 하는경우가 많다. ▪ 간혹 모든 테스트 케이스에 대해서 전체를 초기화하여 시간초과가 나는 경우가 있지만, 드문 경우라 많이들 사용한다.
- 51. ▪ memset(초기화 시작할 주소,초기화 할 값(1바이트),초기화할 바이트 수) ▪ int dy[50][50]; ▪ memset(dy,0x3f,sizeof(dy) ▪ 0x7f : 0x7f7f7f7f memset으로 초기화 할 수 있는 최대 int 크기 ▪ 0x3f : 0x3f3f3f3f 오버 플로우 방지를 위한 적당한 int 크기 ▪ 0 : 0으로 초기화 ▪ 0xff : -1로 초기화, 메모이제이션에서 많이 사용 ▪ 0x80 : 0x80808080 memset으로 초기화 할 수 있는 최소 int크기
- 52. ▪ 문제를 풀다 보면 다양한 상수 값을 코드에 넣는다. ▪ const int MOD=1000000007; ▪ double PI=acos(-1); ▪ const int INF=0x7fffffff; ▪ const int INF=0x7fffffff/2; // overflow 방지 ▪ const int MIN=0x80000000;
- 53. ▪ 간혹 입력으로 주어진 수열의 원소들의 중복을 제거하고 몇번째 원소인지 구해야 하는 경우가 있다. ▪ https://www.acmicpc.net/problem/10867 ▪ 좌표 압축
- 54. set or map 사용 vector<int> arr ={1,3,6,3,2,3,1}; vector<int> X=arr; std::sort(X.begin(),X.end()); X.erase(std::unique(X.begin(),X.end()),X.end()); for(int num:arr){ int idx=std::lower_bound(X.begin(),X.end(),num)-X.begin(); }
- 55. ▪ 간선의 정보가 주어졌을 때, 모든 정점을 한번씩 방문 ▪ n*n 격자판에서 최단거리 찾기 ▪ https://www.acmicpc.net/problem/7576
- 56. ▪ c++ 11문법의 typedef과 같은 역할 외에도 많은 일을 한다. ▪ 많은 사람들이 using namespace std;를 사용하는데 이는 전역변수를 선언할 때, std namespace안에 있는 무언가와 겹치는 경우 컴파일 에러가 난다. ▪ using std::vector; 와 같은 방법을 사용하면 필요한 것만 가져와 명시적으로 표현하기에 이에 대한 에러를 대비할 수 있다.
- 57. ▪ 문제 중 string 을 숫자로 바꿔서 풀어야 하는 경우가 있다. ▪ https://www.acmicpc.net/problem/13168
- 58. std::map<std::string,int> map; int num(std::string& str){ if(!map.count(str))map[str]=map.size(); return map[str]; }
- 59. ▪ 절대값 함수 abs는 특정 라이브러리만 include하면 실수 자료형에 대해서만 선언된다. ▪ 그냥 만들어 쓰는게 마음 편하다.
- 60. ▪ maximum flow문제들을 풀다보면 정점들에게 번호를 잘 매겨야 하는 경우가 있다. ▪ 보통 수식을 만들어 직접 때려 넣는데, 중간에 오타라도 나면은 바로 헬게이트가 열린다.
- 61. int source=0; int sink=n+m+1; auto L=[&](int i){return i+1;}; auto R=[&](int i){return i+n+1;}; s 0 1 n-1 0 1 m-1 t
- 62. ▪ fabs(double) // 실수 절대값 ▪ sqrt(double) // 제곱근 ▪ hypot(double,double) // sqrt(a*a+b*b) , 유클리드 거리
- 64. ▪ 평소 코딩을 하면서 간단하게 사용하고 있다는 것을 모아봤다. ▪ 개인적으로 괜찮다고 생각하는 것이니 별로라고 생각하면 안써도 괜찮다.
- 65. ▪ 맨 끝에 NULL문자가 있음을 이용해 loop의 끝을 지정
- 66. ▪ 특정 format(e.g., time,공백없는 숫자)의 입력과 출력에 대해서는 scanf와 printf를 잘 사용하면 편해진다.
- 67. ▪ 내부의 있는지 판단하는 것에 대해서 따 로 함수를 만들어 사용하면 코드가 깔끔 해진다. ▪ 또한 4방향으로 이동하는 것에서 다음 과 같이 하면 복붙신공을 발휘하지 않아 도 코딩을 할 수 있다.
- 68. ▪ 내부로 나가는 것에 대한 처리를 따로 처 리 하기 싫다면 배열 크기를 겉으로 한 칸씩 더 잡아 벽으로 초기화 해두는 방법 도 있다.
- 69. ▪ 종종 아스키 코드 값을 외워서 하시는 분 들이 있는데 작은따옴표안에 문자를 넣 으면 자동으로 아스키 코드로 변환된다.
- 70. ▪ 정수값에서 자리마다 처리를 할 때에는 나누기와 나머지를 적당히 사용한다,
- 71. ▪ 나머지연산은 때에 따라서 귀찮은 코드를 간단하게 만들어준다.(e.g. ACM Hotel) ▪ 보통 나머지 연산을 하면 0~n-1값이 나오지만 때에 따라서 1~n값이 필요 할 때가 있다. ▪ 다음과 같은 상황에서는 옆과 같이 하면 된다.
- 72. ▪ 일반적으로 정수값 나누기는 내림으 로 계산 되지만 때에 따라 올림, 반올 림이 필요할 수 있다. ▪ 다음과 같은 방법으로 올림, 반올림을 구현할 수 있따.
- 73. ▪ 시간과 같이 단위가 여러 개가 입력으로 들어오는 경우가 있다. ▪ 그러한 문제는 최소 단위로 변환한 후 풀면 편하다.
- 74. ▪ 작년 인터넷 예선에 특정 B진법으로 변환하는 문제가 있는데 이런 문제를 대비해서 진 법 변환을 일반화 해놓은 것을 알아두면 편하다. ▪ 각 자릿수는 B^n의 나머지 값들이기 때문에 다음과 같이 짜면 된다.
- 75. ▪ 자주 사용되는 상수(나머지 값) 의 경우, 오타로 인한 오답을 방 지하기 위해서 따로 선언해서 쓰 는 것이 좋다. ▪ 또한, 여러 개가 있는 경우 배열 로 묶어서 처리해주면 좋다.
- 76. ▪ 문제에 따라 정답이 없을 때 -1와 같은 특정 값을 출력하고 할 때가 있다. ▪ 이러한 경우 원래 정답이 담겨있는 곳에 그 값을 넣는 방법을 써도 괜찮다.
- 77. ▪ 피보나치와 같은 간단한 점화식의 경우 다음과 같이 간단하게 초기화를 할 수 있다.
- 78. ▪ 문자열 처리의 경우 char[]보다 std::string이 확실히 효과적일 때가 많다. ▪ 하지만, 입출력 속도 문제로 std::cin,std::cout은 꺼려하기가 보통인데, scanf나 printf에 서는 다음과 같은 방법으로 쓸 수 있다.
- 79. ▪ C++ reference - http://www.cplusplus.com/ ▪ C++11 – choi backjoon, startlink https://www.acmicpc.net/blog/view/10 ▪ 프로그래밍 대회 : C++11 이야기 – choi Jongwook http://www.slideshare.net/JongwookChoi/c11-draft?qid=9b8d3626-73a4-4d09- a5e5-4f5afaefb2f9&v=&b=&from_search=2