알고리즘 풀이법접근

문제 이해 -> 풀이법 접근 -> 구현 -> 해결

평균 문제의 제한시간 1~5초 1초에 실행할 수 있는 최대 연산 횟수는 약 1억번

• N의 범위가 500: 시간 복잡도가 O(N^3) 이하인 알고리즘을 설계
• N의 범위가 2,000: 시간 복잡도가 O(N^2) 이하인 알고리즘을 설계
• N의 범위가 100,000: 시간 복잡도가 O(NlogN) 이하인 알고리즘을 설계
• N의 범위가 10,000,000: 시간 복잡도가 O(N) 이하인 알고리즘을 설계
• N의 범위가 10,000,000,000: 시간 복잡도가 O(logN) 이하인 알고리즘을 설계

완전탐색 DFS BFS DP 그리디 이분탐색 투포인터 스택 큐

O(n!)

• 브루트 포스: 완전 탐색 문제에서 모든 가능한 경우를 시도하는 경우.

O(2^n)

• 브루트 포스: 특정 조합 문제에서 모든 부분 집합을 시도하는 경우.
• 재귀: 피보나치 수열을 재귀적으로 계산할 때 중복 계산을 하는 경우.

O(n^2)

• 브루트 포스: 이중 루프를 사용하는 문제.
• DP: 일부 동적 계획법 문제

O(n log n)

• 그리디: 동전 문제

O(n)

• 선형 탐색: 배열이나 리스트에서 순차적으로 탐색.
• DFS (깊이 우선 탐색): 그래프나 트리 탐색 시.
• BFS (너비 우선 탐색): 그래프나 트리 탐색 시.

O(log n)

• 이분 탐색: 정렬된 배열에서 이분 탐색을 할 때.
• 이진 트리: 이진 탐색 트리에서 삽입, 삭제, 검색 시 평균 시간복잡도.

O(1)

• 해시 함수: 해시 테이블에서 삽입, 삭제, 검색 시 평균 시간복잡도.
• 상수 연산: 간단한 수학적 연산, 변수 접근.
• 인덱스 접근: 배열의 특정 인덱스에 접근할 때.