[[TableOfContents]] = 수업 = == 진행 == 1. 장소 : 구글 밋으로 진행 예정 2. 시간 : 3/20 14:00 ~ 16:00 == 내용 == * 위키 작성법 * [https://github.com/sindresorhus/awesome 깃허브 awesome 저장소 소개] * [https://docs.google.com/presentation/d/1_bQVuPl8-74TnaRa2j58vETGAD9YNvFX2Le2j_Bs6ZA/edit?usp=sharing 수업 진행] = 숙제 = 1. 수업 내용 정리하기 2. 아래 문제들 풀어오기 - 10문제(선정 예정) 3. 수업 PPT에 있는 스택, 큐, 덱 소스코드 보고 익히기 = 수업 내용 정리 = == 김도엽 == {{{ 1. 프로그래밍 언어 비교 보통 대회를 준비한다면 시간면에서 앞서가는 C/C++를 사용한다. Python은 코드가 간결해 들이는 시간이 적고, Java는 타이핑양은 많지만 우리나라에서 가장 많이 쓰인다. 2. 복잡도 * 시간 복잡도 보통 빅O 표기로 나타낸다. 빅O 표기법은 n이 무한대로 가는 경우를 상정하기 때문에 최고차수만 취급하고 계수는 무시한다. https://baactree.tistory.com/26 발췌 - 보통 1억개의 계산이 1초동안 이루어진다고 보면 된다고 한다. * 공간 복잡도 사용할 배열의 크기 * 자료형 크기 = 공간 복잡도 예를들어 128 MB 제한이 있고 int 배열을 사용한다면 128 MB = 134'217'728 Byte이고 int는 4 Byte이므로 int배열의 크기는 약 3천만을 넘으면 안된다. 3. 입출력 속도 비교 천만개의 수를 입출력 받았을 떄 걸린 시간을 기준으로 비교한 결과가 있다. 입력 : https://www.acmicpc.net/blog/view/56 출력 : https://www.acmicpc.net/blog/view/57 cin으로 입력을 받으면 평균 2.1742초가 걸린다. 대신 다음 코드를 넣으면 평균 0.5938초로 줄어든다. ios_base::sync_with_stdio(false); cin.tie(NULL); 이는 scanf의 평균 0.9206초보다 빠르다. 출력은 차이가 더 심하다. cout << i << endl; 으로 출력하면 평균 11.5322초가 걸린다. 대신 다음 코드를 넣으면 평균 0.8272초가 걸린다. ios_base::sync_with_stdio(false); cout.tie(NULL); cout << i << '\n'; 이는 printf("%d\n", i);의 평균 0.8614초보다도 빠른 시간이다. 4. 동적 할당 본래 C에서 int* arr; arr = (int*)malloc(sizeof int* n); 로 동적 할당해야 할 것을 C++에서는 int* arr = new int[n];로 간편하게 할 수 있다. 5. STL, C++문법 Standard Template Library * pair : 2개의 자료형을 묶는데 사용. 3개 이상은 tuple이 있지만 구조체가 더 많이 쓰임. * vector : 동적배열이 가능하다. push_back, pop_back, clear, resize 등등 많은 함수들이 있다. * auto : 자동으로 타입을 추론해서 선언하는데 도움을 준다. * range based for : 파이썬의 for문과 닮아있다. 6. 자료구조 * deque 앞뒤 양쪽에서 추가와 제거가 가능하다. vector처럼 index 참조가 가능하지만, 연속 메모리 공간이 아니므로 이터레이터는 사용할 수 없다. * lsit STL list는 이중 연결 리스트 기반이다. 반대말은 단일 연결 리스트. 새로운 원소의 추가와 삭제가 빠르다는 강점이 있다. * stack 후입선출(LIFO). STL stack이 있지만 vector와 겹쳐서 vector가 더 많이 쓰인다. * queue 선입선출(FIFO). }}} == 한윤호 == {{{ 여기에 정리해주세요 }}} == 한예준 == {{{ C는 절차지향, C++은 객체지향이다. C++11부터 함수형 언어의 패러다임이 도입되었다. (C++11부터 3년마다 한번씩 표준을 낸다. 가장 최신은 C++20) 복잡도 - 시간 복잡도, 공간 복잡도가 있다. 시간 복잡도는 실행 시간 등에 관한, 공간 복잡도는 배열 등에서 공간을 잡는 것에 관한 것이다. 메모리 초과는 거의 일어나지 않는다. 빅O 표기법 - 시간복잡도를 표현하는 방법. 상수는 없애서 표현한다. 입출력 속도(입력 속도) - ios_base::sync_with_stdio(false); 쓰면 더 빨라진다. 동적 메모리 할당 - C언어에서 malloc 쓰는 것보다 c++에서 쉽게 사용 가능 STL - Standard Template Library, C++에서 사용하는 라이브러리 template, pair, vector,... C++11에서 auto를 사용하여 자동으로 타입을 추론하도록 할 수 있다. 헤더파일 - , ,... -> 웬만한 헤더파일 선언되어 있음! [자료구조] deque - 앞뒤 모두에서 pop, push 가능, 헤더파일: list - 링크드 리스트: 이중 연결 리스트, 단일 연결 리스트 stack - LIFO(Last In First Out) 구조, 나중에 들어온게 먼저 나간다. vector로도 충분히 구현이 가능하다. 재귀의 개념이 stack. queue - FIFO(First In First Out) 구조, 먼저 들어온게 먼저 나간다. 스케쥴링할 때 많이 쓴다. }}} = 후기 = * '''후기 작성 요령''' : 후기는 F4(ThreeFs + Future Action Plan)에 맞게 작성해주세요. * Facts, Feelings, Findings, Future Action Plan. 즉, 사실, 느낀 점, 깨달은 점, 앞으로의 계획. 박인서: 김도엽: C++ 문법 입문을 시작했다. C++의 iterator도 그렇고 포인터도 많이 나오니 C 포인터 문법을 다시 봐야되나 싶은 생각이 들었다. 여태까지 포인터를 안쓰고도 프로그램을 만들어와서 포인터를 몰라도 될 줄 알았는데 이번 수업에서 잘못된 생각이란걸 알게 되었다. 포인터를 쓸 수 있다면 자주 써서 익숙해져야겠다. 한윤호: 한예준: C++라는 새로운 언어와 자료구조(deque, list, stack, queue)에 대해 간략히 배웠다. C는 생각보다 C++과 많이 달랐고, 훨씬 어려워보였다... 항상 C++ 관련 코드를 보면 이게 뭐지 싶었는데 이제는 어느정도(?) 이해할 수 있을 것 같다. 빨리 C++을 익혀서 자료구조로 구현해보고 싶다. ---- ----------------------------------- [새싹교실/2021] [새싹교실/2021/시작이반]