Algorithm Test

복잡도

1. 시간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

2. 공간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

3. 빅오 표기법

O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^n)

4. 시간제한에 따른 시간 복잡도 설계

시간제한이 1초인 문제를 만났을 때 일반적인 기준

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계해야 한다.
• N의 범위가 2000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계해야 한다.
• N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계해야 한다.
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계해야 한다.

---

1. 스택/큐

• 1주차 문제 : 주식가격/기능개발/다리를 지나는 트럭
• 1주차 스택/큐 배우러 가기 (클릭)

---

2. 완전탐색/이분탐색

• 2주차 문제 : 모의고사/소수찾기/숫자카드2
• 2주차 완전탐색/이분탐색 배우러 가기(클릭)

---

3. BFS/DFS

• 3주차 문제 : DFS와 BFS, 바이러스, 타겟넘버
• 3주차 BFS/DFS 배우러 가기(클릭)

---

4. 진법변환/비트연산

• 4주차 문제 : 팩토리얼 진법, 진법 변환, 비밀지도
• 4주차 진법변환/비트연산 배우러 가기(클릭)

---

5. 해시

• 5주차 문제 : Hashing, 완주하지 못한 선수, 전화번호목록
• 5주차 해시 배우러 가기(클릭)

---

6. 재귀함수

• 6주차 문제 : 이진수 변환, 팩토리얼, 괄호변환
• 6주차 재귀함수 배우러 가기(클릭)

---

7. 동적계획법

• 7주차 문제 : 계단 오르기, 정수삼각형, N으로 표현
• 7주차 동적계획법 배우러 가기(클릭)

---

8. 다익스트라

• 8주차 문제 : 배달, 특정 거리의 도시 찾기, 가장 먼 노드
• 8주차 다익스트라 배우러 가기(클릭)

---

Reference

이것이 취업을 위한 코딩 테스트다 with Python