- 코테
- 단기간 준비
- 시간 복잡도
- 공간 복잡도
- 문제 처음 봤을 때
- 기본적으로 알아두어야 할 유형
- what is 코딩 테스트?
-> 왜 보는 거지?
우리의 실력 평가하기 위한 과정
기술 면접 : 이론적인 지식 확인, 포폴 질문, 회사에 대한 열정 확인, (시니어) 문제 풀이 화이트보딩
코딩테스트 : 얼마나 이해하는지 확인하기 위함
진짜로 아는지 확인하기 위함
현업에서는 안하는데 왜..?
-> 새로운 문제가 있을 때 해결할 수 있는지
-> 대기업, 잘나가는 스타트업
프로그래머스 기준 레벨 3, 해커랭크 기준 medium
: 코테 압박감 없음
어렵게 내는 기업은 3.5~4단계/ 해커랭크 hard까지도 한문제 나온다
최소 프로그래머스 1단계는 수월하게 풀 수 있어야 한다
코테 스타일
1. 중소기업, 스타트업 : 면전에서 코테 (노트북을 들고 오라고 하거나 빌려줘서)
2. 글로벌 시 : 온라인(구글 or 줌)으로 코테 (vscode 등 화면공유 시킴)
3. 네이버, 우형, 삼전 : 프로그래머스의 모든 기능을 활용한 코테
단기간 알고리즘 준비
computational thinking
- 주입식 교육 통해 알고리즘 학습 효과적 [템플릿!!]
: 많은 문제 풀고 유형에 대응할 수 있어야
: 일부 코테는 잘 알려진 유형들만 출제, 이 유형들을 접근하는 템플릿 존재
-> 어떤 케이스에 어떤 함수를 써서 풀 수 있는지 주입식으로 ex. TOY
-> 많이 풀면 풀수록 좋음
만약 풀 시간이 많은 날에는 레퍼 안 보고 차근차근 문제를 푸는 것이 가장 좋은 방법
꾸준히 고민하여 하나씩 해결하는 게 best
만약 시간이 없으면 레퍼 보고 빠르게 이해 GeeksforGeeks 추천
수강생일 때 코플릿, toy, 회고 열심히
시간이 있으면 프로그래머스, 백준
졸업하면 계속 코테 : 하루에 2문제 1주, 하루에 4문제 1주
-> 시간 관리, 회고
시간 복잡도
대부분의 문제는 실행시간 : 1초에 가깝게 디자인
1억번의 연산당 1초(그러므로 연산 횟수가 1억번을 넘어가지 않도록)
1초가 걸리는 입력의 크기
O(N) : 100, 000, 000
O(NlogN) : 5,000,000
O(N^2) : 10,000
O(N^3) : 500
O(2^N) : 26
O(N!) : 11
1개의 문을 여는 방법 : 1 O(1)
n개의 문을 여는 방법 : O(n)
->n 문의 개수만큼 써봐야 하니까 n에 정비례 ex.for문
n개의 열쇠로 n개의 문을 여는 방법 : O(n^2) ex.중첩반복문
사람/ 열쇠 / 집주인이 문을 여는 방법 : O(n^3) ex. for문 3번 중첩
=> 무조건 O(n^3)이라고 오바인 건 아니다
입력인 n이 작으면 괜찮기도
하지만 너무 커질 거 같으면 binary search를 사용하거나 n^2로 반복문의 개수를 줄이거나 한다
공간 복잡도
시간복잡도 만큼 중요하지 않다 왜냐면 시간 복잡도가 낮으면 공간도 주로 낮아지니까
js에서 보통 변수 하나는 8 byte
알고리즘 문제에 메모리 조건이 나올 수 있다
일반적으로 128/256/512 mb 자주 등장
배열 하나의 크기 1000
문제 처음 봤을 때
1.입력과 공간 상한을 확인한다
2.먼저 완전탐색으로 문제를 풀어본다 (알고리즘이 바로 떠올랐다면 그렇게 푸세요)
: 배열 메소드는 권장하지 않는다
: 함수 스코프가 헷갈릴 수 있으니까
3.문제 푸는 시간의 30~50%는 문제를 분석+ 수도코드 치는 데에만 사용한다 [매우 중요!!]
-> 이미 친 코드가 아깝게 되니까
기본적으로 알아두어야 할 유형
외워야 하고 코딩테스트 직전에 보고 가야한다!!
1. GCD
2. 순열/조합
3. 정렬은 Array.prototype.sort 사용 : 콜백함수 안 쓰면 문자열로 취급
4. DFS(재귀), BFS(큐)
5. 분할정복(재귀), DP => 감을 잡기 어렵기 때문에 케이스 스터디 필요 Geeksforgeeks
졸업한 것만으로도 러닝곡선이 빠르다
