0. 코딩테스트 유형 분석 + 기초작성요령

코딩테스트 언어, 어떤것이 유리한가?

• C++, Python, JAVA

C++ 의 특징 ( vs 파이썬)

장점

1. 동작 속도가 압도적으로 빠르다. (코스포스 랭킹 상위 티어인 분들은 압도적으로 c++ 을 사용)

• 같은 시간복잡도로 설계한 문제임에도 불구하고, 파이썬과 자바로 풀었을 때 시간초과가 뜨는 것이 c++ 은 무난하게 통과하는 경우가 존재함

2. 코딩테스트 응시 가능한 회사가 굉장히 많다.

3. 인터넷 자료가 정말 풍부하다.

4. C++ STL 에서 제공해주는 기능들이 꽤나 다양하다.

5. 장점은 아니지만, c++ 이 파고들면 엄청 어려운 문법과 설계구조를 가진 언어이다.
   But, 코딩테스트에서 요구하는 문법 및 알고리즘의 수준은 크게 어렵지 않다!

단점

1. 파이썬에 비해 숏코딩에 있어서 다소 불리한 면이 있다.

2. 특정 유형에 요구되는 내장함수들에 있어서 취약점이 두각된다. (문자열 처리 => 파이썬이 유리)

   • But, 그 외의 유형들에 있어서는 C++ STL 도 다양한 라이브러리 및 내장함수를 제공한다!
   • 이러한 특정 유형들에 대해서는 파이썬을 섞어서 코딩테스트에 응시하는 것도 NOT BAD.....

3. 최근들어 파이썬이 Pypy3 컴파일을 지원해줘서 어느정도 실행속도의 한계를 극복해나가는 경향이 보임 (그에따라 파이썬 응시자 비율이 점점 높아지고 있다.)

---

스터디에서 다룰 코딩테스트 유형 소개

• 아래와 같다.
• 각 유형에 대한 특징 + 출제 빈도수 + 사용되는 문법(간략히) 소개

. 기초작성 요령, 배경지식
1. Brute Force (완전탐색)
2. 배열
2. 링크드리스트
3. 스택
4. 스택 활용 (수식의 괄호쌍)
5. 큐
6. 덱
7. BFS (2차원 배열)  ( + DFS )
8. 재귀
9. BackTracking (백트래킹)
10. 정렬1 (Insertion, Selection, Bubble, Merge)
11. 정렬2 (Counting, Radix, Stable, STL Sort)
12. 그래프 (BFS, DFS, 인접행렬, 인접리스트)
13. 트리
14. Dynamic Programming (동적 계획법)
15. 그리디 (탐욕법)
16. 수학 (순열, 조합)
17. Binary Search (이진탐색)
18. 투 포인터
19. 해시 테이블
20. 이진탐색트리 (Binary Search Tree)
21. 우선순위 큐 (Priority Queue)
22. 시뮬레이션(구현)
===========================

학습 미정 : 다익스트라, 플로이드 와샬, 최소신장트리(Spanning SubTree), 
비트마스킹, 트라이(Trie), 위상정렬(Topological Sort)

---

기초 작성 요령 (모든 유형에 해당하는 필수 작성팁)

1. #include <bits/stdc++.h>

• 헤더파일 이름 드래그한 상태에서 => 오른쪽 마우스로 클릭 => "문서로 이동" 클릭
• 코테는 1분 1초가 너무너무 소중합니다.. 언제까지 헤더파일 선언하고 있을거야?

2. cout << "\n" 과 cout << endl 의 차이

• 제발..... "endl" 은 사용하지마.... 절대 쓰지마!!!!!!

3. 시간복잡도 & 인풋(입력값)의 범위를 잘 살펴보자.

• 같은 시간복잡도로 계산되더라도, 실행시간 초과 여부에 큰 영향을 미칠 수 있음에 유의!
• ex) 같은 O(n) 에 설계 되었더라도, O(mn) 과 O(1*n) 은 확연히 다르다.
  => m 값의 범위가 100, 10000 같이 작은 수이면 모를까, m = 1억(100000000) 이 되는 경우 시간 초과가 발생할 가능성이 굉장히 높다.

4. ios::sync_with__stdio(0); // cin.tie(0);

• main 함수에 작성할 때 무조건 맨 위에 반드시!!! 작성해라.
• 이거 쓰고 안쓰고 차이가 은근 크다.
• 예전에 이거 깜빡하고 안쓰니까 실행초과 뜨면 문제가, 이 두 문장 쓰자마자 통과한 케이스가 다수 있었음.

5. 인풋값의 범위를 잘 확인하자.

=> 정수형(int) 의 범위 : –2,147,483,648 ~ 2,147,483,647
=> 가끔씩 long long 을 사용해야하는 경우가 등장한다.

• 중요!!!! => 만일 int 배열에 int 타입의 범위를 벗어나는 값이 할당되는 경우,
  "오버플로우(OverFlow)" 또는 "언더플로우(UnderFlow) 가 발생해서 이상한 값이 할당될 것이다.

  • ex) char 배열 정수 "128" 할당되는 경우 OverFlow 가 발생 => 130이 아니라 뜬금없는 값인 "-127" 이 할당된다.

  • 이 문제는 배열을 "unsigned char" 타입 또는 "int" 타입 또는 "long long" 타입등으로 변환해서 해결 가능하다.

• 예시 문제) BOJ 2193 : 이친수
  => 배열에 할당되는 값이 생각보다 굉장히 큰 값이 할당된다. 따라서 int 배열을 선언했을 때 "틀렸습니다" 로 처리되는 값이 long long 타입으로 바꾸자 "정답 처리" 가 되었다.

6. 반복문에 돌릴 인풋값(n)

• while 도 좋지만, 더 정확한 표현을 위해선 for 문을 사용하는 것을 지향하자.
• 인풋값으로 주어진 n 값을 계속 활용해야 하는 문제가 다수 있음.
• while 문을 실수로 잘못 사용해서 n 값을 변경시키는 경우가 있다!

case1. for문을 사용하는 경우

int n;
cin >> n;

for(int i=0; i < n; i++){
  cout << "likelion" << "\n";
}

case2. while 문을 사용하는 경우

int n ;
cin >> n;

// 알고리즘 문제에서 while 문을 보통 이렇게 사용하는데, 
while(n--){
   cout << "likelion" << '\n';
}

~~ (중간에 이러쿠 저러쿠 코드)

// 아래처럼 또 n 을 다시 활용해야하는 경우가 등장할 수 있다.
while(n--){
  cout << "hi" << '\n';  // 앞서 n을 0으로 만들어버렸기 때문에, 현재 보고있는 이 반복문은 아예 실행되지 않는다.
}

7. (작성 요령은 아니지만) 문제를 풀때 반드시! 옆에다 종이를 두고 해결해나가자.

• 종이에가 논리를 작성하며 문제를 해결해나가자.

8. 배열 공간을 주어진 범위보다 안전빵으로 1~2 정도 크게 할당하자.

• ex) 문제의 조건에 따라서 배열의 크기를 90 으로 설정해도 되는 경우.
  => 안전빵으로 배열의 크기를 91 이나 92 정도로 설정해주면 좋다.

int arr[91];  => 이렇게 범위 넉넉하게 설정하자! 
int arr[92]; 

9. 전역변수 활용

• 되도록 모든 변수 및 배열 등은 전역으로 선언하는 것이 좋다.
• main 안에서 선언시 배열과 vector 의 경우 우리가 초기값을 따로 지정해주지 않는 셀은 쓰레기 값으로 초기활 될것이다. (ex. 배열 arr 의 1~8번 인덱스 셀까지 초기화를 진행한 경우,
• 변수, 배열, vector 등을 전역으로 선언할시 모든 필드의 값이 0으로 초기화됨에 유의하자.