[알고리즘] 알고리즘 문제 접근 과정

알고리즘 문제 접근 과정

• 좌, 우에서 시작하는 방법, 한쪽에서 같이 시작하는 방법 (ex)연속하는 수 더하기)
  1. 아이디어 : 문제를 어떻게 풀지 확실히 설계 후에 진행 (코드 작성 전에 확실히 설계 필요)
  2. 시간복잡도 : 내가 설계한 방법이 얼마나 오래 걸리는지 확인
  3. 자료구조 : 어떤 자료구조를 사용할지 계획

---

시간 복잡도

• 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
• 일반적으로 CPU는 1초에 10^8(약 1억)번의 연산 가능

시간 복잡도	최대 연산 횟수
O(N)	약 1억번
O(N^2)	약 1만번
O(N^3)	약 500번
O(2^N)	약 20번
O(N!)	10번

제한 시간이 1초 일 경우, N의 범위(입력 범위)에 따른 시간 복잡도 선택

• N의 범위가 500 (100): 시간 복잡도가 O(N^3) 이하인 알고리즘을 설계
• N의 범위가 2,000 (1,000): 시간 복잡도가 O(N^2) 이하인 알고리즘을 설계
• N의 범위가 100,000 (10,000): 시간 복잡도가 O(NlogN) 이하인 알고리즘을 설계 (동적프로그래밍, 이분탐색, 다익스트라, 투포인터 등)
• N의 범위가 10,000,000: 시간 복잡도가 O(N) 이하인 알고리즘을 설계
• N의 범위가 10,000,000,000 (10^8 이상): 시간 복잡도가 O(logN) 이하인 알고리즘을 설계 (수학적 기믹 필요)

---

목표

• 개념 정리 후에 문제 풀이 (개념별 5~7문제정도)
• 모든 개념 정리 후에는 분야별로 돌아가면서 문제 풀기
• 문자열, 구현, 수학 관련 문제도 풀어보기
• 하루에 한 문제씩 꾸준히
• BFS → DFS → 백트래킹 → 시뮬레이션 → 이진탐색 → 그리디(탐욕) → DP → MST → 다익스트라 → 플로이드 순서로
• 우선은 파이썬으로 그 다음은 자바