[TIL] 230516 코딩테스트, 시간복잡도

코딩 테스트

🔽참고 강의

https://blog.encrypted.gg/921

[실전 알고리즘] 0x00강 - 오리엔테이션

 

 

✔중요한 세가지 능력

배경지식

문제해결능력

구현력

 

나의 경우 문제 해결 능력에는 자신있으나 

컴공 출신이 아니어서 배경지식이 부족하다.

사실 챗지피티나 구글링을 통해 이 부분을 채울 수 있다고 생각하는데,

코딩 테스트나 기술면접을 통과하려면 어쨌거나 배경지식도 잘 갖추어야한다.

취업을 위해서 뿐만 아니라 배경지식을 잘 습득해야 그것을 머릿속에서 잘 끼워맞춰서 응용할 수 있고 

설계의 범위가 넓어진다.

구현력은 배경지식과 문제해결능력이 갖춰지면 자동으로 따라오는 것이라고 생각된다.

 

 

 

 

코테 각종 대회가 있음..

특정 기관이나 회사의 코테 (ex. 삼성전자 SW test)

SW Expert Academy

SW Expert Academy

 

 

테스트 케이스는 시간조건 뿐만 아니라 메모리 제한도 통과해야 한다.

 

input 값의 제한 조건에 따라 달라질 수 있는 문제.

 

 

테스트 케이스의 인풋값 정보를 모르기 때문에 하나하나 디버깅을 잘 해야함!

 

 

참고,

제한조건 이외의 예외처리를 굳이 안 해도 됨.

input이 0이상이 들어온다고 했으면 그렇게만 들어오는 상황으로 코딩하면 됨

 

 

 

기출 문제 풀어보기

BFS/DFS/백트래킹/시뮬레이션 등….

전광판 문제 풀어보기

 

 

 

---

https://blog.encrypted.gg/922

[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

 

시간복잡도

빅오표기법(O)

 

3n +5 번의 계산을 한다면 → O(n)

 

무작위로 줄 서있는 사람 중에서 특정인을 찾는 코드의 시간 복잡도 : O(n)

최소1, 최대 n, 평균 n/2. 따라서 1/2는 버리고 n의 복잡도를 가짐.

 

이름 순서대로 줄 서있는 사람 중에서 특정인을 찾는 코드의 시간 복잡도 : O(lg n)

⇒ 업다운 게임처럼 중간 사람에게 먼저 물어보고, 작으면 앞쪽 중간에게 다시 물어보는 것을 반복…

반씩 계속 짜르니까 로그함수가 나옴.

 

 

 

시간 복잡도 표를 잘 확인하고,

N의 크기에 따른 허용 값을 알아두면 유용.

외울 필요는 x

 

 

O(1), O(lg N), O(N), O(NlgN)순으로 좋고

O(N^2)부터는 비추.

O(N!)은 가장 효율이 떨어짐.

 

 

 

 

공간복잡도

메모리 관련된 영역.

 

정수 자료형

char : 1byte = 8bit

2^8만큼의 표현이 가능

 

 

unsigned char : 0~255

char : -128 ~ 127

 

 

short : 2 byte

int : 4 byte

long long : 8 byte

integer overflow를 조심할 것

 

 

 

실수 자료형

float : 4 byte (유효숫자 6자리)

double : 8 byte (유효숫자 15자리)

 

소수점 표현 어떻게 ? → 2의 마이너스 승 이용.

 

double 에 long long범위 정수를 함부로 담으면 안됨.

long long은 최대 19자리라서.