[독서] 이것이 취업을 위한 코딩 테스트다.

시간 복잡도(Big-O 표기법)

1. 정의

• 빅오 표기법(Big-O): 알고리즘의 연산 횟수(복잡도)를 표현하는 표기법.
• 가장 빠르게 증가하는 항(주요 요소)만 고려.

2. 예제

• 데이터 합산:→ 반복문은 데이터 수(N)에 비례하므로 O(N).
• array = [3, 5, 1, 2, 4] # N = 5 summary = 0 for x in array: summary += x print(summary) # 출력: 15
• 상수 연산:→ 연산 횟수는 1회 → O(1)

• a = 5
  b = 7
  print(a + b)

• 중첩 반복문:→ 이중 반복문: N * N 연산 → O(N²).
• for i in array: for j in array: temp = i * j print(temp)

3. 시간 복잡도 선택 기준

1. 데이터 크기 (N)에 따른 설계 기준
   • N ≤ 500: O(N²) 가능.
   • N ≤ 2,000: O(N²) 가능.
   • N ≤ 100,000: O(NlogN) 필요.
   • N ≤ 10,000,000: O(N) 필요.
2. 최악의 경우 고려
   • 퀵 정렬 평균: O(NlogN) / 최악: O(N²).
   • 최악의 시간 복잡도를 중심으로 설계 필요.

---

공간 복잡도

• 시간 복잡도와 유사하게 빅오 표기법 사용.
• 제한 메모리 예시: 128MB.
• 배열 기반 문제 해결에 자주 사용됨.

메모리 사용량 예시 (int 기준)

• N = 1,000,000 → 약 4MB 필요.
• 메모리 제약 고려하여 자료구조 선택.

---

1. 기술 면접 유형 및 준비 전략

1.1 기술 면접의 주요 유형

1. 알고리즘 문제 풀이 및 질의응답
   • 코딩 테스트 내용을 기반으로 문제 풀이 및 설명 요구.
   • 준비 방법:
     • 정렬, 탐색 알고리즘의 원리와 시간 복잡도 정리.
     • 상황에 따른 최적 알고리즘 선택 및 이유 설명 연습.
2. 포트폴리오 질의응답
   • 프로젝트 경험과 관련 기술에 대한 질문.
   • 준비 방법:
     • 관련 프로젝트를 정리하고, 코드와 기능 설명 준비.
     • 클라우드 배포(AWS, GCP) 경험 추가.
     • 깃허브에 소스코드 공유 및 문서화 필수.
3. 컴퓨터공학 기초 지식 질의응답
   • 운영체제, 네트워크, 데이터베이스 이론 확인.
   • 주요 주제:
     • OS: 멀티 스레딩, 메모리 관리.
     • 네트워크: TCP/UDP, HTTP/HTTPS 차이.
     • DB: 정규화, 인덱스, NoSQL 개념.

---

2. 기술 면접의 어려움과 대응 전략

1. 면접관별 질문 스타일 차이
   • 수학/알고리즘 중시 vs. 라이브러리/프레임워크 활용 경험 중시.
   • 대응법:
     • 폭넓은 주제 준비.
     • 설명할 때 논리적 구조 유지.
2. 불합격 시 대처법
   • 모든 내용을 완벽히 준비하는 것은 불가능.
   • 조언:
     • 실패 원인 분석 및 보완.
     • 반복 연습을 통해 향상.

---

3. 인성 면접 준비

3.1 주요 질문 및 답변 팁

1. Q: 개발하면서 가장 행복했던 일은?
   • A: 개발 성과나 보람 있는 순간을 구체적으로 설명.
   • 핵심: 개발에 대한 열정과 동기 부여를 강조.
2. Q: 가장 열정적으로 참여한 프로젝트는?
   • A: 프로젝트 개요, 본인 역할, 기여 내용 구체화.
   • 핵심: 문제 해결 과정 및 배운 점 강조.