2주 (6장 ~ 8장)
6. big-O
예제7
모든 경우가 O(n)과 같다
- O(N + P), P < N / 2일 때
- N이 지배적인 항이므로 O(P)는 무시해도 괜찮다
- O(2N)
- 상수항은 무시할 수 있으므로 O(N)과 같다
- O(N + logN)
- O(N)이 O(logN)보다 지배적인 항이므로 O(logN)은 버려도 된다
- O(N + M)
- N, M 사이에 어떤 연관 관계도 보이지 않으므로 여기에선 두 변수 모두를 표시해줘야 한다
예제10
- 소수 판별은 루트 n까지만 하면 된다
- 제곱근보다 큰 수로 나누어 떨어지는 경우가 존재한다면, 그에 상응하는 제곱근보다 작은 수로도 나누어 떨어지기 때문이다
예제12
추가 문제 4
변수 count의 값은 정확히 a / b가 된다.
while 루프는 count 값만큼 반복하므로 a / b
추가 문제 10
단순히 숫자가 들어왔을 경우 그 숫자의 자릿수만큼 돌면 된다고 생각했다.
EX) 1000 -> 3번
여기서 1000과 3의 관계를 놓쳤다.
자리수의 개수가 d라면 해당 숫자는 아무리 커도 10^d보다 작을 수밖에 없다.
만약 n = 10^d라면 d = logn이 되고 따라서 수행시간은 O(logN)이다.
추가 문제 11
O(kC^k)
여기서 k는 문자열의 길이, c는 알파벳의 개수다. 모든 문자열을 생성하는 데 걸리는 시간은 O(c^k)이 걸리고, 각 문자열이 정렬된 문자열인지 확인하는데는 O(k) 시간이 걸리므로 총 수행시간은 O(kC^k)이 된다.
이 문제 진짜 이해 안 됐는데 코드 하나씩 따라가보면서 이해했다.
7. 기술적 문제
준비하기
- 문제를 직접 푸는 훈련을 해야 한다
- 예제 문제를 직접 풀도록 노력해라
- 구현과 검증을 종이에 해라
- 컴퓨터로 실행해봐라
알고 있어야 하는 것들
- 복잡한 알고리즘을 알아야 하는 건 아니지만 기본기는 알아야 한다
- 연결 리스트
- 트리 / 트라이 / 그래프
- 스택&큐
- 힙
- Vector / ArrayList
- 해시테이블
- BFS / DFS
- 이진 탐색
- 병합 정렬
- 퀵 정렬
- 비트 조작
- 메모리(스택 vs 힙)
- 재귀
- 동적 프로그래밍
- big-O 시간 & 공간
- 개념 익히기
- 구현 해보기
- 공간 & 시간 복잡도 확인
2의 승수 표
문제 풀이를 어떻게 해야 하는가
- 듣기
- 예를 들기
- 무식하게 풀기
- 최적화
- 컴토하기
- 구현하기
- 테스트
위 과정을 끊임없이 면접관에게 설명해야 한다
경청하기
- 문제 설명을 잘 듣는다
- 모호한 부분을 질문한다
- "정렬된" 배열, "반복적으로" 수행해야 한다
- 중요한 정보를 활용한다
- 막혔을 경우 놓친 정보가 있는지 확인한다
예제를 직접 그려보기
- 문제를 바로 풀지 말고 예제를 그려보자
- 예제를 잘 잡아야 한다
무식한 방법으로 일단 해보기
- 무식한 방법으로 구현한다
- 면접관에게 설명한다 (시간 & 공간복잡도)
- 복잡한 거 고민하다가 면접관은 이것 조차도 못 푼다고 생각할 수 있다
최적화
- 문제의 조건으로 개선 가능한가?
- 다른 예시는 없을까?
- 메모리를 사용해서 시간을 개선할 수 없을까?
- 정보를 미리 계산할 수 없을까?
검토하기
- 가능한 완벽에 가깝게 검증 후 코딩한다
구현하기
- 함수로 잘 나눠라
- 변수명을 줄여쓰고 싶은 경우 면접관에서 해당 변수를 줄여 쓰겠다고 이야기한다
- 리팩터링은 면접관에게 물어본 후에 진행한다
- 오류 검사는 필요하다
- 오류 검사를 위한 코드를 작성할 것이라 면접관에게 언급한다
테스트
- 로직을 눈으로 확인한다
- i=1처럼 에러가 날만한 부분을 확인한다
- 규모가 작은 예시가 잘 돌아가는지 확인한다
BCR 가능한 최선의 수행 시간
- BCR: 최소한 이만큼은 확인해야 한다
- BCR을 하한선으로 두고 BCR이 아닌 부분을 개선할 수 있다
- BCR이 O(n)이라면 O(n)에 가능한 모든 사전 작업들을 해놓을 수 있다
- BCR만큼 시간복잡도를 줄였다면 공간복잡도를 개선해보자
8. 합격한 뒤에
- 입사 결정 기한은 보통 1~4주 정도
- 입사 제안은 공손하게 거절하자 언제 만날지 모른다
- 명백하게 이유를 들자
- 현재로서는 스타트업에 가는 것이 맞다
탈락통보
- 재지원하는 기회로 만들자
- 언제 재지원 가능한지 질문
- 피드백을 요청하자
- 다음 기회를 위해 어떻게 준비하면 좋을까요?
회사를 결정하는 기준
- 입사 후 무엇을 배울 수 있는지
- 경력을 발전시키는데 도움이 될지
- 미래의 경력도 생각해야 한다
- 좋은 동료
- 회사문화
- 근무시간
연봉협상
- 여러 곳에 합격하면 연협하기 좋다 (대안이 있다)
- 조금 더 구체적으로 많이 불러라
- 연봉 이외의 보상도 생각하라
- 대기업은 테이블이 존재한다
입사 후
- 커리어패스를 미리 그려두자
- 커리어를 잘 쌓고 있는지 주기적으로 점검하자
- 원하는 것이 있다면 적극적으로 요구하자
- 요구해야지 들어준다
- 적어도 일년에 한 번 정도는 면접을 보자
대충살자