1.2. 내용 ¶
- 위키 작성법
- 깃허브 awesome 저장소 소개
- 복잡도, 입출력, 동적 할당
- pair, vector, auto, for-each
- 스택, 큐, 덱, 리스트
- 수업 진행 PPT
3.1. 김도엽 ¶
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).
3.2. 한윤호 ¶
C는 절차지향이지만 C++은 객체지향이다. C++은 대회 준비로 많이 쓰고 파이썬은 코드짜는 시간이 적게 걸리며 자바는 개발에서 보편적이다. (코틀린 등의 앱개발 언어도 자주 쓰이는 추세이기는 하다.) *GitHub https://github.com/sindresorhus/awesome 참고 온라인 개발도 가능하지만 Online Judge 자체 개발 환경에서는 오프라인 IDE처럼 자동완성이 되지 않으니 주의가 필요하다. 복잡도(시간) - O(log(n)) while(n) n/=2; O(n) for(int i=0;i<n;i++); ㄴ기본이 될 두 경우이다. n을 무한으로 보내므로 가장 큰 차수만 남겨둔다. (공간) - 메모리 공간 STL(템플릿, pair, vector)에서 pair는 두개의 자료형을 묶을 수 있고 pair끼리 묶을 수도 있다. vector가 동적 배열로 할 수 있는 기능에는 끝값 추가/제거, 배열 사이즈 조정, 중간에 값 추가/제거 등이 있으며 배열이므로 인덱스로 값을 불러올 수 있다. 연속 메모리 공간을 이용하기 때문에 이터레이터 연산이 가능하다. for문을 이터레이터, range based for을 이용하여 작성할 수 있다. C의 <stdio.h>를 C++에서는 <cstdio>처럼 쓰는 것이 좋다. C++ 입출력에서는 <iostream>을 이용한다. gcc 등에서는 사용할 수 없지만 <bits/stdc++.h> 헤더파일은 다른 여러 헤더파일을 포함하여 선언한다. --- deque - 앞뒤 양쪽 원소 추가/제거 가능, 인덱스 참조 가능, 연속 메모리 공간이 아니므로 이터레이터 연산 불가 list (링크드 리스트: 각 노드가 데이터와 포인터를 가지고 한 줄로 연결지어 데이터를 저장하는 자료구조) - 순서 이동이 빠름, 원소 탐색에는 forward/reverse를 사용, 이중연결 & 단일연결 stack - 선입후출, 재귀, vector를 비교적 자주 사용 queue - 선입선출, Enqueue/Dequeue
3.3. 한예준 ¶
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를 사용하여 자동으로 타입을 추론하도록 할 수 있다. 헤더파일 - <stdio>, <iostream>,... <bits/stdc++.h> -> 웬만한 헤더파일 선언되어 있음! [자료구조] deque - 앞뒤 모두에서 pop, push 가능, 헤더파일: <deque> list - 링크드 리스트: 이중 연결 리스트, 단일 연결 리스트 stack - LIFO(Last In First Out) 구조, 나중에 들어온게 먼저 나간다. vector로도 충분히 구현이 가능하다. 재귀의 개념이 stack. queue - FIFO(First In First Out) 구조, 먼저 들어온게 먼저 나간다. 스케쥴링할 때 많이 쓴다.
4. 후기 ¶
- 후기 작성 요령 : 후기는 F4(ThreeFs + Future Action Plan)에 맞게 작성해주세요.
- Facts, Feelings, Findings, Future Action Plan. 즉, 사실, 느낀 점, 깨달은 점, 앞으로의 계획.
- 박인서: 처음으로 새싹교실을 시작하였다. C++ 내용도 있고 자료구조에 대한 내용도 처음 들었을 텐데 정리한 것을 보면 그래도 어느 정도 잘 따라오는 것 같았다. 역시 자료구조/알고리즘을 배우고 싶다고 온 새싹들인지라 다른 것 같다. 새싹들이 부담가지 않는 선에서 많은 내용들을 다뤄주고 싶다.
- 김도엽: C++ 문법 입문을 시작했다. C++의 iterator도 그렇고 포인터도 많이 나오니 C 포인터 문법을 다시 봐야되나 싶은 생각이 들었다. 여태까지 포인터를 안쓰고도 프로그램을 만들어와서 포인터를 몰라도 될 줄 알았는데 이번 수업에서 잘못된 생각이란걸 알게 되었다. 포인터를 쓸 수 있다면 자주 써서 익숙해져야겠다.
- 한윤호: 입출력에 소요되는 시간이 다른 것을 보고 복잡도를 배우면서 시간초과, 메모리초과로 문제를 틀리는 이유를 이해할 수 있었다. C를 배우긴 했지만 자바가 조금 더 익숙해서 C++은 못 따라갈까 걱정했는데 차근차근 가르쳐주셔서 C++ 코드도 이해할 수 있었다. 다음 주 한 주동안 오늘 수업과 C를 복습해서 다음 수업을 들어야겠다.
- 한예준: C++라는 새로운 언어와 자료구조(deque, list, stack, queue)에 대해 간략히 배웠다. C는 생각보다 C++과 많이 달랐고, 훨씬 어려워보였다... 항상 C++ 관련 코드를 보면 이게 뭐지 싶었는데 이제는 어느정도(?) 이해할 수 있을 것 같다. 빨리 C++을 익혀서 자료구조로 구현해보고 싶다.