[[TableOfContents]]
= 수업 =
== 진행 ==
1. 장소 : 구글 밋으로 진행
2. 시간 : 3/20 14:00 ~ 16:00

== 내용 ==
 * 위키 작성법
 * [https://github.com/sindresorhus/awesome 깃허브 awesome 저장소 소개]

 * 복잡도, 입출력, 동적 할당
 * pair, vector, auto, for-each
 * 스택, 큐, 덱, 리스트
 * [https://docs.google.com/presentation/d/1_bQVuPl8-74TnaRa2j58vETGAD9YNvFX2Le2j_Bs6ZA/edit?usp=sharing 수업 진행 PPT]

= 숙제 =
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++은 대회 준비로 많이 쓰고 파이썬은 코드짜는 시간이 적게 걸리며 자바는 개발에서 보편적이다.
   (코틀린 등의 앱개발 언어도 자주 쓰이는 추세이기는 하다.)
 *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

}}}

== 한예준 ==
{{{
 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) 구조, 먼저 들어온게 먼저 나간다. 스케쥴링할 때 많이 쓴다. 
}}}

= 후기 =
 * '''후기 작성 요령''' : 후기는 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++을 익혀서 자료구조로 구현해보고 싶다.

----
-----------------------------------
[새싹교실/2021]
[새싹교실/2021/시작이반]